TCP - controllo di congestione

Che cos'è la congestione

Si ha congestione quando il carico offerto alla rete supera la sua capacità. Nasce perché i router e i commutatori hanno code: un router ha una coda di ingresso e una di uscita per ogni interfaccia, e se non riesce a elaborare i pacchetti alla velocità con cui arrivano le code si riempiono. Esempio tipico: due sorgenti $S_1$ e $S_2$ collegate da link da $100$ Mbit/s a un router che le inoltra su un collegamento da $10$ Mbit/s: i collegamenti veloci alimentano uno lento.

Conseguenze:

• se le code traboccano, i pacchetti sono scartati;
• i pacchetti in coda subiscono ritardo (che cresce rapidamente quando la utilizzazione del collegamento si avvicina a $1$: Introduzione alla teoria delle codeUn sistema a coda (QS) è fatto da un processo di arrivi (di Poisson, tasso $\lambda$), una coda e uno o più servitori con tasso di servizio $\mu$. Carico offerto $G=\lambda/\mu$, fattore di carico $\rho=\lambda/(m\mu)$: il sistema è stabile solo se $\rho<1$, e allora il throughput è $\lambda$ (altrimenti è $m\mu$). Legge di Little: $E[x]=\lambda E[s]$, valida per qualsiasi disciplina. Coda M/M/1: $E[x]=\frac{\rho}{1-\rho}$, $E[s]=\frac{1/\mu}{1-\rho}$, $E[w]=\frac{\rho/\mu}{1-\rho}$. Con servizio deterministico (M/D/1, caso particolare di Pollaczek-Khinchin): $E[w]=\frac{\rho}{2\mu(1-\rho)}$. Il ritardo cresce senza limite quando $\rho\to1$.Introduzione alla teoria delle code → e Sistemi a coda - processo di Poisson, M/M/1 e formula di LittleUn sistema a coda ha arrivi (di pacchetti, file) e un servitore (il collegamento). Con arrivi di Poisson di intensità $\lambda$ e tempi di servizio esponenziali di media $\frac1\mu$ (coda M/M/1) e $\rho=\frac\lambda\mu<1$: $P[N=n]=(1-\rho)\rho^n$, numero medio nel sistema $\bar N=\frac\rho{1-\rho}$, tempo medio di permanenza $\bar W=\frac1{\mu-\lambda}$, attesa in coda $\bar W_q=\frac\rho{\mu-\lambda}$. La formula di Little $\bar N=\lambda\bar W$ vale in generale. Con buffer finito (M/M/1/K) i pacchetti sono persi con $P_K=\frac{(1-\rho)\rho^K}{1-\rho^{K+1}}$.Sistemi a coda - processo di Poisson, M/M/1 e formula di Little →);
• i flussi che attraversano il collegamento congestionato hanno throughput scadente;
• può arrivare il collasso di rete: i flussi inviano finestre intere ma progrediscono pochissimo, e la maggior parte dei pacchetti in rete sono ritrasmissioni. Altra causa di collasso: sorgenti non controllate dal feedback (come un flusso UDP, Protocollo UDPUDP (User Datagram Protocol) è il protocollo di trasporto senza connessione e inaffidabile: rispetto a IP aggiunge soltanto la comunicazione processo-processo (numeri di porta) e un controllo d'errore facoltativo. L'intestazione è di soli 8 byte (porta sorgente, porta destinazione, lunghezza, checksum). Il checksum copre pseudo-intestazione (indirizzi IP, protocollo 17, lunghezza), intestazione e dati, ed è il complemento a uno della somma a 16 bit; se vale 0 significa "non calcolato", e un risultato 0 si trasmette come 0xFFFF. UDP non ha connessione, numeri di sequenza, controllo di flusso, di errore né di congestione: si sceglie per i messaggi brevi (DNS, DHCP, RIP, SNMP) e per le applicazioni in tempo reale, dove conta non aggiungere ritardo.Protocollo UDP →).

