Esercizi Risolti di Reti di Calcolatori

SOL: U = T / (T +2 T ) ; T = frame size / bwth = f/b

x x p x

U >= 50% se (f/b) / (f/b + 2 T ) >= 0.5, i.e. f/(f + 2b T ) >= 0.5 i.e.

p p

0.5 f >= b·T ; f >= 2·b·T = 2·4000·0.020 = 160 bit

p p

4) Messaggi di 1000 bit sono inviati su un canale satellitare con bwth 1 Mbps e ritardo di propagazione 270

msec. Gli ack sono sempre trasmessi in piggyback; gli header sono di lunghezza trascurabile. Si usano

#seq di 3 bit. Qual è il massimo utilizzo del canale ottenibile con (i) Idle RQ; (ii) Go-Back-N e (iii)

Selective Repeat?

SOL: ritardo di trasmissione T =1000 bit / 1 Mbps = 1 msec.

x

Idle RQ: U = T / (T +2 T ) = 1 / (1 + 2·270) = 0.18%

• x x p 3

Go-Back-N ha finestra grande MAX_SEQ = 2 -1=7; perciò U=k·T /(T +2·T ) = 7·1/(1+2·270) = 1.3%

• x x p

Selective Repeat ha finestra grande (MAX_SEQ+1)/2= (7+1)/2 = 4; perciò U=k·T /(T +2·T ) =

• x x p

4·1/(1+2·270) = 0.74%

5) Si consideri un canale satellitare di 64 Kbps privo di errore, usato per trasmettere messaggi di 512 B in

una direzione, con ack di taglia trascurabile trasmessi nell'altra. Qual è il max throughput per taglie di

finestra di 1, 7, 15 e 127?

SOL: T = 512·8/64000 = 0.064 sec. T = 270 msec. Con finestra 1 si inviano (512·8)=4096 bit in (0.064

x p - 1 -

A.A. 2010-2011 E.Pagani, G.P. Rossi

+2·0.27)=0.604 sec, perciò throughput è S =4096/0.604=6781.46 bps e U=T /(T +2T ) = 0.064/(0.064

1 x x p

+2·0.27)= 10.59%. Con finestra grande 7 S =7·S =47470 bps. Si ha U=1 per k=(T +2T )/T =

7 1 x p x

(0.064+2·0.27)/0.064=9, con throughput S =9·S =61 Kbps. Finestre più grandi sono inutili.

9 1

6) Una stazione deve trasmettere un msg di 1.5 Mb su un path di lunghezza 4 hop che la collega al

destinatario, e ogni hop è costituito da un link con bwth 1 Mbps. Si supponga che i tempi di

propagazione, elaborazione dati e accodamento ai router siano trascurabili. Qual è il ritardo di

trasmissione end-to-end se la rete adotta rispettivamente commutazione di messaggio o di pkt? Nel

secondo caso si assuma che i dati vengano frammentati in pkt da 1500 bit.

SOL: S R1 R2 R3 D

msg switching: 1 hop in 1.5 Mb / 1 Mbps = 1.5 sec; 1.5 · 4 hop = 6 sec.

• pkt switching: 1.5 Mb / 1500 b = 1000 pkt da trasmettere. Ogni pkt compie 1 hop in 1500 b / 1 Mbps =

• o o o o

1.5 ms. I pkt inviato a tempo 0; II pkt inviato a tempo 1.5 ms; III pkt inviato a 3 ms... Perciò 1000 pkt

inviato a 999 · 1.5 ms = 1.4985 sec. e ricevuto a destinazione entro 1.4985 sec + (4 · 0.0015) = 1.5045 sec

7) Sia data una rete tale che ho un path di 10 hop da sorgente a destinazione, e un ritardo di propagazione di

100 per hop. La banda dei canali è di 2 Mbps. Un'applicazione deve mandare 50 Mb di dati. Il

µsec

ritardo e2e è inferiore se la rete è a commutazione di circuito (assumendo 10 ms per il set-up) o se è a

commutazione di pkt (con pkt size 1 Kb)? -4

SOL: Circuito: 10 msec + (50 Mb / 2 Mbps) + (10·10 )sec=25.011 sec

Pkt: tempo trasmissione 1 pkt: 1 Kb / 2 Mbps = 0.5 msec; devo inviare 50 Mb/1Kb = 50000 pkt. L'ultimo pkt

è trasmesso a 49999 · (0.5 msec)= 24.99 sec. A ogni hop pkt spende 0.5 msec per ritrasmissione e 0.0001 sec

per propagazione, perciò ricevo ultimo pkt a 24.99 + (0.5 msec·10) + (10·0.0001)= 24.996. Conviene pkt

switching.

