TCP - connessione, affidabilità e controllo di flusso

TCP (Transmission Control Protocol) è un protocollo di trasporto orientato alla connessione e affidabile. Rispetto a 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 →) aggiunge tre fasi esplicite e un insieme di meccanismi di affidabilità:

1. apertura della connessione (connection set-up): handshake a tre vie;
2. trasferimento dei dati: un flusso di byte (byte stream), come se tra mittente e destinatario ci fosse un circuito dedicato;
3. chiusura della connessione: non si liberano risorse nella rete, ma solo negli host finali.

Per essere affidabile TCP combina idee di Go-Back-N e di Selective Repeat (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 →, e per la teoria generale degli ARQ 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 →): checksum per rilevare gli errori, numeri di byte, di sequenza e di riscontro (acknowledgment) per ritrasmettere i pacchetti persi o corrotti e per riordinare quelli arrivati fuori ordine, riscontri cumulativi e selettivi. Il controllo di congestione è in 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 →, la stima del timeout in 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) →.

I servizi di TCP

• Processo-processo: come UDP, usa i socket e le porte (Livello di trasporto - porte e multiplexingIl livello di trasporto (transport layer) offre la comunicazione logica end-to-end tra processi applicativi di host diversi, ed è realizzato solo negli host finali, non nei router. Il livello di rete consegna al computer giusto (indirizzo IP), il trasporto consegna al processo giusto (numero di porta di 16 bit, 0-65535). Una porta più un indirizzo IP formano un socket; la quaterna (IP sorgente, porta sorgente, IP destinazione, porta destinazione) identifica una connessione. I servizi sono: comunicazione processo-processo, indirizzamento, incapsulamento/decapsulamento, multiplexing/demultiplexing e, se il protocollo è affidabile, controllo di errore, di flusso e di congestione. I protocolli sono UDP (senza connessione, inaffidabile), TCP (con connessione, affidabile) e SCTP (combina i due).Livello di trasporto - porte e multiplexing →).
• Full-duplex: i dati possono viaggiare nei due sensi contemporaneamente; ogni estremo ha un proprio buffer di invio e uno di ricezione.
• Multiplexing e demultiplexing: come UDP, ma serve una connessione per ogni coppia di processi (identificata dalla quaterna porte-IP).
• Servizio affidabile: usa i riscontri per verificare che i dati siano arrivati sani e salvi.
• Orientato alla connessione: le fasi sono tre (apertura, scambio, chiusura). La connessione è logica, non fisica: i segmenti TCP viaggiano dentro datagrammi IP che possono essere persi, corrotti, riordinati e seguire percorsi diversi. TCP trasforma il servizio inaffidabile e senza connessione di IP in un servizio affidabile e con connessione per l'applicazione.
• Flusso di byte: i dati dell'applicazione sono un flusso senza "etichette" o separatori di messaggi.

Il segmento TCP

L'intestazione è organizzata in parole da 32 bit; i campi fissi occupano 20 byte, seguiti da al più 40 byte di opzioni.

