# Controllo della congestione in TCP

In telecomunicazioni e informatica il controllo della congestione in TCP è una funzionalità di controllo di trasmissione da parte di TCP che permette di limitare la quantità di dati trasmessi sotto forma di pacchetti e non ancora riscontrati dal mittente, adattando il flusso dati inviato all'eventuale stato di congestione della rete. Tale stato è desunto indirettamente a partire da informazioni ricavabili dallo stato della trasmissione dei pacchetti da parte di un terminale, evitando così congestione nella rete stessa.

## Descrizione

Il protocollo di trasporto Transmission Control Protocol o TCP attua il controllo della congestione congiuntamente al controllo di flusso. Di contro, il protocollo di trasporto User Datagram Protocol o UDP non implementa alcuna forma di controllo di flusso o della congestione; se necessarie, queste funzionalità possono essere realizzate al livello applicazioni.
Il modello fondamentale di controllo della congestione implementato in TCP prevede che la rilevazione della congestione sia effettuata agli estremi della comunicazione/connessione, e non richiede nessun supporto da parte dei router intermedi per realizzare questa funzione. Questo è coerente con il modello progettuale di IP, che prevede di aggiungere "intelligenza", ovvero funzioni di elaborazione ai nodi terminali lasciando ai router mansioni meno complesse e proprie del livello di rete.
Alcune versioni avanzate del protocollo TCP, però, prevedono anche una collaborazione da parte dei router al meccanismo di controllo della congestione del TCP. Ad esempio:
* la variante di TCP con Random Early Detection (RED) prevede che i router controllino il livello di riempimento delle proprie code e, nell'imminenza di una congestione, eliminino uno dei pacchetti in coda, per indurre un rallentamento delle sorgenti TCP;
* la variante di TCP con Explicit Congestion Notification (ECN) prevede che i router settino probabilisticamente ad uno un bit nella intestazione dei pacchetti IP inoltrati quando il livello di riempimento di una coda supera una soglia prefissata, per indurre un rallentamento delle sorgenti TCP.

### Finestra di congestione

Il controllo di congestione del TCP si basa sul fatto che le due entità messe in comunicazione dal TCP si scambiano pacchetti contenenti dati e pacchetti di riscontro (ACK), che viaggiano nel verso opposto rispetto ai dati.
In assenza di perdite di pacchetti, il tempo che intercorre tra l'invio di un segmento (dall'host A all'host B) e la ricezione del relativo riscontro (inviato dall'host B all'host A) definisce il cosiddetto Round Trip Time (o RTT). In presenza di congestione nella rete, le code nei router diventano più lunghe, e questo fa aumentare il ritardo subito dai pacchetti e dai relativi riscontri, e quindi l'RTT. Il meccanismo di controllo della congestione implementato in TCP rileva l'approssimarsi della situazione di congestione nelle entità terminali delle connessioni TCP ed impone a ciascun mittente un limite alla velocità di invio dei pacchetti in funzione della congestione di rete percepita. Tale limite è rappresentato da una variabile, detta cwnd (Congestion Window, ovvero finestra di congestione), il cui valore impone un limite superiore alla quantità di dati trasmessi e non ancora riscontrati dal mittente, ovvero i dati che, essendo stati consegnati per la trasmissione al livello di rete, sono in viaggio sulla rete o in fase di elaborazione della entità TCP attiva sul nodo destinazione, o i cui ACK sono a loro volta in viaggio sulla rete stessa.
In TCP, il meccanismo di controllo di congestione funziona insieme al controllo di flusso, che, dal canto suo, impone un limite superiore alla quantità di dati trasmessi e non ancora riscontrati dal mittente attraverso un'altra variabile, detta rwnd (Receiver Window ovvero "finestra del ricevitore"), il cui valore è comunicato al mittente direttamente dal ricevitore, in un apposito campo dell'intestazione TCP. Pertanto, la quantità di dati non riscontrati dal mittente non può essere superiore al minimo tra i valori di cwnd e rwnd, ovvero:
    $LastByteSent-LastByteAcked<=min(cwnd,rwnd)$
