Esercizio - RTT e swnd, TCP da 100 KB e stop-and-wait su ogni collegamento

Testo (tema d'esame, sessione di settembre, esercizio 1). Rete a commutazione di pacchetto a datagramma (store-and-forward), code indipendenti per ogni interfaccia di uscita.

La domanda 1 (arrivo di quattro pacchetti da A verso E e D con lunghezze diverse) è in Esercizio - Quattro pacchetti da A verso E e D in una rete store-and-forward. Qui le altre tre. Tra il server A e l'host B c'è una connessione TCP ($\text{MSS}=1250$ B, apertura e ACK trascurabili, intestazioni trascurabili, $\text{cwnd}=1250$ B, $\text{ssthresh}=10$ KB, $\text{rwnd}=1$ MB).

2. RTT e valore della finestra di invio $\text{swnd}^*$ che permette un flusso continuo tra A e B.
3. Tempo totale per trasferire $M=100$ KB (dall'apertura all'ultimo ACK), con i dati che partono appena possibile.
4. Lo stesso, ma usando al posto di TCP lo stop-and-wait a livello di collegamento su ogni collegamento.

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 →, 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 →, 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 lo stop-and-wait 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 →.

Domanda 2: RTT e $\text{swnd}^*$

Il cammino A→B usa $C_1,C_2,C_3$. Con $\text{MSS}=1250$ B $=10$ kbit i tempi di trasmissione sono $T_1=0{,}5$ ms, $T_2=1$ ms, $T_3=5$ ms. Il collo di bottiglia è $C_3$ ($2$ Mbit/s): $T_b=5$ ms.

• Andata: $T_1+\tau_1+T_2+\tau_2+T_3+\tau_3=0{,}5+6+1+4+5+10=26{,}5$ ms.
• Ritorno dell'ACK: $\tau_3+\tau_2+\tau_1=10+4+6=20$ ms.

$$\text{RTT}=46{,}5\ \text{ms},\qquad\text{swnd}^*\ge\frac{\text{RTT}}{T_b}=\frac{46{,}5}{5}=9{,}3\ \Rightarrow\ \text{swnd}^*=\mathbf{10\ \text{MSS}}.$$

(Poiché $\text{rwnd}=1$ MB è enorme, $\text{swnd}=\text{cwnd}$.) Perché si divide per $T_b$ e si arrotonda per eccesso: in un RTT il collo di bottiglia riesce a trasmettere $\text{RTT}/T_b=9{,}3$ segmenti, quindi per tenerlo sempre occupato ne servono almeno $9{,}3$ in volo; la finestra è un numero intero di segmenti e con $9$ il collegamento resterebbe fermo $0{,}3\cdot5=1{,}5$ ms a ogni giro.

Domanda 3: $100$ KB con TCP

$K=100\,000/1250=80$ segmenti; $\text{ssthresh}=10\,000/1250=8$ MSS. Apertura: SYN e SYN+ACK valgono $20$ ms ciascuno ($\tau_1+\tau_2+\tau_3$), i dati partono a $40$ ms.

Finestre: $1,2,4,8$ (slow start fino a ssthresh), poi $9$ (congestion avoidance); alla sesta finestra $10=\text{swnd}^*$: flusso continuo.

Inviati $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 →, più $9$); rimangono $80-24=56$, spediti a ritmo $T_b=5$ ms:

$$T_{\text{TCP}}=40+5\,\text{RTT}+(56-1)\,T_b+\text{RTT}=40+232{,}5+275+46{,}5=\mathbf{594\ \text{ms}}.$$

Lettura dei termini: $40$ ms l'apertura ($2\cdot20$ ms di propagazione); $5\,\text{RTT}$ le cinque finestre non continue ($1,2,4,8,9$, tutte sotto $9{,}3$); $(56-1)\,T_b$ il flusso continuo; $\text{RTT}$ l'ultimo ACK.

Domanda 4: stop-and-wait su ogni collegamento

Su ogni collegamento ogni nodo spedisce un pacchetto e aspetta l'ACK del collegamento prima del successivo. Il tempo per pacchetto di un collegamento è $T+2\tau$ (trasmissione, andata, ritorno dell'ACK trascurabile):

Il più lento è $C_3$: un pacchetto ogni $25$ ms. Gli altri due, più veloci, lasciano i pacchetti in coda in R2: il flusso è dettato da $C_3$.

• Il primo pacchetto arriva a R2 dopo $T_1+\tau_1+T_2+\tau_2=0{,}5+6+1+4=11{,}5$ ms.
• $C_3$ parte con il pacchetto $k$ ($k=0,\dots,79$) a $11{,}5+25k$ ms; l'ultimo parte a $11{,}5+79\cdot25=1986{,}5$ ms.
• Arriva a B dopo $T_3+\tau_3=15$ ms: $2001{,}5$ ms. Il suo ACK torna a R2 dopo altri $\tau_3=10$ ms: $2011{,}5$ ms.
• La soluzione ufficiale conta fino all'ACK ricevuto in A, cioè altri $\tau_2+\tau_1=4+6=10$ ms di ritorno sul cammino:

$$T=11{,}5+80\cdot25+10=\mathbf{2021{,}5\ \text{ms}}.$$

(Qui non c'è apertura di connessione: lo stop-and-wait è un protocollo di collegamento.) Il primo termine ($11{,}5$ ms) è il tempo per portare il primo pacchetto a R2; $80\cdot25$ ms sono gli $80$ cicli di $C_3$ (l'ultimo ciclo comprende la trasmissione, la propagazione e l'ACK); $10$ ms è l'ultimo tratto dell'ACK verso A.

Confronto con la soluzione ufficiale

Coincide. Nota sulla domanda 4: la convenzione "ultimo ACK fino ad A" aggiunge $10$ ms rispetto all'ACK dell'ultimo collegamento ($2011{,}5$ ms) e $20$ ms rispetto alla ricezione dell'ultimo pacchetto in B ($2001{,}5$ ms). Nel testo non si distingue: si segue la soluzione ufficiale.

Errori comuni

• Usare per il collo di bottiglia del stop-and-wait il tempo di trasmissione $T_3=5$ ms invece di $T_3+2\tau_3=25$ ms: lo stop-and-wait paga l'attesa dell'ACK a ogni pacchetto.
• Prendere $\text{swnd}^*=9$ (arrotondando $9{,}3$ per difetto): per un flusso continuo si arrotonda per eccesso.
• In TCP, non fermare la crescita a $\text{ssthresh}=8$ per passare in congestion avoidance.
• Sommare i $\text{RTT}$ dei tre collegamenti ($12{,}5+9+25$): la coda in R2 e R1 assorbe i collegamenti più veloci, conta solo il più lento.

(Verificato con Python: simulatore TCP a finestra intera ($594$ ms) e simulazione dello stop-and-wait per collegamento ($2001{,}5$ ms alla destinazione, $2021{,}5$ ms con il ritorno fino ad A).)