Controllo della congestione in TCP

TCP impone ad ogni mittente un limite alla velocità di invio in funzione della congestione di rete percepita.

Come viene ridotta la velocità?

Abbiamo visto che il mittente TCP tiene conto di alcune variabili: rwnd, lastByteRead. Oltre a questi si aggiunge una nuova variabile di cui si tiene traccia: cwnd ovvero congestion window.

Per concentrarci sulla congestione, assumiamo che il buffer sia capiente abbastanza da poter ignorare il vincolo della finestra di ricezione (rwnd).
Assumiamo anche il mittente abbia sempre dati da inviare e che, quindi, la finestra di congestione sia sempre in uso.
La velocità trasmissiva viene limitata solo indirettamente. Per rendercene conto consideriamo una connessione con perdita di pacchetti e ritardi trascurabili.
All’inizio di ogni RTT, la grandezza di cwnd consente al mittente di inviare cwnd byte di dati.
Quindi la velocità di invio è: Modificando cwnd il mittente può regolare la velocità.

Vediamo come si accorge il mittente che la rete è congestionata.
Definiamo evento di perdita per il mittente TCP come l'occorrenza di un timeout o la ricezione di tre ACK duplicati da parte del destinatario. In presenza di una congestione eccessiva, uno o più buffer dei router lungo il percorso vanno in overflow causando l'eliminazione di un datagramma (che contiene un segmento TCP) che costituisce l'elemento di perdita presso il mittente che lo considera come un'indicazione di congestione sul percorso tra sé e il destinatario.

Consideriamo un caso ottimistico: la rete non è congestionata, non si perdono pacchetti, gli ACK inviati dal ricevente vengono ricevuti dal mittente. Il mittente vede che tutto va bene e aumenta la grandezza di cwnd. Se gli ACK arrivano lentamente, la crescita di cwnd è lenta. Se gli ACK non arrivano cwnd diminuisce. Si dice per questo che TCP è auto-temporizzato.

Come determinano i mittenti TCP la grandezza di cwnd, senza essere troppo cauti (e sottoutilizzando la rete) o troppo poco cauti (sovraccaricandola e congestionandola)?

  • Un segmento perso implica congestione, quindi i tassi di trasmissione TCP devono essere regolati in base alla perdita. Viene perso un pacchetto allora cwnd va diminuita.
  • Gli ACK ricevuti indicano che la rete sta funzionando bene e cwnd può essere aumentato se non arrivano ACK duplicati.
  • Rilevamento della larghezza di banda. TCP all’inizio del trasferimento, aumenta la cwnd fino a congestionare la rete ed in modo da rendersi conto del limite della rete. Poi rallenta e ricomincia la fase di rilevamento del limite, per capire se può spingersi oltre o no.

Possiamo entrare nel merito ora dell’algoritmo di controllo della congestione di TCP composto di tre fasi:

  1. Slow start
  2. Congestion avoidance
  3. Fast recovery

Slow start
...

Quando si stabilisce una connessione TCP, il valore di cwnd, viene inizializzato a 1 MSS, il che comporta una velocità di invio iniziale di circa MSS/RTT. Se MSS = 500 byte e RTT = 200 ms, la velocità iniziale è solo di circa 20 kbps. La cwnd incrementa di 1 MSS la finestra per ogni pacchetto che riceve ACK.
Pasted image 20230929153819.png
cwnd in A, all'inizio è uguale a 1 MSS (Maximum Segment Size).
Se A riceve ACK prima che si verifichi una perdita: raddoppia la dimensione di cwnd, che diventa di 2 MSS, poi 4 MSS, ecc.
Come dice il termine stesso di questa fase, abbiamo una slow start (un inizio lento), tuttavia raddoppiando di volta in volta la dimensione di cwnd la crescita sarà esponenziale.
Nel caso in cui si verifica una perdita, cwnd viene nuovamente impostato a 1 MSS, facendo ripartire la fase di slow start, quando si verifica una perdita si prende nota di un valore che prende il nome di ssthresh (slow start threshold, limite di slow start), tale valore sarà settato a La prossima volta, TCP sa che quando cwnd raggiunge il valore di ssthresh raddoppiare diventa rischioso poiché potrebbe causare delle perdite. Slow start termina e si passa alla fase di congestion avoidance. Slow start termina anche quando si verifica la ricezione, da parte del mittente, di tre ACK duplicati, in tal caso TCP opera la fase di retransmission.