I due meccanismi (controllo di flusso e controllo di congestione) impongono due distinti limiti superiori alla quantità LastByteSent - LastByteAcked. Il più piccolo tra i valori di cwnd e rwnd determina quale tra i due meccanismi sia l'effettivo "fattore limitante" del tasso di trasmissione.
In TCP il mittente regola costantemente cwnd a seconda del livello di congestione di rete rilevato, in tal modo modulando il tasso di trasmissione dei pacchetti inviati. Se il mittente rileva che sul percorso di invio dei pacchetti c'è assenza di congestione, incrementa il valore di cwnd, viceversa se rileva segnali di congestione, lo riduce.
Un mittente TCP può rilevare la presenza di congestione della rete quando si verificano eventi che sono sintomi della perdita di pacchetti, ad esempio:
* scadenza di un time-out a causa della mancata ricezione di ACK;
* ricezione di pacchetti di ACK con lo stesso numero di sequenza (ACK duplicati), che manifestano la presenza di un "buco" nella sequenza di pacchetti ricevuti.
Supponendo che un host A invii pacchetti TCP (segmenti) ad un host B all'inizio di ogni RTT (Round Trip Time), nell'ipotesi che sia cwnd < rwnd, il vincolo consente al mittente di trasmettere cwnd byte sulla propria connessione; al termine dell'RTT il mittente riceve il riscontro dei dati. Da ciò si evince che la frequenza di invio del mittente è cwnd/RTT byte/sec, quindi il mittente può regolare la frequenza di invio di segmenti sulla propria connessione modificando il valore di cwnd.

## Algoritmo

L'algoritmo di controllo di congestione presenta due fasi:
* Partenza Lenta (slow start)
* Aumento Additivo Diminuzione Moltiplicativa (Additive Increase Multiplicative Decrease)
Per distinguere tra le due fasi viene usata una variabile chiamata ssthresh (slow start threshold). Quando il valore della cwnd è minore del valore di ssthresh ci troviamo nella fase di slow start, altrimenti siamo nella fase AIMD. All'avvio della trasmissione la variabile viene settata ad un valore molto alto, mentre la dimensione della cwnd è pari alla dimensione di un segmento.
La versione Reno inoltre ha una terza fase detta ripresa veloce (Fast Recovery).

### Slow start

Durante la fase di partenza lenta (in inglese, slow start) la finestra di congestione cwnd viene impostato di default ad 1 (il che comporta una velocità di invio iniziale di circa MSS/RTT) e il mittente TCP inizia trasmettendo il primo segmento dati, attendendo un riscontro. La cwnd aumenta di una quantità pari al MSS per ciascun segmento che, dopo esser stato trasmesso, viene riscontrato (si riceve un ACK). Quindi ad ogni RTT la cwnd raddoppia di dimensioni (e conseguentemente ne raddoppia anche la velocità trasmissiva).
La fase di slow start viene mantenuta fintanto che non si incorre in un evento di congestione, come la perdita di un segmento dati, oppure quando la dimensione della finestra di congestione raggiunge o supera il valore della variabile ssthresh, evento che conduce alla fase di aumento additivo - diminuzione moltiplicativa (AIMD), o infine nel caso in cui vengono identificati tre segmenti riscontrati duplicati. In tal caso il mittente TCP pone cwnd ad 1 ed inizia di nuovo il processo di Slow Start. Inoltre pone il valore di ssthresh a cwnd/2.
Successivamente si passa all'algoritmo di Congestion Avoidance (quando cwnd >= ssthresh) oppure Fast Recovery (quando vengono identificati tre segmenti riscontrati duplicati).

### AIMD

Durante la fase AIMD si ha un incremento additivo lineare del valore di cwnd di 1 MSS ogni RTT. Ciò si può ottenere attraverso l'incremento da parte del mittente della propria cwnd di una quantità di byte pari a:
    $MSS*(MSS/cwnd)$
ogni volta che giunge un nuovo riscontro. Tale comportamento viene detto Additive Increase o anche Congestion Avoidance. Il termine Multiplicative Decrease si riferisce al comportamento messo in atto dal mittente alla ricezione di tre ACK duplicati consecutivi (con lo stesso numero di riscontro): la variante TCP Reno, in questa circostanza, imposta il valore di SSTRESH a cwnd/2 e assegna a cwnd tale valore incrementato di 3 MSS. Se la congestione diventa eccessiva, uno o più buffer dei router lungo il percorso vanno in overflow, causando l'eliminazione di un datagramma IP che contiene un segmento TCP. Rilevato questo evento allo scadere di un timeout di ritrasmissione, TCP reagisce dimezzando il valore di ssthresh e reimpostando cwnd alla dimensione di un segmento, tornando quindi nella fase di slow start.