Se il tempo di set-up circuito è < (k-1)p/b [con k #hop, p pkt size e b bwth], allora conviene circuit

switching. Es: k=100 ...

8) Calcolare l'utilizzo di un canale avente banda di 6 Mbps e lunghezza del cavo in rame di 4 Km, ottenuto

da un protocollo di livello Trasporto che genera messaggi di taglia fissata 1.5 Kb e che adotta un approccio

di tipo stop-and-wait (Idle RQ).

SOL: Tempo di propagazione Tp = lunghezza cavo / velocità propagazione del segnale = 4 Km / 200000

-5

Km/s = 2 x 10 s. -4

Tempo di trasmissione Tx = frame size / bwth = 1.5 Kb / 6000 Kbps = 2.5 x 10 s.

-4 -4 -5

Utilizzo per Idle RQ è U = Tx / (Tx + 2Tp) = (2.5 x 10 )/( 2.5 x 10 + 2 x 2 x 10 ) = 86.21 %

9) Un blocco di dati da 3 Kb deve essere trasmesso tra due calcolatori connessi da un canale di

comunicazione in rame lungo 70 Km e avente banda di 60 Mbps. Calcolare l'utilizzo del canale se il livello

Trasporto usa un protocollo Go-Back-N con numeri di sequenza rappresentati con 3 bit.

-4 -5

SOL: Tp=70Km/200000 Km/s = 3.5 x 10 . Tx=3 Kb/60000 Kbps = 5x10 s.

3

Con 3 bit per numero di sequenza, il MAX-SEQ è 2 -1=7 e questa è la dimensione K della finestra di invio.

L'utilizzo è U=K Tx / (Tx +2 Tp) =

-5 -5 -4

7 x 5x10 /( 5x10 + 2 x 3.5 x 10 ) = 46.67%

10) Un blocco di dati da 4 Kb deve essere trasmesso tra due calcolatori connessi da un canale di

comunicazione in fibra lungo 50 Km e avente banda di 250 Mbps. Calcolare l'utilizzo del canale se il livello

- 2 -

A.A. 2010-2011 E.Pagani, G.P. Rossi

Trasporto usa un protocollo Selective Repeat con numeri di sequenza rappresentati con 4 bit.

-4 -5

SOL: Tp = 50/300000=1.67 x 10 s. Tx=4/250000=1.6 x 10 s. Con 4 bit per numero sequenza, il MAX-

4

SEQ è 2 -1=15 e la dimensione K della finestra di invio è (MAX-SEQ+1)/2=8. L'utilizzo è U=K Tx / (Tx

-5 -5 -4

+2 Tp) = 8x1.6 x 10 / (1.6 x 10 + 2 x 1.67 x 10 )= 36.57%

11) Si supponga che un IP access gateway debba instradare su una LAN Ethernet tre pacchetti provenienti da

una LAN in una rete non IP, contenenti rispettivamente 2875, 3862 e 1877 B di dati. Quanti frame Ethernet

vengono generati, e qual è il loro contenuto di dati?

SOL: In una classica Ethernet i frame contengono fino a 1500 B di dati; il livello IP aggiunge ai dati veri e

propri il proprio header di 20B. Pertanto:

il primo pacchetto viene spezzato in 2 frame contenenti rispettivamente (1480B dati + 20B header IP);

• (2875-1480) = (1395B dati + 20B header IP)

il secondo pacchetto viene spezzato in 3 frame contenenti rispettivamente (1480B dati + 20B header IP);

• /* 3862 – 1480 = 2382 > 1480 */ (1480B dati + 20B header IP); /* 2382-1480 = 902 */ (902B dati + 20B

header IP)

il terzo pacchetto viene spezzato in 2 frame contenenti rispettivamente (1480B dati + 20B header IP);

• (1877 – 1480) = (397B dati + 20B header IP)

12) Un amministratore di rete deve gestire una campus LAN a cui è assegnato l'indirizzo di classe B

150.10.0.0 . Assumendo che la rete comprenda 100 sottoreti ognuna delle quali connessa ad uno switch

FastEthernet usando un router, definire una appropriata subnet mask se il numero massimo di host connessi

ad ogni subnet è 70.

SOL: Per assegnare un netID ad almeno 100 subnet servono 7 bit (127 subnet). Per assegnare un hostID ad

almeno 70 host servono 7 bit. Quindi qualsiasi suddivisione che soddisfi tali vincoli è appropriata: (7 bit

netID + 9 bit hostID); oppure (8 bit netID + 8 bit hostID); oppure (9 bit netID + 7 bit hostID).

13) Ad una rete è stato allocato un blocco di 1024 indirizzi di rete da 200.30.0.0 a 200.30.3.255 .

Assumendo che sia usato CIDR, rappresentare questi indirizzi in forma binaria e derivare la netmask da