Congestion avoidance
...

Quando TCP entra in questa fase il valore di cwnd è circa la metà di quella che aveva l'ultima volta che ha registrato una congestione di rete. A questo punto anziché raddoppiare il suo valore, adotta un approccio più conservativo, incrementando la cwnd di 1 MSS ogni RTT. Questo risultato si può ottenere in diversi modi: un approccio comune è l'incremento da parte del mittente TCP della propria cwnd di: byte ogni qualvolta riceva un ACK.
Per esempio, se MSS vale 1460 byte e cwnd vale 14600 byte: vuol dire che in un RTT vengono spediti 10 segmenti dal mittente ().
Eseguendo i conti: risulta che cwnd incrementa ad ogni ACK di 1/10. Ricevendo 10 ACK, cwnd incrementa di 1 MSS.

Quando si verifica una perdita congestion avoidance si comporta come slow start. Ovvero il valore di ssthresh viene impostato al valore di cwnd trovato quando si è verificata la perdita diviso due e la cwnd viene impostata a 1 MSS. Questo avviene quando si verifica il timeout (caso grave di congestione). Quando si ricevono tre ACKs duplicati: cwnd viene dimezzata (aggiungendo 3 MSS per tenere conto degli ACK duplicati ricevuti) e imposta ssthresh alla metà di cwnd risultante al momento della ricezione dei tre ACK duplicati. Infine TCP entra nella fase di fast recovery.

Fast recovery
...

Durante questa fase il valore di cwnd viene incrementato di 1 MSS per ogni ACK duplicato ricevuto relativamente al segmento perso che ha causato l'entrata di TCP in fast recovery. Infine quando arriva un ACK per il segmento perso, TCP entra nello stato di congestion avoidance dopo aver ridotto il valore di cwnd. Se si verifica un timeout invece, dallo stato di fast recovery si passa a slow start: cwnd = 1 MSS e ssthresh = cwnd/2 nel momento in cui si è verificata la perdita (relativa al timeout scaduto). Fast recovery è raccomandato, ma non obbligatorio per chi implementa TCP.
Una prima versione di TCP: TCP Tahoe, portava in modo incondizionato la finestra di congestione a 1 MSS ed entrava nella fase di slow start dopo qualsiasi evento di perdita. La versione più recente invece adotta fast recovery (TCP Reno).

Di seguito la macchina a stati del sistema di controllo della congestione di TCP:
Pasted image 20230929161551.png

Retrospettiva sul controllo della congestione
...

La forma di controllo di congestione di TCP è chiamata incremento additivo, decremento moltiplicativo per ovvie ragioni (Additive Increment Multiplicative Decrement). Sono state proposte diverse versione di TCP nel tempo.
L'algoritmo Vegas per esempio tenta di predire l'imminente perdita di un pacchetto basandosi sul RTT, più esso è maggiore, maggiore sarà la congestione nei router. Quando viene predetta, Vegas abbassa linearmente la velocità di trasmissione (non viene dimezzata).

In un grafico di analisi del comportamento di TCP, notiamo che si comporta a dente di sega:
Pasted image 20230929161805.png
Se l'ampiezza della finestra di TCP è di byte la frequenza trasmissiva è approssimativamente: . TCP va alla ricerca di banda aggiuntiva incrementando di 1 MSS, ad ogni RTT fino al verificarsi di un evento di perdita.
Detto il valore di cwnd quando si verifica una perdita.
E assumendo che RTT e siano approssimativamente costanti per la durata della connessione.
La velocità TCP varia tra: Il throughput medio di una connessione è:

