Esercizio - Collegamento di 35 km, stop-and-wait e Go-Back-N con pacchetto perso

Testo. Collegamento punto-punto lungo $d=35$ km, bitrate al PHY $R=34{,}368$ Mbit/s, propagazione ideale ($c=2\cdot10^8$ m/s). Un file di $28\,000$ byte è trasferito tra i due nodi in pacchetti da $280$ byte con intestazione di $40$ byte. Il tempo di elaborazione è trascurabile.

1. Tempo totale di trasferimento (dalla trasmissione del primo bit alla ricezione dell'ultimo) e throughput con ARQ S&W, senza errori.
2. Tempo totale e throughput con ARQ GBN (finestra di trasmissione $N=7$, finestra di ricezione infinita, timeout $t_0=500\ \mu$s), supponendo che il $21$-esimo pacchetto inviato da A si perda.
3. Valore ottimo della finestra $N$ (GBN) per massimizzare il throughput.

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 →; per gli ARQ visti dal lato dei sistemi di comunicazione anche 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

• Payload per pacchetto $I=280\cdot8=2240$ bit; frame $F=(280+40)\cdot8=2560$ bit. Numero di pacchetti: $n=\dfrac{28\,000}{280}=100$.
• Tempo di trasmissione del frame: $t_F=\dfrac{F}{R}=\dfrac{2560}{34{,}368\cdot10^6}=74{,}49\ \mu$s.
• Propagazione: $\tau_p=\dfrac{d}{c}=\dfrac{35\cdot10^3}{2\cdot10^8}=175\ \mu$s.
• ACK trascurabile (nessun dato): $t_A\approx0$; tempo di ciclo $t_G=t_F+2\tau_p=74{,}49+350=424{,}49\ \mu$s.
• Throughput = bit trasmessi sul collegamento (frame, intestazione compresa) per tempo totale; goodput = solo i bit di payload, per tempo totale. Con $n$ pacchetti: $S=nF/T_{tot}$, $S_{good}=nI/T_{tot}$.

Punto 1: stop-and-wait

Si manda un frame e si aspetta l'ACK: un frame ogni $t_G$. L'ultimo frame parte a $(n-1)\,t_G$ e arriva dopo $t_F+\tau_p$: $$T_{tot}=(n-1)\,t_G+t_F+\tau_p=99\cdot424{,}49+74{,}49+175=42\,273{,}8\ \mu\text{s}\approx42{,}274\ \text{ms}.$$ Perché: ogni frame, tranne l'ultimo, occupa un ciclo completo $t_G$ (trasmissione, andata, ritorno dell'ACK) prima che parta il successivo, quindi l'ultimo parte a $(n-1)\,t_G$; per lui basta aspettare $t_F+\tau_p$ (l'ACK finale non serve, il tempo si ferma alla ricezione). Controllo con la teoria: $\rho_{SW}=t_F/t_G=74{,}49/424{,}49=0{,}1755$, cioè a regime $0{,}1755\cdot34{,}368=6{,}03$ Mbit/s, poco meno del valore sotto perché l'ultimo frame non aspetta l'ACK. Throughput: $S=\dfrac{100\cdot2560}{0{,}0422738}=6{,}056$ Mbit/s. Goodput: $S_{good}=\dfrac{100\cdot2240}{0{,}0422738}=5{,}299$ Mbit/s (molto più basso del bitrate perché la finestra è $1$ e $t_G\approx5{,}7\,t_F$).

Punto 2: Go-Back-N con $N=7$ e il $21$-esimo pacchetto perso

Senza errori. Prima di tutto si controlla se la finestra basta per trasmettere in continuo: $N\,t_F=7\cdot74{,}49=521{,}4\ \mu\text{s}\ge t_G=424{,}5\ \mu\text{s}$ ✓ (equivalentemente $N=7\ge t_G/t_F=5{,}70$). Quindi il canale non resta mai vuoto: il tempo senza errori è $n\,t_F+\tau_p=7449+175=7624\ \mu$s $=7{,}624$ ms.

Con la perdita del pacchetto $21$. Il pacchetto $21$ inizia a essere trasmesso a $20\,t_F=1489{,}8\ \mu$s. Il ricevitore ha finestra infinita: accetta e tiene in memoria i pacchetti $22,\dots,27$ che arrivano fuori ordine (non può consegnarli perché manca il $21$), e non invia ACK nuovi per il $21$. Il mittente continua a trasmettere $22,\dots,27$ (la finestra $21$–$27$ si riempie) e si ferma, perché il $28$ non può partire senza l'ACK del $21$.

