Esercizio - Go-Back-N su ogni collegamento con finestre 15 e 6 e confronto con stop-and-wait

Testo. Si trasmette un messaggio di $M=125$ KB, diviso in pacchetti di $L=1250$ byte, dall'host A all'host B attraverso due router in serie: A$-$R1 con $C_1=15$ Mbit/s e $\tau_1=1$ ms, R1$-$R2 con $C_2=20$ Mbit/s e $\tau_2=1$ ms, R2$-$B con $C_3=8$ Mbit/s e $\tau_3=5$ ms.

1. Determinare il tempo totale di trasferimento (dalla trasmissione del primo byte alla ricezione dell'ultimo ACK) se su ogni collegamento si usa GBN con finestra $N=15$ pacchetti. Ritardi di elaborazione e di coda e intestazioni trascurati; anche la dimensione dell'ACK è trascurabile.
2. Ripetere con $N=6$.
3. Ripetere con stop-and-wait su ogni collegamento.

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

• Pacchetti: $K=\dfrac{125\,000}{1250}=100$, ciascuno di $L=1250\ \text{B}=10\,000$ bit.
• Tempi di trasmissione: $$T_1=\frac{10\,000}{15\cdot10^6}=0{,}667\ \text{ms},\quad T_2=\frac{10\,000}{20\cdot10^6}=0{,}5\ \text{ms},\quad T_3=\frac{10\,000}{8\cdot10^6}=1{,}25\ \text{ms}.$$
• Round trip di ogni collegamento (ACK trascurabile): $\text{RTT}_i=T_i+2\tau_i$, cioè $\text{RTT}_1=2{,}667$ ms, $\text{RTT}_2=2{,}5$ ms, $\text{RTT}_3=1{,}25+10=11{,}25$ ms.

Convenzione per "l'ultimo ACK". Si conta fino a quando l'ACK dell'ultimo pacchetto, partito da B, ritorna ad A attraversando i tre collegamenti all'indietro, cioè si aggiunge $\tau_3+\tau_2+\tau_1=7$ ms dopo l'arrivo dell'ultimo pacchetto in B.

Idea generale. Ogni router fa store-and-forward: ritrasmette un pacchetto dopo averlo ricevuto per intero. Il collegamento più lento a regime è quello che detta il ritmo: R2 riceve i pacchetti più in fretta di quanto il collegamento 3 li smaltisca ($T_1,T_2<T_3$), quindi dopo il primo pacchetto ha sempre la coda piena e li trasmette al ritmo del collegamento 3. Il primo pacchetto arriva a R2 dopo $$T_1+\tau_1+T_2+\tau_2=0{,}667+1+0{,}5+1=3{,}167\ \text{ms}.$$

Passo 1: la finestra permette la trasmissione continua?

Per ogni collegamento si controlla $N\,T_i\ge\text{RTT}_i$: se è vero, il mittente non si ferma mai ad aspettare l'ACK e il collegamento trasmette un pacchetto dopo l'altro.

(1) $N=15$: trasmissione continua ovunque

Il collegamento 3 trasmette gli $100$ pacchetti uno dopo l'altro, senza pause, a partire da $3{,}167$ ms: $100\,T_3=125$ ms. L'ultimo bit arriva a B dopo altri $\tau_3=5$ ms, e l'ultimo ACK torna ad A dopo $7$ ms: $$T_{tot}=\left(T_1+\tau_1+T_2+\tau_2\right)+K\,T_3+\tau_3+(\tau_3+\tau_2+\tau_1)=3{,}167+125+5+7=\mathbf{140{,}17\ ms}.$$

(2) $N=6$: finestra insufficiente sul collegamento 3

Sui collegamenti 1 e 2 la trasmissione resta continua, ma sul 3 no: $6\cdot1{,}25=7{,}5<11{,}25$ ms. Dopo $6$ pacchetti (che occupano $7{,}5$ ms) il collegamento 3 deve aspettare il ritorno dell'ACK del primo pacchetto della finestra, che arriva dopo $\text{RTT}_3=11{,}25$ ms dalla sua partenza. Quindi il collegamento 3 lavora a finestre da $6$ pacchetti, una ogni $\text{RTT}_3$:

• $\lfloor100/6\rfloor=16$ finestre complete, di durata $16\cdot11{,}25=180$ ms;
• l'ultima finestra ha $100-16\cdot6=4$ pacchetti: $4T_3=5$ ms di trasmissione, poi $\tau_3=5$ ms di propagazione fino a B (non si aspetta altro per i dati);
• infine l'ultimo ACK: $7$ ms.

$$T_{tot}=3{,}167+16\,\text{RTT}_3+4T_3+\tau_3+(\tau_3+\tau_2+\tau_1)=3{,}167+180+5+5+7=\mathbf{200{,}17\ ms}.$$

(3) Stop-and-wait su ogni collegamento

Con $N=1$ il collegamento 3 invia un pacchetto per $\text{RTT}_3=11{,}25$ ms (i collegamenti 1 e 2 hanno RTT molto più corto e quindi riforniscono R2 più velocemente). Dopo l'arrivo del primo pacchetto a R2 servono $99$ cicli completi, poi l'ultimo pacchetto viene trasmesso e propagato, e infine ritorna l'ACK: $$T_{tot}=3{,}167+(K-1)\,\text{RTT}_3+T_3+\tau_3+(\tau_3+\tau_2+\tau_1)=3{,}167+99\cdot11{,}25+1{,}25+5+7=\mathbf{1130{,}17\ ms}.$$

La finestra minima per non perdere tempo sul collegamento 3 è $N\ge\text{RTT}_3/T_3=11{,}25/1{,}25=9$ pacchetti (il prodotto banda-ritardo del collegamento, in pacchetti): $N=15$ è sopra, $N=6$ sotto.

Il grafico riporta $T(N)$ per ogni finestra $N$ (stessa regola: $\lceil100/N\rceil$ finestre sul collegamento 3 e l'ultima più corta): per $N=1$ è lo stop-and-wait ($1130{,}17$ ms), per $N=6$ vale $200{,}17$ ms, e da $N=9$ in poi il tempo non scende più sotto $140{,}17$ ms.

Confronto con la soluzione ufficiale

Ufficiale: $140{,}16$ ms, $200{,}16$ ms, $1130{,}16$ ms. Coincidono, anche con la formula del testo e con una simulazione a eventi dei tre ARQ per collegamento. La differenza di $0{,}01$ ms (l'ufficiale riporta $.16$, il valore esatto è $.1667$) è un troncamento invece di un arrotondamento: $T_1=0{,}6667$ ms ripetuto.

Errori comuni

• Applicare la formula "$N$ pacchetti per $\text{RTT}$" a tutti i collegamenti: va controllata la condizione di trasmissione continua link per link, e conta quello più lento.
• Trascurare i tempi di trasmissione sui collegamenti 1 e 2 prima che il primo pacchetto arrivi a R2 (i $3{,}167$ ms iniziali).
• Dimenticare il ritorno dell'ultimo ACK ($7$ ms), che qui è richiesto, oppure aggiungere un $\text{RTT}_3$ intero invece del solo viaggio di ritorno $\tau_3+\tau_2+\tau_1$.
• Contare $17$ finestre (anziché $16$ complete più una da $4$) o dimenticare che l'ultima non dura un RTT intero.

(Verificato con Python: simulazione per collegamento: $N=15\to140{,}1667$, $N=6\to200{,}1667$, $N=1\to1130{,}1667$ ms.)