Esercizio - Go-Back-N end-to-end su tre collegamenti

Testo. Si trasmette un messaggio di $M=135$ KB, diviso in pacchetti di $L=1500$ byte, dall'host A all'host B attraverso due router in serie: A$-$R1 con $C_1=2{,}4$ Mbit/s e $\tau_1=5$ ms, R1$-$R2 con $C_2=20$ Mbit/s e $\tau_2=3$ ms, R2$-$B con $C_3=24$ Mbit/s e $\tau_3=2$ ms.

1. Determinare il tempo totale di trasferimento (dalla trasmissione del primo byte alla ricezione dell'ultimo byte) se si usa GBN con finestra $N=4$ eseguito end-to-end a livello DLL. Ritardi di elaborazione e di coda e intestazioni trascurati; anche gli ACK hanno dimensione trascurabile.
2. Ripetere il calcolo contando il tempo fino alla ricezione dell'ultimo ACK.
3. Ripetere con $N=6$.

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 →, 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

• Numero di pacchetti: $K=\dfrac{135\,000}{1500}=90$, ciascuno di $L=1500\ \text{B}=12\,000$ bit.
• Tempi di trasmissione: $$T_1=\frac{12\,000}{2{,}4\cdot10^6}=5\ \text{ms},\quad T_2=\frac{12\,000}{20\cdot10^6}=0{,}6\ \text{ms},\quad T_3=\frac{12\,000}{24\cdot10^6}=0{,}5\ \text{ms}.$$
• Propagazioni: $\tau_1=5$, $\tau_2=3$, $\tau_3=2$ ms.

Collo di bottiglia. È il collegamento con il tempo di trasmissione più lungo: il collegamento 1 ($T_1=5$ ms, contro $0{,}6$ e $0{,}5$ ms). Gli altri due sono molto più veloci, quindi i pacchetti non si accumulano nei router: $T_2,T_3<T_1$ vuol dire che ogni pacchetto trova libero il collegamento successivo.

Che cos'è GBN end-to-end. La finestra $N$ conta i pacchetti inviati da A e non ancora confermati da B (ACK di B che torna ad A attraverso tutta la rete). Il tempo di andata e ritorno è quindi quello dell'intero percorso: $$\text{RTT}_{e2e}=T_1+\tau_1+T_2+\tau_2+T_3+\tau_3+\underbrace{\tau_3+\tau_2+\tau_1}_{\text{ritorno ACK}}=5+5+0{,}6+3+0{,}5+2+2+3+5=26{,}1\ \text{ms}.$$

Passo 1: la trasmissione è continua?

Il mittente non deve mai fermarsi se l'ACK del primo pacchetto di una finestra arriva prima che il mittente abbia finito di inviarla: $N\,T_{b}\ge\text{RTT}_{e2e}$, con $T_b=T_1$ il tempo di trasmissione del collo di bottiglia.

• $N=4$: $4\cdot5=20<26{,}1$ ms: no. A invia $4$ pacchetti (in $20$ ms), poi resta fermo per i $6{,}1$ ms restanti prima che arrivi il primo ACK. Si lavora a finestre, una ogni $\text{RTT}_{e2e}$.
• $N=6$: $6\cdot5=30\ge26{,}1$ ms: sì. Il primo ACK torna mentre A sta ancora trasmettendo la finestra: GBN si comporta come se non ci fosse alcun ARQ.

(1) $N=4$, fino all'ultimo byte

Con $K=90$: $\lfloor90/4\rfloor=22$ finestre complete (88 pacchetti); l'ultima ha $90-88=2$ pacchetti. Le $22$ finestre complete durano $22\cdot26{,}1=574{,}2$ ms. Nell'ultima finestra non si attende alcun ACK: il pacchetto 90 parte dopo $2T_1$ dall'inizio della finestra, e poi attraversa i tre collegamenti ($\tau_1+T_2+\tau_2+T_3+\tau_3$):

$$T_{tot}=22\,\text{RTT}_{e2e}+2T_1+\tau_1+T_2+\tau_2+T_3+\tau_3=574{,}2+10+5+0{,}6+3+0{,}5+2=\mathbf{595{,}3\ ms}.$$

(2) $N=4$, fino all'ultimo ACK

Basta aggiungere il ritorno dell'ultimo ACK, $\tau_3+\tau_2+\tau_1=10$ ms: $$T_{tot}=595{,}3+10=\mathbf{605{,}3\ ms}.$$ (Equivalente: $22\,\text{RTT}_{e2e}+\text{RTT}_{e2e}+T_1$, perché l'ultima finestra termina quando torna l'ACK del primo dei suoi due pacchetti più il tempo $T_1$ del secondo: $574{,}2+26{,}1+5=605{,}3$.)

(3) $N=6$

La trasmissione è continua: A invia i $90$ pacchetti uno dopo l'altro, ognuno occupando $T_1=5$ ms, per $90\cdot5=450$ ms; poi l'ultimo pacchetto attraversa i tre collegamenti. Non servono finestre: $$T_{tot}=K\,T_1+\tau_1+T_2+\tau_2+T_3+\tau_3=450+5+0{,}6+3+0{,}5+2=\mathbf{461{,}1\ ms}\quad(\text{ultimo byte}),$$ $$T_{tot}=461{,}1+10=\mathbf{471{,}1\ ms}\quad(\text{ultimo ACK}).$$

La finestra minima per la trasmissione continua è $N\ge\lceil\text{RTT}_{e2e}/T_1\rceil=\lceil26{,}1/5\rceil=\lceil5{,}22\rceil=6$ (si arrotonda per eccesso: con $N=5$, $5\cdot5=25<26{,}1$, restano $1{,}1$ ms di pausa a ogni giro): con $N=6$ si ottiene il tempo minimo possibile ($K\,T_1$ più la propagazione); con $N=4$ si perdono $134$ ms in attese ($595{,}3-461{,}1$).

Il grafico mostra $T(N)$ per ogni finestra (con la stessa regola, $\lceil90/N\rceil$ finestre, l'ultima più corta): scende velocemente finché $N<6$ e poi si ferma al minimo $461{,}1$ ms. Aumentare $N$ oltre $6$ non serve.

Confronto con la soluzione ufficiale

Ufficiale: $595{,}3$, $605{,}3$ e $461{,}1$ ms (con ultimo ACK per $N=6$: $471{,}1$ ms). Coincidono tutti, anche confrontando con una simulazione a eventi del GBN end-to-end senza perdite.

Errori comuni

• Usare per la continuità il bitrate medio o il collegamento più veloce: conta il collo di bottiglia, qui il collegamento 1.
• Calcolare $\text{RTT}_{e2e}$ senza i tre tempi di trasmissione ($T_1+T_2+T_3=6{,}1$ ms): si otterrebbe $20$ ms e $N=4$ sembrerebbe sufficiente, ma $4\cdot5=20<26{,}1$.
• Contare $23$ finestre da $4$: $90=22\cdot4+2$, l'ultima ne ha solo due e non dura un RTT intero.
• Per $N=6$ usare ancora le finestre: l'ACK torna in tempo e la trasmissione è continua.

(Verificato con Python: $\text{RTT}_{e2e}=26{,}1$ ms; simulazione GBN end-to-end: $N=4\to595{,}3$ (con ACK $605{,}3$), $N=6\to461{,}1$ ($471{,}1$) ms.)