Esercizio - Due collegamenti da 10 e 2 Gbps, 1000 pacchetti con S&W e GBN

Testo. Due host comunicano tramite uno switch, su una catena di due collegamenti con $R_1=10$ Gbit/s, $R_2=2$ Gbit/s e propagazioni $\tau_1=100\ \mu$s, $\tau_2=10\ \mu$s. Lo switch fa commutazione di pacchetto a datagramma (store-and-forward), senza ritardo di elaborazione. Un file è diviso in $1000$ pacchetti da $10$ kbit ($1000$ bit di intestazione e $9000$ di payload). Calcolare il tempo totale di trasferimento (dalla trasmissione del primo bit alla ricezione dell'ultimo) quando:

1. S&W su ciascun collegamento (nessun errore);
2. S&W end-to-end (nessun errore);
3. GBN su ciascun collegamento, con la finestra minima che garantisce trasmissione continua, e i pacchetti $1$, $2$ e $1000$ sono corrotti sul tratto da A allo switch.

Teoria usata: Protocolli ARQ - Stop-and-Wait, Go-Back-N e Selective RepeatARQ (Automatic Repeat reQuest) rende affidabile un collegamento che sbaglia: il ricevitore conferma (ACK) i frame ricevuti bene, il trasmettitore ritrasmette allo scadere del timeout. Servono timeout (contro il deadlock) e numeri di sequenza (contro i duplicati). Con $t_G=t_F+2\tau_p+t_A$ e probabilità di errore $p$: Stop-and-Wait $\rho=\frac{t_F(1-p)}{t_G}$; Go-Back-N con finestra $N\ge t_G/t_F$ $\rho=\frac{1-p}{1+(N-1)p}$; Selective Repeat $\rho=1-p$. Efficienza $\eta=\rho,I/F$. La finestra ottima è la capacità del tubo in pacchetti. In Selective Repeat esiste anche una lunghezza ottima del frame: con overhead $o$ e probabilità di errore sul bit $P_b$, $x_{ott}\simeq\frac o2+\sqrt{o/P_b}$ (frame più corti se il canale sbaglia di più).Protocolli ARQ - Stop-and-Wait, Go-Back-N e Selective Repeat →, 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 →; Tecniche ARQ - stop-and-wait, go-back-N e selective repeatL'ARQ (automatic repeat request) usa un codice che rivela gli errori e fa ritrasmettere i pacchetti sbagliati, con conferme ACK/NACK. Con $p=1-(1-P_{bit})^L$ la probabilità che un pacchetto sia errato, $t_P$ il tempo di pacchetto, $t_A$ quello dell'ACK e $\tau_P$ il ritardo di propagazione: stop-and-wait $S=\frac{t_P(1-p)}{t_P+t_A+2\tau_P}$; go-back-N $S=\frac{(1-p),t_P}{1+(N-1)p}$ con $N-1=\left\lceil\frac{2\tau_P}{t_P+t_A}\right\rceil$; selective repeat $S=(1-p)\frac{t_P}{t_P+t_A}$. Il numero medio di trasmissioni di un pacchetto è $\frac1{1-p}$.Tecniche ARQ - stop-and-wait, go-back-N e selective repeat →.

Dati

• $F=10\,000$ bit per pacchetto (l'intestazione fa parte del pacchetto che viaggia), $K=1000$.
• $T_1=\dfrac{F}{R_1}=\dfrac{10^4}{10^{10}}=1\ \mu$s; $T_2=\dfrac{F}{R_2}=\dfrac{10^4}{2\cdot10^9}=5\ \mu$s.
• $\tau_1=100\ \mu$s, $\tau_2=10\ \mu$s.
• ACK di dimensione trascurabile (conta solo la propagazione di ritorno).
• Tempi di ciclo: $RTT_1=T_1+2\tau_1=201\ \mu$s; $RTT_2=T_2+2\tau_2=25\ \mu$s.

Caso 1: S&W su ciascun collegamento

Su ogni collegamento si manda un pacchetto e si aspetta il suo ACK. A è vincolato dal ciclo più lungo, $RTT_1=201\ \mu$s $>RTT_2=25\ \mu$s: lo switch smaltisce un pacchetto ogni $25\ \mu$s, ben prima che A ne mandi uno nuovo (ogni $201\ \mu$s). Il ritmo è $1$ pacchetto ogni $RTT_1$; l'ultimo pacchetto parte a $(K-1)\,RTT_1$ e poi fa i due salti: $$T_{tot}=(K-1)\,RTT_1+T_1+\tau_1+T_2+\tau_2=999\cdot201+1+100+5+10=200\,915\ \mu\text{s}=200{,}915\ \text{ms}.$$ Controllo: l'utilizzazione dello stop-and-wait sul collegamento 1 è $\rho=T_1/RTT_1=1/201$, quindi $K\,T_1/\rho=1000\cdot201\ \mu\text{s}=201$ ms, circa il risultato (la differenza è l'ultimo ciclo che non aspetta l'ACK). Il collegamento 1 trasmette per $1/201$ del tempo: ha $10$ Gbit/s di bitrate, ma un solo pacchetto da $10$ kbit ogni $201\ \mu$s, cioè $49{,}75$ Mbit/s.

Caso 2: S&W end-to-end

Un solo pacchetto in rete: il ciclo comprende l'andata su entrambi i collegamenti e il ritorno dell'ACK da B ad A: $$RTT_{e2e}=T_1+\tau_1+T_2+\tau_2+\tau_2+\tau_1=1+100+5+10+10+100=226\ \mu\text{s}.$$ $$T_{tot}=(K-1)\,RTT_{e2e}+T_1+\tau_1+T_2+\tau_2=999\cdot226+116=225\,890\ \mu\text{s}=225{,}890\ \text{ms}.$$

Caso 3: GBN su ogni collegamento, con tre pacchetti corrotti

Finestra minima per trasmissione continua. Serve $N\ge t_G/t_F$, cioè $N\ge RTT/T$ (ACK trascurabile):

• collegamento 1: $N_1=\left\lceil\dfrac{201}{1}\right\rceil=201$ pacchetti;
• collegamento 2: $N_2=\dfrac{25}{5}=5$ pacchetti.

Il collegamento 2 è il più lento ($T_2=5>T_1=1$): è il collo di bottiglia, anche senza errori, perché lo switch non può emettere più di un pacchetto ogni $5\ \mu$s. Senza errori il tempo sarebbe $T_1+\tau_1+K\,T_2+\tau_2=1+100+5000+10=5111\ \mu$s.

Con gli errori. Gli errori sono solo sul collegamento 1 (A → switch). Ipotesi coerenti con la teoria GBN: ricevitore con finestra $M=1$ (scarta tutto ciò che non è il pacchetto atteso); il timeout è il minimo possibile, cioè $RTT_1=201\ \mu$s, contato dall'inizio della trasmissione del pacchetto.

1. A trasmette i pacchetti $1,2,\dots,201$ a ritmo continuo ($1\ \mu$s ciascuno) e la finestra si riempie. I pacchetti $1$ e $2$ sono corrotti; lo switch li scarta, e scarta anche $3,\dots,201$ perché non sono quelli attesi. Nessun ACK arriva.
2. Il timer del pacchetto $1$ scade a $201\ \mu$s, proprio quando A ha finito di trasmettere la finestra: A ricomincia dal pacchetto $1$ e trasmette in modo continuo $1,2,\dots,1000$ (ora corretti, salvo il $1000$). Il pacchetto $j$ finisce di essere ricevuto dallo switch a $201+(j-1)+1+100=301+j\ \mu$s. In particolare il pacchetto $1$ è completamente ricevuto a $302\ \mu$s.
3. Il pacchetto $1000$ è corrotto alla sua prima trasmissione (parte a $1200\ \mu$s): il timer scade a $1200+201=1401\ \mu$s, lo si ritrasmette e arriva allo switch a $1401+1+100=1502\ \mu$s.
4. Lo switch inoltra sul collegamento 2 un pacchetto ogni $5\ \mu$s, a partire da $302\ \mu$s: il pacchetto $j$ finisce di uscire a $302+5j\ \mu$s. Il pacchetto $1000$ ha bisogno di uscire a $5302-5=5297\ \mu$s, ma è già nello switch dal $1502\ \mu$s: la sua ritrasmissione non ritarda nulla, perché la coda dello switch non si è ancora svuotata.

Quindi l'unico costo degli errori è il ritardo con cui parte la sequenza corretta: $$T_{tot}=RTT_1+T_1+\tau_1+K\,T_2+\tau_2=201+1+100+5000+10=5312\ \mu\text{s}=5{,}312\ \text{ms}.$$ (Cioè $5111+201$: gli errori sui pacchetti $1$ e $2$ costano un $RTT_1$, quelli sul pacchetto $1000$ nulla.)

Confronto con la soluzione ufficiale

Ufficiale: $200{,}915$ ms, $225{,}890$ ms, $5{,}312$ ms. Coincide in tutti e tre i casi. Per il terzo caso la soluzione ufficiale dà solo il risultato: il modello ricostruito qui (timeout $=RTT_1$ contato dall'inizio della trasmissione, collo di bottiglia sul collegamento 2) lo riproduce esattamente; il valore $5{,}312$ è $5{,}111$ ms (senza errori) più un $RTT_1$.

Errori comuni

• Usare i $9000$ bit di payload al posto dei $10\,000$ bit del pacchetto nei tempi di trasmissione: sul collegamento viaggia tutta la PDU.
• Nel GBN scegliere la finestra con il solo $RTT_2$ (finestra $5$) anche sul collegamento 1, dove serve $201$: con $N=5$ A trasmetterebbe a ritmo molto più basso.
• Ritrasmettere solo il pacchetto $1$ (stile Selective Repeat) invece di tutta la finestra: in GBN si torna indietro e si riparte da lì.
• Aggiungere al totale anche il ritardo del pacchetto $1000$: la sua ritrasmissione cade mentre lo switch sta ancora smaltendo la coda.

(Verificato con Python: $T_1=1\ \mu$s, $T_2=5\ \mu$s, $RTT_1=201\ \mu$s; $200{,}915$ ms, $225{,}890$ ms; simulatore GBN con timeout $201\ \mu$s: pacchetto $1$ ricevuto a $302\ \mu$s, ultimo pacchetto fuori dallo switch a $5{,}312$ ms.)