Fairness
...

Consideriamo connessioni TCP diverse che passano tutte attraverso un collegamento con capacità trasmissiva bps che è il collo di bottiglia. Ovvero gli altri collegamenti non sono congestionati. Ogni connessione trasferisce file di grandi dimensioni e supponiamo che non ci sia traffico UDP attraverso il collo di bottiglia. Il quesito è: l'algoritmo AIMD del controllo di congestione di TCP è fairness (equo)? Ovvero la velocità trasmissiva media per ogni connessione è (circa)? La risposta è si.

Esempio: consideriamo il caso più semplice in cui ci sono due connessioni TCP che condividono un collegamento con capacità trasmissiva . Assumiamo che le connessione abbiano gli stessi valori di MSS e RTT (e pertanto abbiano stesse finestre di congestione e stesso throughput), che debbano trasmettere tanti dati e che non vi siano altre connessioni TCP o datagrammi UDP che attraversano questo collegamento. Ignoriamo la fase di slow start e supponiamo di trovarci già nella fase di congestion avoidance per tutto il tempo.
Pasted image 20230929162645.png
Pasted image 20230929162653.png
Il grafico sopra traccia il throughput delle due connessioni.
Se TCP sta suddividendo la larghezza di banda del collegamento in modo uguale tra le due connessioni, allora il throughput dovrebbe cadere sulla bisettrice del primo quadrante. Idealmente la somma dei due throughput dovrebbe essere uguale a .
L'obiettivo dovrebbe essere ottenere throughput situati vicino all'intersezione tra la bisettrice e la linea di massimo utilizzo della banda.

Chiarimento

La linea di pieno utilizzo della banda vuol dire che alla sinistra della linea, la banda non è sfruttata al massimo, in corrispondenza della linea la banda è sfruttata a pieno, alla destra della linea la banda non è sufficiente (e si verificheranno delle perdite).

Supponiamo che le dimensioni della finestra TCP siano tali che a un certo istante di tempo le connessioni 1 e 2 raggiungono i throughput corrispondenti al punto A del grafico.
In tale punto, la banda utilizzata dalle due connessioni, sono inferiori al limite di pieno utilizzo, non si verificheranno accodamenti o perdite, per cui le due connessioni aumenteranno la loro finestra di 1 MSS per RTT per congestion avoidance.
Fino a che non si verificano perdite avverrà l'aumento di 1 MSS, quando ci si avvicina alla line di pieno utilizzo, o la si supererà, allora ad un certo punto si verificheranno anche delle perdite. A quel punto (B, nel grafico), le due connessioni decrementeranno le loro finestre di un fattore 2, trovandosi nel punto C.
In questo punto, siamo sotto il limite di pieno utilizzo, non ci saranno perdite e le connessioni aumenteranno di 1 MSS ad ogni RTT, fino a giungere in D, dove si verificheranno delle perdite e le finestre vengono dimezzate, trovandosi in un punto E (non presente in figura), sempre più vicino alla bisettrice.
A questo punto dovreste essere convinti che il throughput delle due connessioni oscilleranno nei pressi della bisettrice. Dunque a prescindere dal punto in cui le connessioni si trovano all'inizio, ad un certo punto convergeranno verso la bisettrice, un punto di equa condivisone del traffico tra le due connessioni TCP.
TCP è fairness.

Fairness e UDP
...

UDP non ha un controllo della congestione.
Non è fairness. Le applicazioni multimediali usano UDP proprio perché preferiscono perdere pacchetti piuttosto che ridurre il loro tasso trasmissivo. Le applicazioni UDP non sono fair, ovvero non cooperano con le connessioni TCP. Per questo motivo le connessioni TCP possono essere soffocate dalle connessioni UDP.