usare – in dotted notation – e il netID di questa rete. 8 8

SOL: 200.30.0.0 => 200 = 128 + 64 +8 => 11001000.00011110.[0] .[0]

200.30.3.255 => 11001000.00011110.00000011.11111111

8 8 8

Netmask deve annullare la differenza tra le due: [1] .[1] .11111100.[0]

ovvero 255.255.[128+64+32+16+8+4=]252.0 mentre netID è l'indirizzo base 200.30.0.0

14) L'Università di Bologna si fa assegnare le reti da 194.76.16._ a 194.76.23._ Calcolare la maschera usata

per fare CIDR.

SOL: 194 = 128 + 64 + 2 ; 76 = 64+8+4 ; 16=16 => 11000010 . 01001100 . 00010000 . _ sono 8 reti

256 - 8 = 248 = 128 +64+32+16+8 => 11111000 ;

mask: 11111111.11111111.11111000.00000000

calcolando l'ultimo ottetto di ogni rete del gruppo, si nota che differiscono per gli ultimi 3 bit

15) Convertire l'indirizzo IP esadecimale C22F1582 alla dotted notation

- 3 -

A.A. 2010-2011 E.Pagani, G.P. Rossi

SOL: Si considerano le cifre esadecimali a coppie: max FF = 16 x 15 + 15 = 255

C2=16 x 12 + 2=194; 2F= 16 x 2 + 15=47; 15= 16 x 1 + 5=21; 82= 16 x 8 + 2=130 . Quindi

194.47.21.130

16) Una rete di classe B ha subnet mask 255.255.240.0 Qual è il max# host per subnet? 12

SOL: 240=128+64+32+16 -> 11110000 perciò ho 4+8=12 bit per host ID, pertanto 2 -1=4095 host ID

possibili.

17) In un sistema che utilizza CIDR, le tabelle di routing hanno – come entry relativa alla ditta Acme Inc. – i

dati: 148.125.16.0 255.255.240.0. Dire qual è il numero massimo di host che possono essere connessi alla

rete di Acme, e quale tra le alternative seguenti indica l'indirizzo di un host nella rete:

- 10010100.01111101.00010110.10011100

- 10010101.01101001.00101001.01011011

- 11001011.00111100.00011011.10000111

- 10111001.01000111.01001100.10001001 o

SOL: I bit riservati per host identifier sono l'ultimo ottetto, e gli ultimi 4 bit del 3 ottetto (da 240 =

12

11110000 in binario). Con 8+4=12 bit si possono indirizzare 2 = 4096 host. La rappresentazione in binario

dell'indirizzo base è: 148=10010100 ; 125=01111101 ; 16=00010000. Quindi l'unico possibile indirizzo

valido per un host è il primo mostrato.

18) Nel grafo seguente, trovare lo shortest path da A ad ogni altra destinazione utilizzando l'algoritmo di

Dijkstra C (2,A)

A 2

4

A E

C E (6,B)

2 6 1

1 G G (9,F)

2

1

5 2 2

2 H H (9,F)

B D F

B D F 1 4 2

1 4 2 (4,D) (3,C) (7,D)

7 msg scambiati per fare broadcast tra 8 nodi

19) Rappresentare le tabelle di routing costruite dopo il primo scambio di Distance Vector nella rete mostrata

A C E

2 6

1

5 2

B D

1

t_0 A B C D E

- 4 -

A.A. 2010-2011 E.Pagani, G.P. Rossi

A 5,B 2,C non esiste non esiste

B 5,A non esiste 1,D 2,E

C 2,A non esiste 1,D 6,E

D non esiste 1,B 1,C non esiste

E non esiste 2,B 6,C non esiste

t_1 A B C D E

A 5,B 2,C 3,C 7,B

B 5,A 2,D 1,D 2,E

C 2,A 2,D 1,D 6,E

D 3,C 1,B 1,C 3,B

E 7,B 2,B 6,C 3,B

20) Si consideri la rete in figura. Usando Distance Vector, ad un certo tempo il nodo C riceve i seguenti

vettori (si assume che i costi alle destinazioni siano riportati in ordine alfabetico): da B (5, 0, 8, 12, 6, 2); da

D (16, 12, 6, 0, 9, 10); da E (7, 6, 3, 9, 0, 4). I costi stimati da C verso B, D ed E sono rispettivamente 6, 3, 5.

Qual è la nuova tabella di instradamento di C?

A B C D E F

B C B) 5 0 8 12 6 2 delay=6

A D D) 16 12 6 0 9 10 delay=3

E) 7 6 3 9 0 4 delay=5

E F A B C D E F

hop 11 6 0 3 5 8

da B B C D E B

21) Allo scopo di applicare OSPF, si rappresenti la rete seguente come un grafo o