Il timer del pacchetto $21$, contato dall'inizio della sua trasmissione, scade a $1489{,}8+500=1989{,}8\ \mu$s, mentre il $27$ è ancora in trasmissione (finisce a $27\,t_F=2011{,}2\ \mu$s). Il GBN riparte dal primo pacchetto non confermato: terminata la trasmissione del $27$, A ritrasmette tutta la finestra $21,\dots,27$ ($7$ pacchetti, $521{,}4\ \mu$s). Dopo, la ritrasmissione del $21$ è arrivata a destinazione, il ricevitore ha già in memoria $22$–$27$ e invia un ACK cumulativo fino al $27$ (arriva a $2011{,}2+74{,}5+350=2435{,}7\ \mu$s, prima che la ritrasmissione finisca a $2532{,}6\ \mu$s): la finestra scorre e A prosegue con $28,\dots,100$ senza pause.

Il totale è quindi quello senza errori più la ritrasmissione della finestra: $$T_{tot}=(n+N)\,t_F+\tau_p=107\cdot74{,}49+175=8145\ \mu\text{s}\approx8{,}145\ \text{ms}.$$ Throughput: $S=\dfrac{100\cdot2560}{0{,}0081452}=31{,}43$ Mbit/s; goodput: $\dfrac{100\cdot2240}{0{,}0081452}=27{,}50$ Mbit/s.

Il costo della perdita è $N\,t_F=521\ \mu$s: tutta una finestra ritrasmessa (anche pacchetti già ricevuti bene), il difetto del GBN rispetto al SR.

Punto 3: finestra ottima

Senza errori il throughput è massimo (trasmissione continua) se $N\,t_F\ge t_G$, cioè $$N\ge\frac{t_G}{t_F}=\frac{424{,}49}{74{,}49}=5{,}70\ \Rightarrow\ N_{min}=6.$$ Con $N=5$ il canale sarebbe vuoto un po' ($N\,t_F=372{,}4<424{,}5\ \mu$s: efficienza $0{,}877$); con $N\ge6$ è continuo. Non conviene andare oltre $6$: non si guadagna nulla senza errori e, quando un pacchetto si perde, si ritrasmettono $N$ pacchetti, quindi una finestra più grande costa di più. La finestra ottima è $N=6$. Senza errori l'utilizzazione del GBN è $\rho=\min\{1,\,N\,t_F/t_G\}$ (con $N$ pacchetti in volo il trasmettitore lavora per $N\,t_F$ su un ciclo di $t_G$): cresce linearmente con $N$ e arriva a $1$ per $N=t_G/t_F=5{,}70$; per $N=5$ vale $5\cdot74{,}49/424{,}49=0{,}877$, per $N\ge6$ vale $1$.

Confronto con la soluzione ufficiale

• S&W: $42{,}274$ ms e throughput $6{,}056$ Mbit/s ✓. Goodput: ufficiale $5{,}23$ Mbit/s, ricalcolato $5{,}299\approx5{,}30$ Mbit/s ✗. Il rapporto goodput/throughput deve valere $I/F=280/320=0{,}875$ (come in GBN: $27{,}5/31{,}43$) e $6{,}056\cdot0{,}875=5{,}299$: $5{,}23$ non è coerente con il resto della soluzione, ed è probabilmente un refuso di battitura ($5{,}30$).
• GBN: $8{,}145$ ms ✓; throughput $31{,}43$ Mbit/s ✓ e goodput $27{,}5$ Mbit/s ✓. Questo risultato richiede due ipotesi: finestra di ricezione infinita (il $22$–$27$ non vanno ritrasmessi uno alla volta) e timer contato dall'inizio della trasmissione del pacchetto (se si contasse dalla fine, la scadenza sarebbe a $2064\ \mu$s, A resterebbe fermo $53\ \mu$s e il totale sarebbe $8{,}198$ ms, non il valore ufficiale).
• $N=6$ ✓.

Errori comuni

• Dimenticare l'intestazione: usare $280$ byte (invece di $320$) per $t_F$ dà $65{,}2\ \mu$s, e tutti i valori cambiano.
• Calcolare $n=28\,000/320$ invece di $28\,000/280$: i $28\,000$ byte sono payload.
• Nel GBN ritrasmettere solo il pacchetto $21$: in GBN si ripete tutta la finestra non confermata ($N$ pacchetti).
• Confondere throughput e goodput: il primo conta anche l'intestazione, il secondo no.

(Verificato con Python: $t_F=74{,}488\ \mu$s, $\tau_p=175\ \mu$s, $t_G=424{,}488\ \mu$s; S&W $42{,}2738$ ms, $6{,}0558$ e $5{,}2988$ Mbit/s; GBN: scadenza del timer a $1989{,}8\ \mu$s, fine del pacchetto $27$ a $2011{,}2\ \mu$s, totale $8{,}1452$ ms, $31{,}43$ e $27{,}50$ Mbit/s; $t_G/t_F=5{,}699$, $N=6$.)