• Porte (16 + 16 bit): dei processi di mittente e destinatario.
• Numero di sequenza (SN, 32 bit): numero assegnato al primo byte di dati contenuto nel segmento. All'apertura ciascuna parte sceglie con un generatore casuale un numero di sequenza iniziale (initial sequence number, ISN) in $[0,2^{32}-1]$.
• Numero di riscontro (AN, 32 bit): il prossimo byte atteso dal ricevente. Se ha ricevuto con successo il byte $x$, risponde $x+1$. È un riscontro cumulativo: AN $=5643$ significa che tutti i byte fino al $5642$ compreso sono stati ricevuti. ACK e dati possono viaggiare nello stesso segmento (piggybacking).
• HLEN (4 bit): lunghezza dell'intestazione in parole da 4 byte, quindi sempre tra $5$ ($5\cdot4=20$ byte) e $15$ ($15\cdot4=60$ byte).
• Flag (6 bit): URG (il puntatore urgente è valido), ACK (il numero di riscontro è valido), PSH (consegna subito all'applicazione), RST (azzera la connessione), SYN (sincronizza i numeri di sequenza), FIN (il mittente ha finito). Con ECN (RFC 3168) si aggiungono CWR ed ECE.
• Finestra (16 bit): lo spazio di buffer libero del ricevente, in byte (receive window, rwnd). Con 16 bitcon k bit si rappresentano i numeri da 0 a 2^k − 1Sistemi di numerazione posizionali → vale al massimo $2^{16}-1=65\,535$ byte; il valore lo decide il ricevente e il mittente deve rispettarlo. Serve per il controllo di flusso e di congestione.
• Checksum (16 bit): come in UDP ma obbligatorio; copre intestazione, dati e pseudo-intestazione (con protocollo $=6$).
• Puntatore urgente (16 bit): valido solo con URG; sommato a SN dà il numero dell'ultimo byte urgente.
• Opzioni (fino a 40 byte): end of option (riempimento), no operation (allineamento), MSS, SACK, timestamp.

MSS: dimensione massima del segmento

L'opzione MSS (maximum segment size) dice la massima quantità di dati TCP (esclusa l'intestazione TCP) che un host accetta in un segmento. Il valore predefinito è $536$ byte, il massimo $65\,535$. Per evitare la frammentazione IP (Datagramma IP e frammentazioneIPv4 è un servizio senza connessione, non affidabile, best effort: i pacchetti (datagrammi) possono essere persi, corrotti, riordinati o ritardati. L'intestazione ha 20-60 byte (HLen conta parole da 4 byte, da 5 a 15); il campo Total Length (16 bit) dà la lunghezza totale fino a 65 535 byte; TTL limita i salti, Protocol identifica il protocollo trasportato (1 ICMP, 6 TCP, 17 UDP), il checksum copre solo l'intestazione. Se un datagramma è più grande dell'MTU del collegamento viene frammentato: solo il payload si divide, ogni frammento ha un'intestazione propria; l'Offset (13 bit) è in unità di 8 byte, MF=1 in tutti i frammenti tranne l'ultimo, e il riassemblaggio avviene solo a destinazione.Datagramma IP e frammentazione →) un host dovrebbe annunciare come MSS la dimensione del più grande datagramma IP che sa gestire, cioè l'MTU meno le intestazioni IP e TCP.

Formula (MSS). $\text{MSS}=\text{MTU}-\text{(intestazione IP)}-\text{(intestazione TCP)}=\text{MTU}-40$ (con intestazioni di 20 byte ciascuna).

