Esercizio - TCP e stop-and-wait su tre collegamenti, messaggio da 100 kB

Testo. Una connessione TCP è stabilita tra il server $A$ e l'host $B$ (si trascura ogni altro traffico) attraverso $A\to R_1\to R_2\to B$ con $C_1=20$ Mbit/s, $\tau_1=6$ ms; $C_2=10$ Mbit/s, $\tau_2=4$ ms; $C_3=2$ Mbit/s, $\tau_3=10$ ms. $\text{MSS}=1250$ byte, segmenti di apertura e ACK di lunghezza trascurabile, come le intestazioni di tutti i livelli; $\text{cwnd}$ iniziale $=1250$ B, $\text{ssthresh}=10$ kB, $\text{rwnd}=1$ MB.

1. Trovare il RTT e il valore della finestra $\text{swnd}^*$ che permette un flusso continuo di segmenti tra $A$ e $B$.
2. Calcolare il tempo totale di trasferimento di un messaggio di $M=100$ kB (dall'apertura della connessione alla ricezione dell'ultimo ACK), con i dati che partono il prima possibile.
3. Ripetere il calcolo supponendo che, invece di TCP, sul livello di collegamento di ciascun collegamento si usi l'ARQ stop-and-wait.

Teoria usata: TCP - controllo di congestioneLa congestione nasce quando collegamenti veloci alimentano un collegamento lento: le code dei router si riempiono, i pacchetti si perdono o ritardano e, nel caso peggiore, la rete collassa (quasi solo ritrasmissioni). TCP controlla la propria finestra di congestione cwnd con il feedback delle perdite (timeout o tre ACK duplicati): slow start (cwnd raddoppia a ogni RTT) fino alla soglia ssthresh, poi congestion avoidance (+1 MSS per RTT); a ogni perdita ssthresh = W/2. Le varianti si distinguono per come reagiscono ai tre dupACK: Tahoe riparte da cwnd = 1 dopo la ritrasmissione rapida; Reno usa il fast recovery (ssthresh = cwnd/2, cwnd = ssthresh + 3, +1 per ogni altro dupACK); NewReno gestisce gli ACK parziali e recupera più perdite nella stessa finestra; SACK riscontra i blocchi ricevuti e ritrasmette solo quello che manca.TCP - controllo di congestione →, TCP - connessione, affidabilità e controllo di flussoTCP (Transmission Control Protocol) è il protocollo di trasporto con connessione e affidabile: trasforma il servizio senza connessione e inaffidabile di IP in un flusso di byte ordinato, senza errori né duplicati. La connessione si apre con l'handshake a tre vie (SYN, SYN+ACK, ACK) e si chiude con tre o quattro segmenti (FIN). I byte sono numerati: il numero di sequenza è quello del primo byte del segmento, il numero di ACK (cumulativo) è il prossimo byte atteso. Il mittente può inviare $\min(\text{rwnd},\text{cwnd})$ byte non ancora confermati; rwnd (finestra del ricevitore, in un campo di 16 bit) è il controllo di flusso. L'errore si gestisce con checksum, ACK, timeout di ritrasmissione (RTO) e ritrasmissione rapida dopo tre ACK duplicati. Per usare tutto il canale la finestra deve valere almeno il prodotto banda-ritardo (BDP); il throughput massimo è $\text{MSS}\cdot W_{\max}/\text{RTT}$.TCP - connessione, affidabilità e controllo di flusso →, 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 →, 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 →. Convenzione di calcolo (apertura a $2\tau$, round a distanza di un RTT, flusso continuo): vedi Esercizio - TCP, slow start e messaggio da 18 kB su un collegamento da 8 Mbps.

Dati

$\text{MSS}=1250\cdot8=10\,000$ bit. Tempi di trasmissione: $T_1=10\,000/(20\cdot10^6)=0{,}5$ ms, $T_2=1$ ms, $T_3=5$ ms. Il collegamento 3 è il collo di bottiglia ($2$ Mbit/s). $\sum\tau=6+4+10=20$ ms. Segmenti: $100\,000/1250=80$. $\text{ssthresh}=10\,000/1250=8$ segmenti.

(1) RTT e finestra per il flusso continuo

Un segmento attraversa i tre collegamenti (trasmissione e propagazione su ciascuno), l'ACK torna con le sole propagazioni: $$\text{RTT}=T_1+T_2+T_3+2\sum\tau=0{,}5+1+5+40=\boxed{46{,}5\ \text{ms}}.$$ Il flusso è continuo se, quando torna il primo ACK, la finestra è ancora in trasmissione sul collo di bottiglia: $\text{swnd}^*\cdot T_3\ge\text{RTT}$: $$\text{swnd}^*\ge\frac{46{,}5}{5}=\boxed{9{,}3\ \text{segmenti}}\ \Rightarrow\ 10\ \text{segmenti interi}.$$ (Equivale a dire che la finestra deve contenere il prodotto banda-ritardo del cammino, $2\cdot10^6\cdot0{,}0465=93\,000$ bit $=9{,}3$ segmenti.)

