Esercizio - Quattro pacchetti da A verso E e D in una rete store-and-forward

Testo. Nella rete della figura i router fanno commutazione di pacchetto a datagramma con store-and-forward; ogni router ha code indipendenti su ogni interfaccia di uscita. Al tempo $t=0$ la coda di uscita del server A contiene quattro pacchetti, nell'ordine di trasmissione, diretti a E, E, D, D. Lunghezze: $L_D=250$ byte, $L_E=1250$ byte. Le trasmissioni partono a $t=0$ in tutti i nodi. Calcolare l'istante in cui i quattro pacchetti arrivano a destinazione.

Topologia (A si collega a R1; i terminali B e C non hanno traffico in questo esercizio):

($C_3$ verso B e $C_4$ verso C partono da R2 ma nessun pacchetto li usa.) Il cammino verso E è $C_1\to C_2\to C_5\to C_7$, quello verso D è $C_1\to C_2\to C_5\to C_6$.

Teoria usata: Commutazione di circuito e di pacchettoUn nodo di commutazione (switch) può collegare ingresso e uscita in tre modi. Commutazione di circuito: si stabilisce prima un collegamento fisico dedicato (rete telefonica), tempo di consegna $T=3Nt_p+Nt_s+M/R$. Commutazione di pacchetto a datagramma: il messaggio è diviso in $K$ pacchetti con intestazione, ognuno è instradato indipendentemente con store-and-forward, $T=Nt_p+(N+K-1)\frac{M/K+H}{R}$, con $K_{ott}=\sqrt{(N-1)M/H}$. A circuito virtuale: tre fasi (setup, dati, chiusura), connessione logica dedicata ma senza risorse dedicate, identificatore locale che cambia a ogni salto.Commutazione di circuito e di pacchetto →, Analisi delle prestazioni di reteLe prestazioni di una rete si misurano con tre famiglie di metriche: traffico (bitrate $R_0$ massimo del collegamento, throughput $S\le R_0$ dati consegnati con successo, goodput al livello applicazione), ritardo (end-to-end $d_{tot}=d_{proc}+d_{queue}+d_{trans}+d_{prop}$ con $d_{trans}=L/R$ e $d_{prop}=d/v$; jitter; RTT) e capacità del tubo (BDP $=R\cdot$ ritardo, bit che riempiono il collegamento), più l'affidabilità (PER, PDR, PLR). Il throughput di un percorso è quello del collegamento collo di bottiglia, $\min$ dei bitrate, ricordando che i collegamenti condivisi dividono la capacità.Analisi delle prestazioni di rete →.

Modello e regola di calcolo

Un pacchetto $i$ che attraversa un collegamento con capacità $C$ e propagazione $\tau$ si comporta così:

1. è pronto nel nodo di partenza quando è stato ricevuto per intero (store-and-forward: il router non inizia a inoltrare finché non ha tutti i bit);
2. se il collegamento è occupato aspetta in coda (FIFO, in ordine di arrivo al nodo): la trasmissione inizia a $t_{inizio}=\max(t_{pronto},\,t_{libero})$;
3. dura $T=L/C$: finisce a $t_{fine}=t_{inizio}+T$ e il collegamento torna libero;
4. il pacchetto è pronto al nodo successivo a $t_{fine}+\tau$.

Il tempo di trasmissione $T=L/C$ va calcolato con $L$ in bit: $L_E=1250\cdot8=10000$ bit, $L_D=250\cdot8=2000$ bit. Per esempio il pacchetto E su $C_5$: $10\,000/(12{,}5\cdot10^{6})=0{,}8\cdot10^{-3}$ s $=0{,}8$ ms; il pacchetto D su $C_6$: $2000/(20\cdot10^{6})=0{,}1$ ms.

Passo 1: il collegamento $C_1$ (A → R1)

A trasmette i quattro pacchetti uno dopo l'altro, senza pause:

(tempi in ms). I pacchetti arrivano a R1 distanziati di $0{,}5$ ms, $0{,}1$ ms, $0{,}1$ ms.

Passo 2: il collegamento $C_2$ (R1 → R2), più lento di $C_1$

$C_2$ ha capacità metà di $C_1$, quindi i pacchetti si accodano in R1:

Passo 3: il collegamento $C_5$ (R2 → R3)

$C_5$ ($12{,}5$ Mbit/s) è più veloce di $C_2$ ($10$ Mbit/s), ma i pacchetti arrivano a R2 già in fila, e dopo E1 serve ancora $0{,}8$ ms:

Qui D1 aspetta E2 ($0{,}6$ ms) e D2 aspetta D1 ($0{,}56$ ms).

Passo 4: l'ultimo salto, due uscite diverse in R3

R3 ha due code di uscita indipendenti: $C_7$ verso E e $C_6$ verso D. I pacchetti per D non aspettano quelli per E.

• Verso E ($C_7$, $2$ ms per pacchetto): E1 inizia a $14{,}3$ e finisce a $16{,}3$; arriva a E a $16{,}3+0{,}2=\mathbf{16{,}5}$ ms. E2 era pronto a $15{,}3$ ma $C_7$ è occupato fino a $16{,}3$: inizia a $16{,}3$, finisce a $18{,}3$ e arriva a $18{,}3+0{,}2=\mathbf{18{,}5}$ ms.
• Verso D ($C_6$, $0{,}1$ ms): D1 inizia a $15{,}46$, finisce a $15{,}56$, arriva a $15{,}56+0{,}8=\mathbf{16{,}36}$ ms; D2 inizia a $15{,}62$, finisce a $15{,}72$, arriva a $\mathbf{16{,}52}$ ms.

Si nota che D1 e D2, partiti per ultimi, arrivano prima di E1: sono corti e il loro ultimo collegamento è veloce. E2 invece ricomincia a ritardare perché $C_7$ ($5$ Mbit/s) è il collo di bottiglia.

Confronto con la soluzione ufficiale

La soluzione ufficiale dà E1 $=16{,}5$ ms, E2 $=18{,}5$ ms, D1 $=16{,}36$ ms e per l'ultimo pacchetto $16{,}52$ ms. Coincide. Nell'ultima riga la soluzione scrive "second packet towards E", ma $16{,}52$ ms è il secondo pacchetto verso D (E2 arriva a $18{,}5$ ms): è un refuso del testo ufficiale.

Errori comuni

• Usare i byte al posto dei bit in $L/C$: $1250$ byte a $10$ Mbit/s sono $1$ ms, non $0{,}125$ ms.
• Far partire il pacchetto successivo prima che il precedente sia stato ricevuto per intero dal router (si dimentica lo store-and-forward).
• Dimenticare la coda: il tempo di inizio è $\max(t_{pronto},t_{libero})$, non semplicemente $t_{pronto}$.
• Mettere in coda insieme i pacchetti per E e per D in R3: le code sono per interfaccia di uscita.

(Verificato con Python: simulatore a eventi FIFO per interfaccia; E1 $16{,}5$, E2 $18{,}5$, D1 $16{,}36$, D2 $16{,}52$ ms.)