Il collasso non è solo teoria: è stato osservato più volte in reti reali.

Ginocchio e precipizio; efficienza ed equità

Se si disegna il throughput in funzione del carico offerto, la curva sale linearmente, poi si appiattisce nel ginocchio (knee): da lì in poi più carico dà solo più ritardo. Più avanti c'è il precipizio (cliff): oltre, il throughput crolla (collasso).

• Evitare la congestione (congestion avoidance) significa operare vicino al ginocchio: si rallenta se si sa che più avanti c'è un precipizio.
• Controllare la congestione (congestion control) significa operare al precipizio e rallentare quando si nota un calo di capacità (la perdita di un pacchetto è un'indicazione).

Requisiti: usare le risorse in modo efficiente (massimo throughput senza ritardi eccessivi: il ginocchio), distribuirle in modo equo (fair) e prevenire o evitare il collasso. Senza conoscere i requisiti dei flussi, equo significa dividere in parti uguali.

Formula (indice di equità di Jain). Per $N$ flussi con rate $x_1,\dots,x_N$: $$\text{FI}=\frac{\left(\sum_{i=1}^{N}x_i\right)^2}{N\sum_{i=1}^{N}x_i^2},\qquad \frac1N\le\text{FI}\le1.$$ Vale $1$ se tutti hanno lo stesso rate, $1/N$ se uno solo usa tutto.

Perché i limiti: indicando con $\mu=\frac1N\sum x_i$ la media dei rate e con $\sigma^2=\frac1N\sum x_i^2-\mu^2$ la loro varianzaI momenti E[X^k] e i momenti centrati E[(X − μ)^k] descrivono la forma di una legge; la varianza Var(X) = E[(X − μ)²] = E[X²] − E[X]² misura quanto X si disperde attorno alla media, vale Var(aX + b) = a² Var(X) e Var(X) = 0 solo se X è costante.Varianza e momenti → (sempre $\ge0$), si ha $\sum x_i=N\mu$ e $\sum x_i^2=N(\sigma^2+\mu^2)$, quindi $\text{FI}=\frac{N^2\mu^2}{N\cdot N(\sigma^2+\mu^2)}=\frac{\mu^2}{\sigma^2+\mu^2}\le1$, con uguale solo se $\sigma=0$ (rate tutti uguali). Se uno solo usa tutto, $x=(R,0,\dots,0)$: $\text{FI}=R^2/(N R^2)=1/N$.

Esempio. Tre flussi su un link da $30$ Mbit/s. Divisione $(10,10,10)$: $\text{FI}=30^2/(3\cdot300)=1$. Divisione $(18,1,1)$: $\text{FI}=20^2/(3\cdot326)=400/978=0{,}409$. Divisione $(8,6,4)$: $\text{FI}=18^2/(3\cdot116)=324/348=0{,}931$.

L'idea di TCP

TCP sonda il canale per trovare il punto appena prima del precipizio (la "capienza del tubo") e rallenta quando lo supera. È un protocollo a finestra: in ogni RTT si possono inviare al più $W$ pacchetti non riscontrati. Adattare $W$ significa adattare il ritmo di immissione di pacchetti nella rete.

Le variabili del mittente:

• cwnd (congestion window): la finestra decisa dal mittente in base al feedback della rete, in segmenti (MSS) o byte;
• rwnd: la finestra annunciata dal ricevente, per il controllo di flusso (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 →);
• ssthresh (slow start threshold): una stima corrente della capacità disponibile, mantenuta per ogni connessione.

Formula (finestra effettiva). $W=\min(\text{cwnd},\text{rwnd})$.

Esempio. Con $\text{ssthresh}=4$ MSS e $\text{rwnd}=6$ MSS: $W=\min(1,6)=1$, poi $2$, $4$ (si raggiunge ssthresh), $5$, $6$ (si raggiunge rwnd: da lì $W$ resta $6$ anche se cwnd continua a crescere: $\min(6,7)=6$).

Slow start e congestion avoidance

Slow start (SS, "partenza lenta", esponenziale) e congestion avoidance (CA, "evitamento della congestione", lineare) sono algoritmi con obiettivi diversi implementati insieme:

• SS: alla partenza della connessione e dopo un timeout controlla la fase iniziale di trasmissione: si parte piano ma si cresce in fretta, per arrivare presto a un buon throughput. Il nome inganna: la crescita è esponenziale.
• CA: quando si è raggiunta la capacità del collegamento, controlla la trasmissione crescendo lentamente per non causare congestione.

Si parte con $\text{cwnd}=1$ MSS e $\text{ssthresh}=W_{\max}$ (un valore molto grande, o prefissato).

Formula (regole per ogni ACK nuovo).

• se $\text{cwnd}\le\text{ssthresh}$ (SS): $\text{cwnd}\leftarrow\text{cwnd}+1$;
• se $\text{cwnd}>\text{ssthresh}$ (CA): $\text{cwnd}\leftarrow\text{cwnd}+\dfrac1{\text{cwnd}}$.

Conseguenza per RTT: in SS $\text{cwnd}$ raddoppia a ogni RTT (un ACK per ogni segmento: $+1$ per ACK vale $+W$ per round); in CA aumenta di 1 MSS per RTT (arrivano $W$ ACK, ciascuno vale $1/W$).

Il conto: in un round il mittente invia $W$ segmenti e riceve $W$ ACK. In SS ogni ACK somma $1$: $W+W\cdot1=2W$. In CA ogni ACK somma $1/W$: $W+W\cdot\frac1W=W+1$. Per questo la crescita in SS è esponenziale ($W=2^i$ dopo $i$ round) e in CA è lineare ($W=W_0+i$).

Esempio. Partendo da $\text{cwnd}=1$ con $\text{ssthresh}=8$: round $0$: $1$; round $1$: $2$; round $2$: $4$; round $3$: $8$; da qui $9$, $10$, $11$, $\dots$. Nel round $i\le3$ la finestra vale $W_i=2^i$ e sono stati inviati $2^{i+1}-1$ segmenti in tutto ($1+2+4+8=15$ dopo il round $3$): è la somma di una progressione geometricaLe serie di cui si conosce il carattere e da usare come termine di paragone: geometrica (converge a 1/(1-q) se |q|<1), telescopiche (somma b_1 - lim b_n, come Mengoli), armonica generalizzata (1/n^alpha converge se e solo se alpha>1).Serie notevoli - geometrica, telescopica, armonica → di ragione $2$, $\sum_{k=0}^{i}2^k=\frac{2^{i+1}-1}{2-1}$. Viceversa, per arrivare a una finestra $W$ in SS servono $\log_2W$ round (Esponenziale e logaritmoLa funzione esponenziale a^x (base positiva diversa da 1) e la sua inversa, il logaritmo in base a, con grafici e proprietà.Esponenziale e logaritmo →): da $1$ a $8$ sono $\log_28=3$ round.

Alcune precisazioni:

• Nello slow start la finestra cresce di 1 per ogni ACK; quindi di quanti ACK arrivano nel round, cioè quanti segmenti sono stati riscontrati. In CA la crescita è di 1 per round, indipendentemente dal numero di ACK. L'esempio delle slide suppone che gli ACK non siano ritardati.
• Con gli ACK ritardati (un ACK ogni $b=2$ segmenti) in SS la finestra cresce di un fattore $1+1/b=1{,}5$ per round, in CA di $1/b$ MSS per round: è il motivo per cui $b$ compare nel modello analitico (Modello analitico del tasso di invio di TCPIl modello analitico del corso calcola il tasso di invio a regime B (segmenti al secondo) di un flusso TCP Reno in funzione della probabilità di perdita p, dell'RTT, del parametro di ACK ritardato b e del timeout T0. Il tempo è diviso in round di durata RTT; il ciclo della finestra tra due perdite segnalate da tre dupACK (TDP) ha media E[W] = (2-3b)/(3b) + sqrt(((3b-2)/(3b))^2 + 8(1-p)/(3bp)) e il tasso è B = E[Y]/E[A] (pacchetti inviati diviso durata di un TDP). Per p piccolo si ottiene la formula della radice quadrata B = (1/RTT) sqrt(3/(2bp)) (circa 1,22/(RTT sqrt p) per b = 1 e 0,87/(RTT sqrt p) per b = 2). Con i timeout si aggiungono la probabilità Q che una perdita finisca in timeout, E[R] = 1/(1-p) pacchetti e E[Z^TO] = T0 f(p)/(1-p) secondi di attesa: B = (E[Y] + Q E[R])/(E[A] + Q E[Z^TO]). Con la finestra massima Wmax il tasso non supera Wmax/RTT.Modello analitico del tasso di invio di TCP →). Il conto: in un round con $W$ segmenti arrivano $W/b$ ACK; in SS ciascuno somma $1$, quindi $W+W/b=W(1+1/b)$; in CA ciascuno somma $1/W$, quindi $W+\frac Wb\cdot\frac1W=W+\frac1b$.
• Dopo un timeout lo slow start riparte e continua fino a metà della finestra a cui avvenne la congestione, che è la nuova ssthresh.

Convenzione per i calcoli in round. Negli esercizi del corso, a ogni RTT: se $\text{cwnd}<\text{ssthresh}$ si passa a $\min(2\,\text{cwnd},\text{ssthresh})$; se $\text{cwnd}\ge\text{ssthresh}$ si aggiunge $1$. La finestra di invio effettiva è sempre $\min(\text{cwnd},\text{rwnd})$.

Esercizi: Esercizio - TCP, slow start e messaggio da 18 kB su un collegamento da 8 Mbps, Esercizio - TCP, slow start e 120 segmenti su un collegamento da 32 Mbps, Esercizio - TCP con perdita di finestra e riduzione di rwnd, Esercizio - UDP e TCP su tre collegamenti, messaggio da 225 kB, Esercizio - TCP e stop-and-wait su tre collegamenti, messaggio da 100 kB.

Come TCP scopre le perdite

• Timeout di ritrasmissione (RTO). Il mittente ha un timer per connessione (non per pacchetto). Se l'ACK dell'ultimo pacchetto temporizzato non arriva prima che scada, il pacchetto è considerato perso. L'RTO si calcola dinamicamente: Stima del timeout di ritrasmissione (RTO)TCP ritrasmette un segmento se il suo ACK non arriva entro il timeout di ritrasmissione (RTO), che deve seguire il tempo di andata e ritorno (RTT) della rete: troppo corto provoca ritrasmissioni inutili, troppo lungo rallenta il recupero. L'RTT si misura con un solo timer per connessione (granularità G del clock). Si mantengono una media mobile esponenziale SRTT_i = (1-α)SRTT_{i-1} + α·rtt_i con α = 1/8 e la deviazione media MAD_i = (1-ρ)MAD_{i-1} + ρ|rtt_i - SRTT_{i-1}| con ρ = 1/4 (in RFC 6298 RTTVAR, β = 1/4); RTO = SRTT + 4·MAD, con minimo di 1 s. L'algoritmo di Karn ignora le misure dei segmenti ritrasmessi (non si sa a quale trasmissione si riferisce l'ACK) e a ogni timeout consecutivo il valore raddoppia fino a 64 volte T0. Per un RTT gaussiano la deviazione media vale MAD = σ·sqrt(2/π) ≈ 0,797σ.Stima del timeout di ritrasmissione (RTO) →.
• ACK duplicati. Con i pacchetti $1,2,\dots,8$, se il $4$ si perde, la ricezione di $5,6,7,8$ genera quattro volte lo stesso ACK, $\text{ACK}(4)$: i pacchetti $1,2,3$ sono arrivati e il primo fuori ordine è il $4$. Il ricevente deve inviare un dupACK a ogni segmento fuori ordine, e non si sa se sia perdita o solo riordino. Dopo $K$ (di solito $3$) dupACK TCP presume che il segmento sia perso e ritrasmette quello indicato dal $K$-esimo dupACK: ritrasmissione rapida (fast retransmit).

Il timeout è l'indizio di congestione grave (non arriva più niente); i tre dupACK sono un indizio lieve (qualche pacchetto è comunque passato).

Formula (reazioni di base, regole del corso). Quando la congestione è indicata da $K$ dupACK: $\text{ssthresh}=W/2$. Con timeout: $\text{ssthresh}=W/2$ e $\text{cwnd}=1$ (nuovo slow start). ($W$ è la finestra al momento dell'evento.)

Le varianti di TCP

Old Tahoe

Implementa slow start e congestion avoidance e usa solo il timeout come recupero. Allo scadere del timeout riparte dal primo pacchetto non riscontrato, senza ritrasmettere esplicitamente (in pratica un Go-Back-N).

Tahoe

Aggiunge la ritrasmissione rapida. Alla $K$-esima dupACK: ritrasmette il segmento mancante, pone $\text{ssthresh}=W/2$ e $\text{cwnd}=1$ e riparte dallo slow start, come se fosse scaduto un timeout. In SS: se c'è congestione, ssthresh$=\text{cwnd}/2$ e $\text{cwnd}=1$; se non c'è, a ssthresh si passa in CA; in CA, se c'è congestione, stesso trattamento (ssthresh dimezzata, ritorno in SS). Tahoe tratta allo stesso modo timeout e tre dupACK.

Reimpostare $\text{cwnd}=1$ dopo la ritrasmissione rapida è inefficiente: è come riavviare la connessione, con possibile calo di throughput. Ma i dupACK dicono che i pacchetti dopo quello perso sono arrivati: si può ritrasmettere meno e far avanzare cwnd con più decisione. È l'idea del fast recovery.

Reno: fast recovery

Reno aggiunge a Tahoe lo stato di fast recovery (recupero rapido), per riprendersi da una congestione lieve. Quando il ricevente continua a mandare dupACK, ogni dupACK in più vuol dire che un altro pacchetto è uscito dalla rete.

Formula (Reno).

• Alla terza dupACK: $\text{ssthresh}=\text{cwnd}/2$; si ritrasmette il segmento mancante; $\text{cwnd}=\text{ssthresh}+3$ MSS (i tre pacchetti che hanno generato i tre dupACK hanno lasciato la rete).
• A ogni dupACK successivo: $\text{cwnd}\leftarrow\text{cwnd}+1$ MSS (un altro pacchetto ha raggiunto il ricevente) e si trasmette un pacchetto se cwnd lo consente.
• Quando arriva un ACK che riscontra dati nuovi: $\text{cwnd}=\text{ssthresh}$ e si esce dal fast recovery (si prosegue in CA).
• Dopo un timeout: come Tahoe ($\text{ssthresh}=\text{cwnd}/2$, $\text{cwnd}=1$, slow start).

Esempio. $\text{cwnd}=12$: tre dupACK $\Rightarrow$ $\text{ssthresh}=6$, $\text{cwnd}=9$; due dupACK in più $\Rightarrow\text{cwnd}=11$; all'ACK nuovo $\text{cwnd}=6$ e CA ($7,8,\dots$). Tahoe, nello stesso caso, ripartirebbe da $1$.

Limite di Reno: se nella stessa finestra si perdono più segmenti, il primo ACK che riscontra dati nuovi (parziale, perché non copre tutta la finestra) fa uscire dal fast recovery; per recuperare il secondo segmento servono altri tre dupACK, e a volte non ne arrivano abbastanza e scatta il timeout.

NewReno

NewReno recupera più perdite nella stessa finestra, restando nel fast recovery finché non è riscontrato tutto ciò che era in volo quando è iniziata la perdita. Variabili: recover (il più alto numero di sequenza trasmesso quando inizia il recupero) e flightsize $=\text{lastseqno}-\text{ack\_no}+1$ (pacchetti in volo).

Formula (NewReno).

• Alla $K$-esima dupACK: $\text{recover}=\text{lastseqno}$; $\text{ssthresh}=\max(\text{flightsize}/2,\ 2\,\text{MSS})$; $\text{cwnd}=\text{ssthresh}+3$ MSS; si azzera il timer di ritrasmissione (per evitare un timeout durante il recupero); si ritrasmette il segmento mancante.
• A ogni nuovo dupACK: $\text{cwnd}\leftarrow\text{cwnd}+1$, e si trasmette se cwnd lo permette.
• Quando arriva un ACK che riscontra dati nuovi: se $\text{ack\_no}>\text{recover}$ (ACK completo) allora $\text{cwnd}=\text{ssthresh}$ ed esce dal fast recovery; altrimenti è un ACK parziale che riscontra $n_{\text{acked}}$ pacchetti: $\text{cwnd}\leftarrow\text{cwnd}-n_{\text{acked}}+1$, si azzera il timer, si ritrasmette il pacchetto con $\text{seq\_no}=\text{ack\_no}$ e si trasmette se consentito.

Esempio (slide del corso). Finestra $W=9$ in CA, sono in volo i pacchetti $P_3,\dots,P_{11}$; si perdono $P_6$ e $P_8$; ACK ritardati con $b=2$. Il ricevente manda $\text{ACK}\,5$ (riscontra $P_3,P_4$), $\text{ACK}\,6$ (riscontra $P_5$), poi ogni pacchetto che arriva fuori ordine ($P_7,P_9,P_{10},P_{11}$) genera un dupACK$\,6$. Alla terza dupACK il mittente ha già inviato fino a $P_{14}$: $\text{recover}=P_{14}$, $\text{flightsize}=14-6+1=9$, $\text{ssthresh}=\lfloor9/2\rfloor=4$, $\text{cwnd}=4+3=7$; ritrasmette $P_6$. Gli altri dupACK portano cwnd a $8$, $9$, $10$ e fanno partire $P_{15}$. L'arrivo di $P_6$ al ricevente genera $\text{ACK}\,8$ (riscontra $P_6$ e $P_7$, manca $P_8$): è un ACK parziale ($8\le14$) con $n_{\text{acked}}=2$, quindi $\text{cwnd}=10-2+1=9$; in volo ci sono $P_8,\dots,P_{15}$, cioè $8$ pacchetti $<9$, quindi parte un nuovo pacchetto, $P_{16}$, e si ritrasmette $P_8$. Quando poi arriva $\text{ACK}\,16$, $16>\text{recover}=14$: ACK completo, $\text{cwnd}=\text{ssthresh}=4$ e fine del recupero. Due perdite sono state recuperate in due RTT senza timeout.

SACK: riscontro selettivo

Con l'opzione SACK (selective acknowledgment) il ricevente comunica quali blocchi ha ricevuto, così il mittente ritrasmette solo quello che manca.

• Apertura: l'opzione si negozia nel solo segmento SYN: Kind $=4$, Length $=2$.
• Uso: in ogni ACK, quando ci sono pacchetti fuori ordine, compare l'opzione con Kind $=5$, Length variabile e una lista di blocchi: per ognuno il bordo sinistro (primo byte del blocco) e il bordo destro (primo byte dopo il blocco), 4 byte ciascuno.

Formula (lunghezza dell'opzione SACK). Con $n$ blocchi: $\text{lunghezza}=8n+2$ byte. Poiché le opzioni TCP sono al massimo $40$ byte, $n\le4$ ($8\cdot4+2=34$). Se c'è anche il timestamp ($12$ byte con riempimento), restano $28$ byte e $n\le3$ ($8\cdot3+2=26$).

Passaggio: ogni blocco ha due bordi da $4$ byte, quindi $8$ byte, e a questi si aggiungono $2$ byte per Kind e Length. Imporre $8n+2\le40$ dà $n\le38/8=4{,}75$, cioè $n\le4$ perché $n$ è intero; con $28$ byte disponibili $8n+2\le28$ dà $n\le26/8=3{,}25$, cioè $n\le3$.

Esempio. Il ricevente ha i byte $1$–$1000$ (campo ACK $=1001$, riscontro cumulativo), manca $1001$–$2000$, ha $2001$–$3000$, manca $3001$–$4000$, ha $4001$–$5000$. Opzione: Kind $=5$, Length $=2+2\cdot8=18$, blocchi $[2001,3001)$ e $[4001,5001)$.

NewReno con SACK. Alla $K$-esima dupACK: $\text{recover}=\text{lastseqno}$; $\text{ssthresh}=\max(\text{flightsize}/2,2\,\text{MSS})$; $\text{cwnd}=\text{ssthresh}$ (senza "$+3$": non serve, perché il numero di pacchetti in rete si calcola con la variabile pipe); si ritrasmette il segmento mancante; $\text{pipe}=\text{lastseqno}-\text{lastackno}+1$, diminuita dei pacchetti che SACK dice già arrivati. Finché $\text{pipe}<\text{cwnd}$: se la lista SACK mostra un buco si ritrasmette il primo pacchetto mancante, altrimenti si trasmette un pacchetto nuovo, e $\text{pipe}$ aumenta di 1. A ogni nuovo ACK (duplicato o no) $\text{pipe}=\text{pipe}-n_{\text{acked}}$ e si ripete il ciclo. Con un ACK che riscontra dati nuovi oltre recover si esce dal recupero.

Riepilogo

La finestra nel tempo: Tahoe e Reno a confronto

Esempio completo, a round (un round $=1$ RTT; non si conta l'attesa dell'RTO, che sul grafico tempo-reale sarebbe uno o più RTT di silenzio). $\text{ssthresh}$ iniziale $=16$ MSS. Nel round $9$ ($\text{cwnd}=20$) scade un timeout: ssthresh $=10$, $\text{cwnd}=1$ (uguale in Tahoe e Reno). Nel round $16$ ($\text{cwnd}=12$) arrivano 3 dupACK: ssthresh $=6$; Tahoe riparte con $\text{cwnd}=1$ (slow start), Reno con $\text{cwnd}=6$ (CA, ignorando la fase di gonfiamento durante il recupero).

Nel round $5$ si raggiunge la soglia ($\text{cwnd}=16=\text{ssthresh}$) e da lì si cresce di $1$ per round. Dopo il timeout lo slow start si ferma al valore $10$ (metà di $20$) e riprende la crescita lineare. Dopo i tre dupACK Reno perde meno finestra: nel round $24$ ha $13$ contro i $10$ di Tahoe.

Linea continua: Tahoe; tratteggiata: Reno (coincide con Tahoe fino al round $16$).

Tahoe, Reno, NewReno e SACK con quattro perdite in una finestra

Il confronto sperimentale di Fall e Floyd (simulazione con quattro pacchetti persi nella stessa finestra) si riassume così:

1. Tahoe $\approx$ NewReno: Tahoe riparte da $1$, NewReno recupera una perdita per RTT (quattro ritrasmissioni, una per RTT), in tempi simili.
2. Reno fatica a recuperare più perdite nella stessa finestra: ritrasmette il primo pacchetto perso, poi servono abbastanza trasmissioni per produrre nuovi dupACK e permettere la seconda ritrasmissione, e alla fine scatta il timeout.
3. SACK dà le prestazioni migliori: con i dupACK arricchiti dalle informazioni SACK il mittente fa ritrasmissioni selettive dei soli pacchetti persi, quindi recupera tutte le perdite in circa un RTT.