(2) TCP: tempo totale

Apertura: $2\sum\tau=40$ ms. Finestre: slow start $1,2,4,8$ (si ferma a $\text{ssthresh}=8$), poi avoidance $9,10,\dots$

I primi cinque round portano $1+2+4+8+9=24$ segmenti ($1+2+4+8=15$ è una somma geometrica1 + 2 + 4 + ... + 2^k = 2^(k+1) − 1, perché ogni termine è il doppio del precedenteSerie notevoli - geometrica, telescopica, armonica →; poi la crescita lineare $+1$ a round). Dal sesto round la finestra supera $9{,}3$ e il collegamento 3 non si ferma più: restano $80-24=56$ segmenti, uno ogni $T_3=5$ ms a partire da $272{,}5$ ms. L'ultimo inizia dopo $55\cdot5=275$ ms, a $547{,}5$ ms, e l'ACK torna un RTT dopo: $$T_{TCP}=T_{setup}+5\,\text{RTT}+(56-1)T_3+\text{RTT}=40+232{,}5+275+46{,}5=\boxed{594\ \text{ms}}.$$ Lettura dei termini: $40$ ms l'apertura; $5\,\text{RTT}$ i primi cinque round; $55\,T_3$ la distanza tra il primo e l'ultimo dei $56$ segmenti; $\text{RTT}$ l'ultimo ACK.

(3) Stop-and-wait su ogni collegamento

Qui non c'è finestra TCP: ogni collegamento ha il proprio ARQ stop-and-wait (trasmetto un pacchetto, aspetto il suo ACK, solo allora trasmetto il successivo, 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 →). Ogni collegamento $i$ può quindi emettere un pacchetto ogni $$\text{RTT}_i=T_i+2\tau_i:\qquad \text{RTT}_1=0{,}5+12=12{,}5\ \text{ms},\ \text{RTT}_2=1+8=9\ \text{ms},\ \text{RTT}_3=5+20=25\ \text{ms}.$$ Il più lento è il collegamento 3: il ritmo del trasferimento è un pacchetto ogni $\text{RTT}_3=25$ ms, mentre gli altri due collegamenti sono più veloci e i pacchetti si accodano in $R_2$ (buffer supposti sufficienti).

Il primo pacchetto arriva davanti al collegamento 3 a $T_1+\tau_1+T_2+\tau_2=11{,}5$ ms e da lì i pacchetti partono ogni $25$ ms: l'ultimo ($K=80$) parte a $11{,}5+79\cdot25=1986{,}5$ ms, viene trasmesso in $5$ ms, si propaga $10$ ms e arriva a $B$ a $2001{,}5$ ms; l'ACK ripercorre i tre collegamenti in $\tau_3+\tau_2+\tau_1=20$ ms. In formula, come per il TCP si arriva fino all'ultimo ACK: $$T_{S\&W}=(K-1)\,\text{RTT}_3+\text{RTT}=79\cdot25+46{,}5=\boxed{2021{,}5\ \text{ms}}.$$ Con la finestra TCP lo stesso trasferimento richiede $594$ ms: lo stop-and-wait tiene il collo di bottiglia occupato per soli $5$ ms ogni $25$.

(Verificato con Python: simulatore a eventi per il TCP, $594{,}0$ ms; simulazione per-collegamento dello stop-and-wait con ACK trascurabili, consegna a $B$ a $2001{,}5$ ms e ultimo ACK in $A$ a $2021{,}5$ ms.)

Confronto con la soluzione ufficiale

Le slide danno $\text{swnd}^*\ge9{,}3$ MSS, $T_{TCP}=T_{setup}+5\,\text{RTT}+(56-1)T_3+\text{RTT}=594$ ms (con "$80-(1+2+4+8+9)=56$ segmenti inviati in modo continuo") e $T_{S\&W}=(K-1)\text{RTT}_3+\text{RTT}=2021{,}5$ ms: tutto coincide. Osservazione: nello stop-and-wait per collegamento l'ACK finale non arriva davvero fino ad $A$ (ogni collegamento ha i propri ACK); il risultato ufficiale conta comunque il ritorno dell'ultimo ACK lungo i tre collegamenti ($20$ ms) per omogeneità con il caso TCP. Se si volesse il tempo di consegna a $B$ sarebbe $2001{,}5$ ms.

Errori comuni

• Calcolare $\text{swnd}^*$ con il tempo di trasmissione sul collegamento 1 ($0{,}5$ ms) invece che sul collo di bottiglia ($5$ ms): la soglia sarebbe $93$ segmenti, sbagliata.
• Dopo la soglia continua, contare ancora un RTT per finestra: i segmenti rimasti escono uno ogni $T_3$.
• Nello stop-and-wait usare $\text{RTT}$ dell'intero cammino come passo tra i pacchetti: il passo è il ciclo del collegamento più lento, $T_3+2\tau_3=25$ ms.
• Fermare la crescita a $10$ segmenti pensando a $\text{ssthresh}=10$ kB: $10$ kB sono $8$ segmenti.