Esercizio - TCP con finestra del ricevitore di 4 segmenti su tre collegamenti

Testo. Catena $A\to R_1\to R_2\to B$ con collegamenti bidirezionali, stessa capacità nei due versi, $C_1\le C_2\le C_3$ e ritardi di propagazione $\tau_1,\tau_2,\tau_3$. Tra $A$ e $B$ c'è una connessione TCP con $\text{MSS}=250$ B, già a regime. Si supponga $\text{rwnd}$ minore di $\text{cwnd}$ e pari a $4$ MSS, quindi $\text{swnd}=\text{rwnd}$.

1. Calcolare il tempo totale (dall'invio del primo segmento alla ricezione dell'ultimo ACK) per trasferire un flusso di $13\,000$ byte prodotto dall'applicazione, con intestazioni IP $H_{IP}$, TCP $H_{TCP}$ e di collegamento $H_{LL}$, nessun errore, nessun traffico concorrente, ACK di lunghezza trascurabile.
2. Quanto deve valere $\text{swnd}$ perché il flusso di segmenti sul collegamento 1 sia continuo?

Teoria usata: 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 →, 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 →, 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 →.

Modello e simboli

Il TCP a regime con finestra fissa $w=\text{swnd}$ si comporta come un protocollo a finestra scorrevole (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 →): il mittente può avere al massimo $w$ segmenti non confermati; ogni ACK che torna fa partire un segmento nuovo.

• Ogni segmento ha lunghezza $L=\text{MSS}+H_{IP}+H_{TCP}+H_{LL}$ (i dati sono $250$ byte, il resto è intestazione).
• Il tempo di trasmissione sul collegamento $i$ è $T_i=L/C_i$; poiché $C_1\le C_2\le C_3$, il collegamento 1 è il collo di bottiglia: $T_1\ge T_2\ge T_3$. I segmenti, uscendo da $A$ a distanza $T_1$ l'uno dall'altro, non si accodano mai nei router.
• RTT del primo segmento, con ACK trascurabili: va in avanti attraversando i tre collegamenti (trasmissione + propagazione), l'ACK torna solo con la propagazione: $$\text{RTT}=\frac L{C_1}+\frac L{C_2}+\frac L{C_3}+2(\tau_1+\tau_2+\tau_3)\ (=T\text{ nelle slide}).$$
• Numero di segmenti: $13\,000/250=52$.

(1) Tempo totale

Il comportamento dipende dal confronto tra il tempo $w\,T_1$ che serve per inviare l'intera finestra e il RTT, cioè il tempo prima che torni il primo ACK.

Caso $w\,T_1<\text{RTT}$ (finestra più corta del "tubo", cioè $swnd\cdot L<\text{RTT}\cdot C_1$). Il mittente invia i $4$ segmenti, poi resta fermo finché non torna l'ACK del primo. Ogni finestra dura quindi esattamente un RTT: la finestra $k$ ($k=0,1,\dots$) inizia a $k\cdot\text{RTT}$. Le finestre sono $52/4=13$. L'ultima parte a $12\,\text{RTT}$; il suo ultimo segmento esce dopo altri $3T_1$ ed il relativo ACK torna un RTT dopo l'inizio della sua trasmissione: $$T_{tot}=12\,\text{RTT}+3T_1+\text{RTT}=\boxed{13\,\text{RTT}+3\frac L{C_1}}.$$

Caso $w\,T_1\ge\text{RTT}$. Quando il primo ACK ritorna, il mittente sta ancora trasmettendo la finestra: non si ferma mai e il collegamento 1 resta occupato continuamente. Il segmento $52$ comincia dopo $51T_1$ e il suo ACK torna un RTT dopo: $$T_{tot}=\boxed{51\frac L{C_1}+\text{RTT}}.$$

Le due formule coincidono sulla soglia $4T_1=\text{RTT}$: $13\,\text{RTT}+3T_1=52T_1+3T_1=55T_1$ e $51T_1+\text{RTT}=55T_1$.

