Esercizio - Go-Back-N su un collegamento e stop-and-wait sull'altro, messaggio da 300 KB

Testo. Si trasmette un messaggio di $M=300$ KB, diviso in pacchetti di $L=1500$ byte, dall'host A all'host B. A e B sono collegati da due collegamenti in serie tramite un nodo intermedio R: il primo ha $C_1=24$ Mbit/s e $t_1=4$ ms di propagazione, il secondo $C_2=48$ Mbit/s e $t_2=2$ ms.

1. Determinare il tempo totale di trasferimento (dalla trasmissione del primo byte in A alla ricezione dell'ultimo byte in B) se sul primo collegamento si esegue GBN con finestra $N=3$ pacchetti e sul secondo si esegue stop-and-wait. Ritardi di elaborazione e di coda trascurati.
2. Ripetere il calcolo se invece GBN con $N=3$ è eseguito end-to-end sui due collegamenti e il 2° pacchetto è perso sul primo collegamento. Si consideri il timeout minimo possibile per GBN.

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 →, 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 →, Livello di collegamento e framingIl livello di collegamento (DLL) consegna un frame da un nodo a un nodo adiacente su un collegamento. Servizi: framing, accesso al mezzo (MAC) con indirizzi MAC a 48 bit, controllo di flusso, rilevazione e correzione degli errori. Si divide in DLC (framing, controllo di errore e di flusso) e MAC (accesso al mezzo condiviso). Il framing delimita i frame con un flag: nei protocolli a byte (flag di 8 bit, ESC) si usa il byte stuffing, in quelli a bit (flag 01111110) il bit stuffing, che inserisce uno 0 dopo ogni cinque 1 consecutivi.Livello di collegamento e framing →, 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 e grandezze di base

• Numero di pacchetti: $K=\dfrac{300\,000\ \text{B}}{1500\ \text{B}}=200$.
• Lunghezza di un pacchetto: $L=1500\ \text{B}=12\,000$ bit.
• Tempi di trasmissione: $T_1=\dfrac{12\,000}{24\cdot10^6}=0{,}5$ ms, $T_2=\dfrac{12\,000}{48\cdot10^6}=0{,}25$ ms.
• Propagazioni: $\tau_1=4$ ms, $\tau_2=2$ ms.
• Gli ACK sono trascurabili (dimensione non data): il loro unico effetto è il ritardo di propagazione.

Modello. Tempi di coda trascurati significa che R ha una memoria sufficiente e inoltra i pacchetti nell'ordine di arrivo (store-and-forward): inizia a ritrasmettere un pacchetto solo quando lo ha ricevuto per intero. Su ciascun collegamento l'ARQ regola quante volte il mittente può inviare nuovi pacchetti.

(1) GBN ($N=3$) sul collegamento 1, stop-and-wait sul collegamento 2

Chi è il collo di bottiglia?

Non basta guardare i bitrate ($C_1<C_2$ suggerirebbe il primo collegamento): conta quanti pacchetti al secondo ciascun collegamento riesce davvero a far passare con il suo ARQ.

• Collegamento 1 (GBN, $N=3$). Il $\text{RTT}$ del collegamento è $\text{RTT}_1=T_1+2\tau_1=0{,}5+8=8{,}5$ ms. La trasmissione continua (finestra sempre piena) richiederebbe $N T_1\ge\text{RTT}_1$, cioè $3\cdot0{,}5=1{,}5\ge8{,}5$: falso. Dunque il mittente trasmette $3$ pacchetti e poi attende l'ACK: $3$ pacchetti ogni $8{,}5$ ms, cioè $0{,}353$ pacchetti/ms.
• Collegamento 2 (stop-and-wait). Un pacchetto per ogni $\text{RTT}_2=T_2+2\tau_2=0{,}25+4=4{,}25$ ms, cioè $3$ pacchetti ogni $3\cdot4{,}25=12{,}75$ ms, ossia $0{,}235$ pacchetti/ms.

Il collegamento 2 è più lento ($12{,}75>8{,}5$ ms per $3$ pacchetti), nonostante il bitrate doppio: il suo stop-and-wait lo spreca quasi tutto in attesa. Il collo di bottiglia è il secondo collegamento, a causa dell'ARQ. Il primo collegamento consegna i pacchetti a R più in fretta di quanto R riesca a smaltirli, quindi si forma una coda in R e il secondo collegamento non resta mai a corto di pacchetti.

Tempo totale

Il primo pacchetto arriva a R dopo $T_1+\tau_1=4{,}5$ ms. Da quel momento il collegamento 2 lavora a cicli da $\text{RTT}_2$, uno per pacchetto: il pacchetto $k$ inizia sul collegamento 2 all'istante $T_1+\tau_1+(k-1)\,\text{RTT}_2$. L'ultimo ($k=K$) viene poi trasmesso ($T_2$) e propagato ($\tau_2$), e non serve aspettare il suo ACK:

$$T_{tot}=T_1+\tau_1+(K-1)\,\text{RTT}_2+T_2+\tau_2=0{,}5+4+199\cdot4{,}25+0{,}25+2=\mathbf{852{,}5\ ms}.$$

Verifica che la coda non si svuoti: l'ultimo pacchetto arriva a R, col ritmo del collegamento 1, intorno ai $566$ ms, mentre il collegamento 2 lo trasmette a $850{,}25$ ms: R ha sempre pacchetti pronti, quindi la formula vale.

(2) GBN con $N=3$ end-to-end, 2° pacchetto perso

Ora la finestra di $3$ pacchetti si applica all'intero percorso: un pacchetto viene considerato confermato solo quando il suo ACK ritorna da B ad A.

Si ha trasmissione continua?

Il collo di bottiglia ora è semplicemente il collegamento con il tempo di trasmissione più lungo, il primo ($T_1=0{,}5>T_2=0{,}25$). Il $\text{RTT}$ end-to-end è $$\text{RTT}_{e2e}=T_1+\tau_1+T_2+\tau_2+\tau_2+\tau_1=0{,}5+4+0{,}25+2+2+4=12{,}75\ \text{ms}.$$ Trasmissione continua se $N\,T_1\ge\text{RTT}_{e2e}$: $3\cdot0{,}5=1{,}5\ge12{,}75$ è falso. Quindi il mittente invia $3$ pacchetti, poi resta fermo ad aspettare: si lavora a finestre, una ogni $\text{RTT}_{e2e}=12{,}75$ ms (il primo ACK arriva dopo un $\text{RTT}$ e riapre la finestra).

Senza perdite

Con $K=200$ e finestre da $3$: $\lfloor200/3\rfloor=66$ finestre complete; l'ultima contiene $200-66\cdot3=2$ pacchetti. Le $66$ finestre complete durano $66\,\text{RTT}_{e2e}$. L'ultima finestra non attende l'ACK: il secondo pacchetto parte dopo $T_1$ (il primo è trasmesso per primo), quindi l'ultimo pacchetto arriva a B dopo $2T_1+\tau_1+T_2+\tau_2$:

$$T_{tot,noloss}=66\cdot12{,}75+\left(2\cdot0{,}5+4+0{,}25+2\right)=841{,}5+7{,}25=\mathbf{848{,}75\ ms}.$$

Con la perdita del 2° pacchetto

Cosa succede, istante per istante:

Da $13{,}25$ ms in poi servono ancora i pacchetti da $2$ a $200$, cioè $199$ pacchetti: $66$ finestre complete da $3$ più un pacchetto. Quindi $$T_{tot,loss}=\underbrace{0{,}5+12{,}75}_{=13{,}25}+66\cdot12{,}75+\underbrace{T_1+\tau_1+T_2+\tau_2}_{6{,}75}=13{,}25+841{,}5+6{,}75=\mathbf{861{,}5\ ms}.$$

È esattamente il caso senza perdite più un timeout: $848{,}75+12{,}75=861{,}5$ ms. Il timeout minimo è $\text{RTT}_{e2e}$ perché l'ACK del pacchetto $2$ non può tornare prima di un ciclo completo dall'inizio della sua trasmissione: aspettare meno farebbe ritrasmettere pacchetti ancora in viaggio.

Quanto conta la finestra? Il grafico mostra $T(N)$ senza perdite con $N=3$ (valore dell'esercizio, $848{,}75$ ms) e con finestre più grandi. Per avere trasmissione continua servirebbe $N\ge\lceil12{,}75/0{,}5\rceil=26$ pacchetti, e il tempo scenderebbe a $K\,T_1+\tau_1+T_2+\tau_2=100+6{,}25=106{,}25$ ms: con $N=3$ il collegamento 1 lavora $3\cdot0{,}5/12{,}75=11{,}8\,\%$ del tempo.

Confronto con la soluzione ufficiale

• (1) Ufficiale: $852{,}5$ ms. Coincide, con la stessa formula $T_1+\tau_1+(K-1)\text{RTT}_2+T_2+\tau_2$.
• (2) Ufficiale: $848{,}75$ ms senza perdite, $861{,}5$ ms con perdita (timeout uguale all'RTT). Coincide, anche confrontando con una simulazione a eventi del GBN end-to-end (stessi tre valori).

Errori comuni

• Dire che il collo di bottiglia è il collegamento 1 perché $C_1<C_2$: con lo stop-and-wait sul 2 conta il throughput di ARQ, non il bitrate.
• Aggiungere il tempo dell'ultimo ACK: il testo chiede fino alla ricezione dell'ultimo byte in B.
• Contare $67$ finestre senza notare che l'ultima ne ha solo $2$ (o $1$ nel caso con perdita): l'ultima finestra non dura un $\text{RTT}$ intero.
• Calcolare il $\text{RTT}_{e2e}$ senza i due tempi di trasmissione $T_1$ e $T_2$ (qui $12{,}75$ ms e non $12$ ms).

(Verificato con Python: simulazione a eventi: $852{,}5$ ms; $848{,}75$ ms; $861{,}5$ ms.)