Esercizio - TCP con perdita di finestra e riduzione di rwnd

Testo. Si trasferiscono $39{,}5$ kB con TCP. Parametri: $\text{MSS}=500$ byte, $\text{RTT}=500$ ms, timeout $T_1=2\cdot\text{RTT}$. Condizioni iniziali: $\text{rwnd}=12$ kB, $\text{ssthresh}=8$ kB, $\text{cwnd}=500$ B. Inoltre: al tempo $3$ s tutti i segmenti in volo vengono persi; al tempo $4{,}5$ s il ricevitore imposta $\text{rwnd}=2$ kB.

1. Disegnare l'andamento nel tempo di $\text{cwnd}$, $\text{ssthresh}$ e $\text{rwnd}$.
2. Calcolare il tempo di trasferimento.

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 →.

Dati in segmenti

Conviene contare in segmenti da $\text{MSS}=500$ B (con $1$ kB $=1000$ B):

• messaggio: $39\,500/500=79$ segmenti;
• $\text{rwnd}=12$ kB $=24$ segmenti, poi $2$ kB $=4$ segmenti;
• $\text{ssthresh}=8$ kB $=16$ segmenti; $\text{cwnd}$ iniziale $1$;
• timeout $T_1=2\,\text{RTT}=1$ s.

Convenzione. L'esercizio dà soltanto il RTT, non separa tempo di trasmissione e propagazione: i tempi di trasmissione sono trascurabili, e il tempo $0$ è l'istante in cui parte la prima finestra (l'apertura non viene contata; il risultato ufficiale, $8{,}5$ s $=17\,\text{RTT}$, lo conferma). Ogni finestra inizia un RTT dopo la precedente: a $t=0$, $0{,}5$ s, $1$ s, $\dots$ (spiegazione completa in Esercizio - TCP, slow start e messaggio da 18 kB su un collegamento da 8 Mbps).

Fase prima della perdita

Slow start fino a $\text{ssthresh}=16$ ($1,2,4,8,16$), poi congestion avoidance ($+1$ per round).

$\text{rwnd}=24$ non limita mai ($\text{cwnd}\le18$). Consegnati con successo prima della perdita: $1+2+4+8+16+17=48$ segmenti (lo slow start dà $1+2+4+8+16=31=2^5-1$, la somma geometrica1 + 2 + 4 + ... + 2^k = 2^(k+1) − 1, perché ogni termine è il doppio del precedenteSerie notevoli - geometrica, telescopica, armonica →, e a questi si aggiunge la finestra da $17$). I $18$ segmenti inviati a $3$ s (dal $49$ al $66$) sono persi, nessun ACK torna.

Il timeout

Il temporizzatore parte quando si invia la finestra persa, a $t=3$ s, e scade dopo $T_1=1$ s: a $t=4$ s. Alla scadenza (evento grave, come un time-out in Tahoe/Reno): $$\text{ssthresh}=\frac{\text{cwnd}}2=\frac{18}2=9,\qquad\text{cwnd}=1.$$ Si riparte in slow start dal primo segmento non confermato (il $49$). Il valore $18$ è la finestra in volo al momento della perdita: $\text{ssthresh}=9$ è lo stesso sia con $\text{cwnd}/2$ sia con "segmenti in volo / 2".

Dopo il timeout, con la riduzione di $\text{rwnd}$

Restano $79-48=31$ segmenti ($79$ è il totale, i $48$ già consegnati non si ripetono; i $18$ persi sì). $\text{swnd}=\min(\text{cwnd},\text{rwnd})$ (rwnd $=2$ kB $=2000/500=4$ segmenti dal tempo $4{,}5$ s).

Da $t=5$ s (sette finestre da $4$) la finestra di invio è dettata dal ricevitore: anche se $\text{cwnd}$ continua a crescere (con $\text{ssthresh}=9$: $8$ poi $9,10,\dots$), si spediscono solo $4$ segmenti per round. Il tempo non dipende da come cresce $\text{cwnd}$ oltre $4$.

L'ultima finestra (gli ultimi $4$ segmenti) parte a $8{,}0$ s; l'ACK torna un RTT dopo, a $8{,}5$ s.

Riepilogo del tempo

$$T_{tot}=\underbrace{6\,\text{RTT}}_{3\ \text{s: prime 6 finestre}}+\underbrace{T_1}_{1\ \text{s}}+\underbrace{2\,\text{RTT}}_{\text{finestre da }1\text{ e }2}+\underbrace{7\,\text{RTT}}_{7\text{ finestre da }4\text{, ultima con il suo ACK}}=3+1+1+3{,}5=\boxed{8{,}5\ \text{s}}.$$ Si vede che il tempo, rispetto a una trasmissione senza perdita, è aumentato di $T_1$ (attesa del timeout) più i round persi a riconquistare la finestra.

(Verificato con Python con un simulatore a eventi: $8{,}500$ s; le sequenze delle finestre coincidono con le tabelle.)

Confronto con la soluzione ufficiale

Le slide danno $T_{tot}=T_{setup}+6\,\text{RTT}+T_{out}+2\,\text{RTT}+7\,\text{RTT}+(4-1)T_b=8{,}5$ s (con $T_{setup}$ e $T_b$ nulli), $\text{ssthresh}=18/2=9$ dopo la perdita e $\text{swnd}=\text{rwnd}=4$ dal tempo $4{,}5$ s: tutto coincide. L'unica cosa lasciata implicita è che il tempo $0$ è l'inizio della prima finestra.

Errori comuni

• Non considerare che a $\text{cwnd}=16=\text{ssthresh}$ si passa a crescita lineare ($17,18$, non $32$).
• Calcolare $\text{ssthresh}=16/2=8$ o $17/2$: la finestra che era in volo alla perdita è $18$.
• Dimenticare che la finestra persa va ritrasmessa: i segmenti $49$-$66$ contano di nuovo.
• Usare $\text{cwnd}$ al posto di $\min(\text{cwnd},\text{rwnd})$ dopo $4{,}5$ s: la finestra effettiva resta $4$.