## Politiche per il controllo della congestione

Gli eventi che indicano al mittente la perdita di dati trasmessi sono:
* ACK non riscontrati allo scadere del timer (time-out).
* ACK duplicati ricevuti 3 volte.
Versioni differenti del protocollo TCP implementano gli algoritmi di controllo della congestione in maniera diversa. Nel seguito si descrivono due varianti principali: la versione TCP Tahoe, che non distingue tra gli eventi sopra elencati, e la versione TCP Reno, che reagisce ai due eventi in maniera differente.

### TCP Tahoe

TCP Tahoe prevede che ogni qual volta si verifichi un evento perdita (o evento di congestione) di qualsiasi tipo, la finestra di congestione venga dimezzata e questo nuovo valore viene memorizzato nella variabile soglia ssthresh. Fatto questo la trasmissione dei dati ricomincia impostando il valore iniziale della finestra di congestione corrente pari ad 1 MSS (massima dimensione di un segmento TCP). Si ha quindi una "ripartenza lenta" o Slow Start, ovvero la crescita della finestra di congestione avviene progressivamente (seguendo un trend esponenziale nel tempo) fino a raggiungere il valore di soglia prima determinato. Oltre questo valore la crescita avviene linearmente nel tempo secondo la modalità AIMD descritta sopra, fino a quando non si verifica nuovamente un evento perdita e si riparte dalla fase Slow Start. È importante sottolineare come la riduzione della finestra di congestione ad 1 MSS comporti una repentina riduzione della velocità di trasmissione dei dati nella connessione TCP.
Questo effetto, da un lato, de-congestiona la rete, ma, dall'altro, limita temporaneamente (ma fortemente) la velocità di trasmissione/ricezione dei dati. Pertanto, la crescita esponenziale fino al livello di soglia consente alla connessione TCP di recuperare prontamente (ma parzialmente) una parte della banda ormai persa in seguito all'evento di congestione. Una volta raggiunto il livello di soglia, la crescita avviene lentamente per sondare il livello di banda effettivamente disponibile in rete e cercare di raggiungere nuovamente il livello di congestione il più lentamente possibile.
Si riporta la descrizione di come l'algoritmo di controllo di congestione in TCP Tahoe modifica il valore corrente di cwnd.
* Evento "ACK ricevuto":
    ${\mbox{se }}cwnd<ssthresh{\mbox{ allora }}cwnd=2*cwnd$ (Slow Start)
    ${\mbox{altrimenti }}cwnd=cwnd+1/cwnd$ (AIMD)
* Evento "Timeout scaduto" oppure "Tre ACK duplicati ricevuti":
    $ssthresh=cwnd/2$
    $cwnd=1MSS$
    Continua dalla fase Slow Start.

### TCP Reno

TCP Reno reagisce in maniera diversa ai due eventi che segnalano la possibile perdita di un pacchetto dati. L'evento timeout scaduto viene considerato un indicatore "forte" di congestione, e pertanto, TCP Reno, così come TCP Tahoe, fa ripartire la fase di Slow Start da un valore di cwnd pari ad 1 MSS:
* Evento "Timeout scaduto":
    $ssthresh=cwnd/2$
    $cwnd=1MSS$
    Continua dalla fase Slow Start.
L'evento tre ACK duplicati, invece, viene considerato un indicatore "debole" di congestione, perché sintomatico del fatto che comunque la rete ha consegnato ulteriori pacchetti, dopo un pacchetto probabilmente perso. Pertanto, in TCP Reno questa circostanza produce la ritrasmissione veloce (Fast Retransmit) del segmento che contiene i dati già trasmessi per i quali non è ancora arrivato il riscontro, senza attendere lo scadere del relativo timeout
* Evento "Tre ACK duplicati":
    $ssthresh=cwnd/2$
    $cwnd=ssthresh+3MSS$
    Continua come nella fase AIMD.
(Nell'immagine sotto c'è un errore, la 3° threshold di Tahoe dovrebbe essere a 5=10/2, non 4, e quindi il raddoppio di Slow Start andrebbe fatto una volta in più)

