TCP: finestra scorrevole, controllo di congestione ed equità

IP consegna i pacchetti “al meglio”: possono perdersi, arrivare in disordine o duplicati. Sopra di lui TCP costruisce un flusso di byte affidabile e ordinato tra due programmi, e fa anche qualcosa di più delicato: regola la velocità di ogni trasmettitore in modo che milioni di connessioni condividano la rete senza farla collassare. In questa lezione vediamo la trasmissione affidabile con la finestra scorrevole e la dimostrazione del suo rendimento, la gestione della connessione, il controllo di congestione con la crescita additiva e la diminuzione moltiplicativa, e la dimostrazione che questo meccanismo divide la banda in modo equo.

Il rendimento di “invia e aspetta”

Il modo più semplice di trasmettere in modo affidabile: inviare un pacchetto, aspettare la conferma (ACK), poi inviare il successivo, ritrasmettendo se la conferma non arriva entro un tempo limite.

Teorema. Con pacchetti di bit, velocità e tempo di andata e ritorno RTT, la frazione di tempo in cui il collegamento trasmette con “invia e aspetta” è

Dimostrazione. Il trasmettitore impiega a inviare il pacchetto; l’ultimo bit arriva dopo il ritardo di propagazione, e la conferma torna dopo un altro: in tutto, dall’inizio della trasmissione alla conferma, passano (trascurando la durata della conferma). In questo intervallo il collegamento è usato solo per . ∎

Con 1 Gb/s, pacchetti da 1500 byte (12 µs) e RTT di 30 ms, : si usa lo 0,04 % del collegamento. La soluzione è la finestra scorrevole: si possono inviare fino a byte senza aspettare conferme. La velocità massima diventa

e per riempire il collegamento la finestra deve valere almeno il prodotto banda-ritardo (lezione sull’architettura): nell’esempio 3,75 MB. Se un pacchetto si perde, si può ritrasmettere tutto da lì in poi (go-back-N) o solo il pacchetto perso (ripetizione selettiva, che TCP realizza con le conferme selettive, SACK).

La connessione TCP

TCP apre la connessione con lo scambio a tre vie: SYN dal client, SYN-ACK dal server, ACK dal client. Ogni byte ha un numero di sequenza, e le conferme sono cumulative: “ho ricevuto tutto fino al byte “. Il destinatario annuncia quanto spazio ha nel proprio buffer (la finestra di ricezione): è il controllo di flusso, che impedisce a un trasmettitore veloce di sommergere un ricevitore lento. Il tempo limite di ritrasmissione si adatta continuamente, stimando la media e la variabilità dell’RTT.

Il controllo di congestione

Il controllo di flusso protegge il ricevitore; la rete va protetta a parte. Se tutti trasmettono troppo, le code dei router si riempiono, i pacchetti si perdono, i trasmettitori ritrasmettono, e la rete può arrivare al collasso da congestione: tutta la capacità è usata per ritrasmissioni inutili. Accadde davvero in Internet nel 1986, e Van Jacobson introdusse il meccanismo che, con varianti, si usa ancora.

Il trasmettitore mantiene una finestra di congestione , e la finestra usata è la minore tra questa e quella di ricezione:

• partenza lenta (slow start): all’inizio raddoppia a ogni RTT, per trovare in fretta la capacità disponibile;
• crescita additiva: superata una soglia, cresce di un pacchetto per RTT, per saggiare con cautela se c’è altro spazio;
• diminuzione moltiplicativa: quando un pacchetto si perde, segno che una coda è piena, viene dimezzata.

In regime la finestra oscilla a dente di sega tra e , con un valore medio di . Ne segue la nota formula di Mathis: con una probabilità di perdita , il throughput è circa , dove MSS è la dimensione del segmento. Raddoppiare la distanza dimezza la velocità, e per avere 10 Gb/s su lunghe distanze servono probabilità di perdita minuscole.

L’equità

Perché proprio “crescita additiva e diminuzione moltiplicativa” (AIMD)? Perché è la combinazione che porta le connessioni a dividersi la banda in parti uguali, senza che nessuno le coordini.

Teorema. Due connessioni con lo stesso RTT che condividono un collegamento con politica AIMD convergono a velocità uguali.

Dimostrazione. Siano e le due velocità e la differenza. Durante la crescita additiva entrambe aumentano della stessa quantità per RTT, quindi non cambia. Quando la somma supera la capacità, entrambe subiscono una perdita e si dimezzano: diventa . Dopo perdite la differenza vale , che tende a zero, mentre la somma continua a oscillare attorno alla capacità. ∎

Con una crescita moltiplicativa e una diminuzione additiva la differenza crescerebbe invece di calare. Connessioni con RTT diversi non sono trattate allo stesso modo: chi è più vicino cresce più in fretta e ottiene di più.

Le varianti moderne

Sulle reti veloci e lontane la crescita di un pacchetto per RTT è troppo lenta. CUBIC, predefinito in Linux, fa crescere la finestra secondo una funzione cubica del tempo dall’ultima perdita, indipendente dall’RTT. BBR, sviluppato da Google, non aspetta le perdite: stima la banda del collo di bottiglia e l’RTT minimo, e trasmette alla velocità stimata, tenendo le code corte. Il protocollo QUIC, su cui si basa HTTP/3, porta queste funzioni sopra UDP, insieme alla crittografia, per poterle aggiornare senza toccare il sistema operativo.