Esempio. Ethernet, MTU $=1500$ byte: $\text{MSS}=1500-20-20=1460$ byte (i $1500$ byte del datagramma IP contengono $20$ byte di intestazione IP, $20$ di intestazione TCP e il resto è payload). Un collegamento con MTU $512$ dà $\text{MSS}=512-40=472$. Un segmento pieno è quindi $1460$ byte di dati più $20$ di TCP $=1480$ byte e, con i $20$ di IP, esattamente $1500$ byte (l'MTU): la frazione di byte utili è $1460/1500=97{,}3\,\%$.

Numeri di sequenza e di riscontro

Ogni byte del flusso ha un numero. Il numero di sequenza di un segmento è quello del suo primo byte; il successivo parte dal numero precedente più il numero di byte trasportati.

Esempio. File di $5000$ byte, ISN $=10\,001$, segmenti da $1000$ byte:

Dopo aver ricevuto il segmento 3 per intero il ricevente risponde AN $=13\,001$. Passaggi: l'SN del segmento $k$ è $\text{ISN}+(k-1)\cdot1000$ (qui $10\,001+3\cdot1000=13\,001$ per $k=4$); l'ultimo byte del segmento 3 è $12\,001+1000-1=13\,000$ e il prossimo byte atteso è $13\,000+1=13\,001$. Gli estremi «$-1$» e «$+1$» nascono dal fatto che un segmento da $n$ byte con primo byte $s$ copre i byte $s,\dots,s+n-1$.

Proprietà (quanti numeri di sequenza consuma un segmento). Un segmento senza dati (per esempio un semplice ACK) non consuma numeri di sequenza. I segmenti SYN e FIN, pur senza dati, ne consumano uno (come se portassero un byte immaginario), perché devono essere riscontrati.

Apertura della connessione: handshake a tre vie

Il client apre la connessione e passa per tre segmenti (three-way handshaking). Esempio con SYN, ISN del client $8000$, ISN del server $15\,000$:

1. SYN. Il client invia un segmento con solo il flag SYN, SN $=8000$ (il suo ISN, scelto a caso). Non porta dati, non ha numero di riscontro e non definisce la finestra, ma consuma un numero di sequenza.
2. SYN + ACK. Il server risponde con SYN e ACK: SN $=15\,000$ (il suo ISN, diverso: la comunicazione è full-duplex e ogni verso ha il suo), AN $=8001$ (riscontra il SYN, atteso il byte $8001$), rwnd $=5000$. Anche questo consuma un numero di sequenza.
3. ACK. Il client riscontra: SN $=8001$, AN $=15\,001$, rwnd $=10\,000$. Un ACK senza dati non consuma numeri di sequenza; l'implementazione può però far portare al terzo segmento i primi dati del client (piggyback), e allora consuma tanti numeri quanti sono i byte.

Tempi. Se i segmenti di apertura sono trascurabili rispetto al tempo di propagazione $\tau$, il client riceve il SYN+ACK dopo $2\tau$ (un tempo di andata e ritorno di sola propagazione) e può iniziare a spedire dati subito, nello stesso segmento dell'ACK (piggyback). Nella convenzione degli esercizi del corso il tempo di apertura prima dei dati è $T_{\text{setup}}=2\tau$ con piggyback (i dati partono insieme al terzo segmento), mentre senza piggyback il terzo segmento deve prima raggiungere il server e il conto sale a $3\tau$. Con $\tau=10$ ms: $20$ ms oppure $30$ ms.

Scambio dei dati

Dopo l'apertura i due lati scambiano dati e riscontri nei due versi, con piggybacking. Esempio: il client invia $2000$ byte in due segmenti, poi il server ne invia $2000$ in uno, poi il client un altro segmento:

Chiusura della connessione

A tre vie. Il client invia un segmento con FIN (consuma un numero di sequenza), SN $=x$. Il server risponde con FIN+ACK (SN $=y$, AN $=x+1$; consuma anch'esso un numero). Il client invia l'ultimo ACK (AN $=y+1$) e chiude la sessione nei due versi.

A quattro vie con chiusura a metà (half closing). Il client invia FIN, il server risponde solo con ACK e continua a inviare dati, mentre il client può spedire solo ACK senza dati. Quando ha finito, il server invia il suo FIN e il client risponde con ACK e chiude.

Le finestre di TCP

Finestra di invio

La finestra di invio (send window) somiglia a quella di Selective Repeat (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 →) ma con alcune differenze:

• la dimensione è in byte, non in pacchetti (anche se la trasmissione avviene per segmenti);
• il mittente TCP può inviare segmenti appena li riceve dal suo processo;
• il Selective Repeat teorico potrebbe usare un timer per ogni pacchetto; TCP usa un solo timer.

Si distinguono: i byte già inviati e riscontrati; i byte in volo (inviati ma non riscontrati, a partire dal primo byte non riscontrato $S_f$); i byte che si possono ancora inviare (usable window), fino al prossimo byte da inviare $S_n$; e i byte fuori dalla finestra, che si possono inviare solo quando la finestra scorre.

Formula (finestra di invio). $\text{swnd}=\min(\text{rwnd},\,\text{cwnd})$, e un nuovo byte si può inviare se $\text{ultimo\_inviato}-\text{ultimo\_riscontrato}\le\text{swnd}$. rwnd (finestra del ricevitore) dipende dall'estremo di destinazione; cwnd (finestra di congestione, 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 →) dipende dalla rete.

Esempio. Con rwnd $=6$ MSS e cwnd $=4$ MSS, $\text{swnd}=4$ MSS; quando cwnd sale a $7$ MSS, $\text{swnd}=6$ MSS: oltre rwnd non si può andare.

Finestra di ricezione

Anche questa è simile a quella di Selective Repeat, ma: TCP lascia che il processo ricevente legga ("pull") i dati con il suo ritmo, quindi una parte del buffer può essere occupata da byte ricevuti e già riscontrati, in attesa di essere letti; e il riscontro è cumulativo (indica il prossimo byte atteso) anziché selettivo.

Formula (finestra del ricevitore). $\text{rwnd}=\text{dimensione del buffer}-\text{byte in attesa di essere letti dal processo}.$

Controllo di flusso

Il buffer è di dimensione fissa, ma TCP obbliga mittente e ricevente ad adattare le finestre. La finestra del ricevitore si chiude quando arrivano byte che l'applicazione non consuma, si apre quando l'applicazione li legge. Il mittente adegua la sua: la finestra di invio si chiude se arriva un ACK con rwnd ridotta, si apre se rwnd aumenta, e si restringe (shrinks) se il margine destro arretra: situazione da evitare.

Esempio. Buffer del ricevente di $800$ byte; i byte sono numerati da $101$.

Nei passi 1 e 2 i byte sono riscontrati ma rwnd diminuisce: la finestra si chiude. Nei passi 3 e 4 gli ACK sono ripetuti, perché il ricevente non ha ricevuto nuovi dati ma ha liberato posto: la finestra si riapre.

Il blocco (deadlock) e il persist timer

Se il ricevente riempie il buffer, invia un ACK con rwnd $=0$ e il mittente si ferma. Per ripartire serve un ACK con rwnd $>0$: il ricevente lo manda (come ACK duplicato) quando l'applicazione ha liberato almeno un MSS o metà buffer. Ma se questo ACK si perde, il mittente non lo saprà mai e resterebbe bloccato per sempre, mentre il ricevente aspetta dati.

Definizione (persist timer). Quando rwnd $=0$ il mittente avvia un persist timer (inizialmente $500$ ms, dipende dall'implementazione). Se scade senza aver ricevuto segmenti, il mittente invia una sonda (probe) di 1 byte, che fa ripetere al ricevente il prossimo byte atteso e la finestra corrente. Se il ricevente è ancora pieno rifiuta la sonda; altrimenti la riscontra e annuncia la finestra disponibile. A ogni mancata risposta il timer raddoppia (backoff esponenziale), fino a un massimo di $60$ s.

Esempio. Sonde a $0{,}5$, $1$, $2$, $4$, $8$, $16$, $32$, $60$ s: il valore dopo $n$ mancate risposte è $0{,}5\cdot2^n$ s (progressione geometrica di ragione $2$) e, arrivati a $0{,}5\cdot2^7=64$ s, che supera il massimo, si ferma a $60$ s. Dopo l'ottava sonda quindi si sonda ogni $60$ s.

Il problema dei datagrammi minuscoli e l'algoritmo di Nagle

Se l'applicazione mittente produce dati lentamente, TCP potrebbe inviare segmenti da pochi byte, con grande overhead: un segmento con 1 byte di dati diventa un datagramma di $20+20+1=41$ byte, e l'efficienza è $1/41=2{,}4\%$ (peggio ancora contando collegamento e fisico).

Definizione (algoritmo di Nagle). Dopo aver inviato il primo segmento, il mittente accumula i dati nel buffer d'uscita e aspetta o che arrivi l'ACK del ricevente, o che si siano accumulati dati sufficienti per riempire un MSS; poi trasmette.

L'algoritmo tiene conto sia della velocità dell'applicazione sia di quella della rete: su una rete veloce gli ACK tornano presto e i segmenti partono spesso; su una lenta si accumula di più.

La sindrome della finestra stupida (silly window syndrome)

Il problema opposto nasce quando è il ricevente a consumare i dati lentamente. Per esempio il mittente produce blocchi da 1 kB, ma l'applicazione ricevente legge 1 byte per volta: se il buffer è pieno e ne libera uno solo, il ricevente annuncia rwnd $=1$ e il mittente invia un segmento di 1 byte; trasmettere un blocco lungo richiede un'eternità. Due rimedi lato ricevente:

1. ACK ritardato (delayed ACK): l'ACK non parte subito ma solo quando nel buffer c'è una quantità decente di spazio.
2. Algoritmo di Clark: l'ACK parte subito all'arrivo dei dati, ma annuncia una finestra $0$ finché non c'è spazio per almeno un MSS oppure finché almeno metà del buffer è libero.

Controllo di errore

L'applicazione consegna a TCP un flusso di dati e pretende che sia consegnato all'altro estremo per intero, in ordine, senza errori, perdite e duplicati. TCP lo ottiene con tre strumenti semplici: checksum, riscontro e timeout; più la ritrasmissione. I segmenti fuori ordine non vengono scartati: il ricevente li tiene e riscontra il byte che manca.

Ritrasmissione allo scadere dell'RTO. Il mittente ha un solo retransmission timeout per connessione. Quando scade, rispedisce il segmento in testa alla coda (quello con il numero di sequenza più basso) e riavvia il timer. Il valore dell'RTO è dinamico e dipende dal tempo di andata e ritorno (RTT) dei segmenti: 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) →.

Ritrasmissione rapida (fast retransmit). Il ricevente deve inviare un ACK duplicato (dupACK) ogni volta che riceve un segmento fuori ordine. Un dupACK non dice se il segmento è stato perso o solo riordinato dalla rete. Se arrivano tre ACK duplicati (cioè l'ACK originale più tre copie identiche) è un forte indizio di perdita, e il segmento indicato dall'ACK si ritrasmette subito, senza aspettare il timeout.

Esempio (segmento perso, timeout). Il client invia quattro segmenti da $100$ byte, byte $501$ – $900$. Il segmento $3$ ($701$–$800$) si perde. Il server riceve $501$–$600$ e $601$–$700$ (ACK $=701$), poi $801$–$900$ fuori ordine: non lo scarta, ma riscontra ancora ACK $=701$ (dupACK). Un solo dupACK non basta per la ritrasmissione rapida: dopo il timeout il client rispedisce $701$–$800$ e il server, avendo già $801$–$900$, risponde ACK $=901$.

Esempio (ritrasmissione rapida). Il client invia sei segmenti da $100$ byte ($101$–$700$); il terzo ($301$–$400$) si perde, e il timeout non scade prima del terzo dupACK:

L'ACK $=701$ conferma in un colpo solo i byte $301$–$700$: è il vantaggio del riscontro cumulativo.

ACK ritardati

Normalmente TCP non invia l'ACK nell'istante in cui riceve i dati: li ritarda sperando di avere dati in viaggio nello stesso verso, così da spedire l'ACK nello stesso pacchetto (delayed ACK). Un ACK parte ogni $b$ pacchetti dati consecutivi ricevuti (in quasi tutte le implementazioni $b=2$), o allo scadere di un breve timer. Il parametro $b$ entra nel modello del tasso di invio (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 →).

Finestra, BDP e throughput massimo

TCP è un protocollo a finestra scorrevole: ogni RTT si possono inviare al più $W$ segmenti non riscontrati (stessa logica di Go-Back-N e Selective Repeat in 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 →: la finestra deve coprire la capacità del tubo). Il canale è usato in modo continuo se la finestra permette di trasmettere finché non torna l'ACK del primo segmento. Con tempo di trasmissione di un segmento $t_x=L/C$ ($L$ lunghezza in bit, $C$ bitrate) il mittente impiega $W\cdot t_x$ per spedire l'intera finestra, e l'ACK del primo segmento torna dopo un RTT dall'inizio dell'invio: per non fermarsi deve valere

$$W\cdot t_x\ge\text{RTT}\qquad\Longleftrightarrow\qquad W\cdot L\ge C\cdot\text{RTT},$$

dove nel secondo passaggio si è moltiplicato per $C$ e si è usato $t_x\,C=L$.

Definizione (BDP). Il prodotto banda-ritardo (bandwidth-delay product) è $\text{BDP}=C\cdot\text{RTT}$, la quantità di bit in volo. La finestra ideale in bit è $W\cdot L=\text{BDP}$.

Se $W\cdot L<\text{BDP}$ si spreca banda (il mittente aspetta gli ACK); se $W\cdot L>\text{BDP}$ i pacchetti in eccesso si accodano nei router, il RTT aumenta e si può arrivare a perdite.

Esempio (continuità). $C=10$ Mbit/s, $L=1500$ byte$=12\,000$ bit, $\tau=5$ ms per tratta: $t_x=1{,}2$ ms, $\text{RTT}=t_x+2\tau=11{,}2$ ms (ACK trascurabile). Serve $W\ge11{,}2/1{,}2=9{,}33$, cioè $W=10$ segmenti.

Formula (throughput massimo). La finestra limita la quantità di dati inviabili per RTT, quindi qualunque variante di TCP non può superare $$\text{throughput}\le\frac{\text{MSS}\cdot W_{\max}}{\text{RTT}}.$$

Perché: in ogni RTT il mittente può spedire al più $W_{\max}$ segmenti da $\text{MSS}$ byte, cioè $\text{MSS}\cdot W_{\max}$ byte (dopo di che deve aspettare gli ACK); i byte inviati per RTT, divisi per la durata dell'RTT, sono il tasso massimo. Se la finestra è espressa in byte (come rwnd) il prodotto $\text{MSS}\cdot W_{\max}$ è la finestra stessa. Per avere bit/s si moltiplica per $8$.

Esempio. Collegamento da $100$ Mbit/s, $\text{RTT}=40$ ms, $\text{MSS}=1460$ byte. $\text{BDP}=10^8\cdot0{,}04=4\cdot10^6$ bit $=500$ kB, cioè $500\,000/1460=342{,}5\approx343$ segmenti: per riempire il canale servono $343$ segmenti in volo. Con la sola finestra a 16 bit ($W_{\max}=65\,535$ byte, senza l'opzione di scalatura) il throughput è al più $65\,535\cdot8/0{,}04=13{,}1$ Mbit/s (il fattore $8$ converte byte in bit, $0{,}04$ s è l'RTT): solo il $13\%$ del canale, perché $13{,}1/100=0{,}131$. Nel grafico l'utilizzazione $U=\min(1,\,W/343)$ cresce linearmente con la finestra e arriva a $1$ solo con $W\ge\text{BDP}/\text{MSS}$; la finestra a 16 bit ($65\,535/1460\approx45$ segmenti) si ferma al $13\%$.

{"tipo":"funzione","titolo":"Utilizzazione del canale U = min(1, W/342,5) con C = 100 Mbit/s, RTT = 40 ms, MSS = 1460 byte: con rwnd massima di 16 bit (≈ 44,9 segmenti) U = 13%","curve":[{"espressione":"min(1,x/342.47)","etichetta":"U"}],"x":[0,400],"y":[0,1.1],"verticali":[{"x":44.89,"etichetta":"65 535 B"},{"x":342.47,"etichetta":"BDP"}],"assi":{"x":"W (segmenti in volo)","y":"U"}}
``` Esercizi su questi temi: <a class="wiki" href="/internet/esercizi/esercizio-tcp-con-finestra-del-ricevitore-di-4-segmenti-su-tre-collegamenti/">Esercizio - TCP con finestra del ricevitore di 4 segmenti su tre collegamenti</a>; per misurare capacità e ritardo con i tempi di andata e ritorno, <a class="wiki" href="/internet/esercizi/esercizio-capacita-e-ritardo-di-propagazione-di-un-collegamento-con-due-messaggi-echo/">Esercizio - capacita e ritardo di propagazione di un collegamento con due messaggi echo</a>.