### TCP New Reno

TCP Reno risolve in parte il problema di perdite non dovute a congestione solo quando le perdite non sono fortemente correlate tra loro, cioè quando si perde al massimo un pacchetto all'interno di ogni finestra. Questo comportamento è problematico nelle situazioni in cui si perdono interi burst di pacchetti (situazione frequente ad esempio nei collegamenti wireless). Infatti, in questi casi TCP Reno potrebbe ridurre il valore della finestra di congestione più volte consecutivamente (ovvero tante volte quanti sono i pacchetti persi) causando un drastico peggioramento della velocità di trasmissione della connessione TCP.
TCP New Reno cerca di aggirare il problema basandosi sul sistema degli ACK parziali. Vengono considerati ACK parziali gli ACK che riscontrano pacchetti intermedi, e non gli ultimi pacchetti che necessiterebbero riscontro, dopo che è stata già iniziata la fase di Fast Recovery in seguito all'arrivo di tre ack duplicati. Quando uno di questi ack si presenta durante una fase di Fast Recovery (cioè in seguito alla ricezione di 3 ack duplicati), TCP New Reno si mantiene in tale fase continuando a reinviare i pacchetti via via richiesti finché non viene riscontrato l'ultimo pacchetto inviato nella fase precedente all'ingresso in Fast Recovery.

### TCP Bottleneck Bandwidth and Round trip-time (BBR)

Il TCP BBR è un algoritmo del controllo della congestione studiato da Google nel 2016. La particolarità di questo algoritmo è il fatto di NON essere basato sulle perdite ma di essere rate-based. In particolare, BBR non stima il modello della rete grazie alle perdite ma grazie alla stima di due parametri: RTT di propagazione e Bottleneck Bandwidth.

## Gestione del Retransmission Timeout

Nelle precedenti sezioni si è visto come il timeout per la gestione delle ritrasmissioni (Retransmission Timeout o RTO) sia utilizzato negli algoritmi di controllo di congestione del TCP. Tuttavia è anche importante spiegare a quale valore e secondo quali modalità l'RTO venga impostato dal TCP. A tal riguardo, si noti che condizione necessaria a garantire il corretto funzionamento del meccanismo di timeout sia quella di utilizzare un valore di RTO maggiore di RTT (RTO > RTT). La violazione di tale condizione infatti comporterebbe l'occorrenza di timeout spuri (ovvero di timeout espirati poiché troppo brevi rispetto al tempo impiegato ai riscontri per raggiungere il mittente dei dati). Tuttavia, il valore di RTT di una connessione TCP varia continuamente durante la trasmissione dei dati a causa dei ritardi di accodamento variabili che si riscontrano in rete. Questo comporta la necessità di impiegare un meccanismo per l'adattamento dinamico dell'RTO che possa quindi garantire il soddisfacimento della condizione RTO > RTT anche quando l'RTT varia nel tempo. Il TCP calcola il valore di RTO come segue:
    $RTO=SRTT+4*RTTVAR$
dove SRTT (smoothed round-trip time) rappresenta la media dei valori di RTT misurati e RTTVAR (round-trip time variation) una stima della deviazione standard della variabile RTT. Qualora si verifichino espirazioni del timer consecutive, il valore di RTO viene progressivamente raddoppiato.

## Equità

L'equità in una rete a commutazione di pacchetto misura in che modo la banda di una rete viene ripartita tra i flussi dati attivi. Nel caso di una rete composta da un unico collegamento a collo di bottiglia avente banda pari a R bps, condiviso da K connessioni TCP, la perfetta equità corrisponde ad una ripartizione uniforme della banda R tra le K connessioni attive. In altre parole, la perfetta equità viene raggiunta se ciascuna delle K connessioni TCP ottiene a regime una velocità media di trasmissione dei dati pari a R/K. Nel caso del TCP, questa condizione può verificarsi solo quando le K connessioni presentano lo stesso RTT (Round Trip Time). Infatti, la velocità media di trasmissione dei dati di una connessione TCP è inversamente proporzionale al suo RTT. Queste considerazioni sono valide in presenza di applicazioni persistenti, ovvero in grado di trasmettere senza interruzioni quantità di dati teoricamente infinita.