(2) Finestra minima per il flusso continuo

Serve $w\,T_1\ge\text{RTT}$, cioè $w\ge C_1\,\text{RTT}/L$: la finestra deve contenere almeno il prodotto banda-ritardo (bandwidth-delay product, BDP) del collegamento 1 espresso in segmenti, e poiché $w$ è intero: $$\boxed{w_{min}=\left\lceil\frac{C_1}L\left(\frac L{C_1}+2\tau_1+\frac L{C_2}+2\tau_2+\frac L{C_3}+2\tau_3\right)\right\rceil=\lceil \text{RTT}/T_1\rceil}.$$ (Nelle slide il RTT è scritto come $\frac L{C_1}+2\tau_1+\dots$, che è la stessa somma.)

Esempio numerico (verificato)

Scelgo $H_{IP}=20$, $H_{TCP}=20$, $H_{LL}=10$ byte, quindi $L=300$ B $=2400$ bit; $C_1=1$, $C_2=2$, $C_3=4$ Mbit/s; $\tau_1=\tau_2=\tau_3=1$ ms.

• $T_1=2{,}4$ ms, $T_2=1{,}2$ ms, $T_3=0{,}6$ ms; $\text{RTT}=2{,}4+1{,}2+0{,}6+2\cdot3=10{,}2$ ms.
• $w\,T_1=4\cdot2{,}4=9{,}6<10{,}2$: finestra corta, flusso non continuo: $$T_{tot}=13\cdot10{,}2+3\cdot2{,}4=132{,}6+7{,}2=139{,}8\ \text{ms}.$$
• $w_{min}=\lceil10{,}2/2{,}4\rceil=\lceil4{,}25\rceil=5$. Con $\text{swnd}=5$ il tempo scenderebbe a $51\cdot2{,}4+10{,}2=132{,}6$ ms.
• Con ritardi più piccoli, $\tau=0{,}2$ ms: $\text{RTT}=2{,}4+1{,}2+0{,}6+1{,}2=5{,}4$ ms e $4\cdot2{,}4=9{,}6\ge5{,}4$, flusso continuo: $T_{tot}=51\cdot2{,}4+5{,}4=127{,}8$ ms.

Un simulatore a eventi (collegamenti in serie store-and-forward, ACK cumulativi) dà $139{,}8$ ms e $127{,}8$ ms, uguali alle formule.

Il grafico mostra $T(w)$ per tutte le finestre, con la regola «una finestra ogni RTT se $w\,T_1<\text{RTT}$, flusso continuo altrimenti»: per $w=1$ (stop-and-wait) il tempo è $530{,}4$ ms, con $w=4$ vale $139{,}8$ ms e da $w_{min}=5$ in poi resta $132{,}6$ ms, perché la finestra copre già il prodotto banda-ritardo.

Confronto con la soluzione ufficiale

Le slide scrivono $T_{tot}=\frac{52}4T+(4-1)\frac L{C_1}=13T+3L/C_1$ con $T=\text{RTT}$, e $51L/C_1+T$ per il caso continuo: identiche alle formule trovate. Per la parte (2) danno $w=\frac{C_1}L\cdot\text{RTT}$ senza arrotondare: va preso l'intero superiore.

Errori comuni

• Usare la formula del caso continuo quando $4T_1<\text{RTT}$ (sottovalutando il tempo): si controlla sempre prima $w\,T_1$ contro il RTT.
• Contare nel RTT la trasmissione degli ACK: sono trascurabili, tornano con la sola propagazione.
• Dimenticare che la formula $13\,\text{RTT}+3T_1$ vale se il collegamento 1 è il più lento (qui garantito da $C_1\le C_2\le C_3$); altrimenti i segmenti si accodano in $R_1$.
• Non arrotondare per eccesso la finestra minima.