“TCP Congestion Control Demystified”

Angelo Dell'Aera

<buffer@antifork.org>

Metro Olografix Camp - Pescara, Agosto 2004

La storia del TCP/IP è
la storia di UNIX...

Nel 1983 ha inizio la storia del TCP/IP con il rilascio di 4.2 BSD da parte del Computer Systems Research Group (CSRG) di Berkeley. Infatti, 4.2 BSD include la prima release della suite di protocolli nonchè il supporto per l'API socket.

Le ultime release del sistema operativo di Berkeley hanno fortemente influenzato la scrittura dello stack TCP/IP di Linux (almeno fino al kernel 2.2.x) e sono tuttora alla base delle implementazioni presenti in FreeBSD, OpenBSD e NetBSD.

4.3 BSD

Nel 1986, viene rilasciato 4.3 BSD che contiene alcuni miglioramenti notevoli soprattutto per quanto riguarda l'API socket.

Ma, sfortunatamente, all'epoca Internet era una rete di dimensioni troppo modeste perchè ci si potesse rendere conto che un aspetto estremamente importante era stato trascurato. Ma, dopo pochi mesi, un evento evidenziò a tutti la dura realtà.

Van Jacobson e 4.3 BSD Tahoe

Nel 1988 viene pubblicato un articolo di Van Jacobson dal titolo “Congestion Avoidance and Control”. Nella prima parte dell'articolo, l'autore descrive di aver osservato per la prima volta nella storia dell'infanta Internet un fenomeno di congestione della rete.

Intuite le ragioni che portarono a questo fenomeno, l'autore propose una soluzione che, seppure con alcune varianti, viene usata anche nelle implementazioni odierne. Questa soluzione viene inclusa in 4.3 BSD Tahoe, rilasciato nel 1988.

4.3 BSD Reno

Nel 1990 viene rilasciato 4.3 BSD Reno che include una versione riveduta e corretta dell'algoritmo proposto da Van Jacobson. Esso inoltre includeva altri algoritmi sviluppati da Van Jacobson quali fast recovery, TCP header prediction e SLIP header compression. Inoltre, 4.3 BSD Reno modificava in modo molto significativo la gestione delle routing table.

Spesso si sente parlare di TCP Reno a dimostrazione di quale sia l'importanza di questa implementazione per la comunità.

4.4 BSD

Nel 1993 viene rilasciato 4.4 BSD che include il supporto per il multicasting e le TCP Extensions for High Performance come stabilito dall'RFC1323.

Da 4.4 BSD sono stati ricavati 4.4 BSD-Lite (1994) e 4.4 BSD-Lite2 (1995), che possono essere ritenuti i genitori di sistemi operativi quali BSD/OS, FreeBSD, OpenBSD e NetBSD. Le implementazioni del TCP/IP di questi sistemi operativi sono spesso definite Berkeley-derived implementations.

Linux

Linux vede la luce nel 1991 ed è fortemente influenzato da Solaris, una versione commerciale di UNIX sviluppata da Sun Microsystems.

Fino alla versione del kernel 0.93, lo stack TCP/IP di Linux era implementato in maniera pietosa. In quella data, un giovane e squattrinato programmatore inglese di nome Alan Cox iniziò a riscrivere from scratch l'intero codice di networking e, in qualche mese, pose le basi per quello che sarebbe stato lo stack TCP/IP fino alla versione del kernel 2.2.x (attualmente ancora mantenuto).

Linux

Il kernel 2.4 e il recente 2.6 presentano al momento l'implementazione più performante, completa e allo stesso tempo innovativa del codice di networking presente sulla piazza.

Questo è dovuto a molti motivi. Prima di tutto, il design del codice è semplicemente eccezionale e il merito di questo è da attribuire quasi completamente a David S. Miller, attuale maintainer del codice di networking.

Linux

Inoltre Linux è praticamente l'unico sistema operativo che dispone di meccanismi di sincronizzazione e granular locking su architetture SMP realmente in grado di definirsi tali.

Inoltre, chiunque abbia mai studiato l'implementazione dei softirqs sa quali potenziali performance siano ottenibili con un approccio simile...

Pensare poi che softnet sia il risultato di test commissionati da Microsoft a Mindcraft nel Marzo 1999 fa sorridere!

Il problema della congestione

Per comprendere a fondo le problematiche relative al problema della congestione, ipotizziamo uno scenario in cui un hop router debba realizzare il multiplexing di pacchetti provenienti da più sorgenti su un unico link condiviso. Al momento, non facciamo alcuna ipotesi particolare sulla banda dei link coinvolti nello schema.

Il problema della congestione

Hop Router

Host 1

Host 2

Host 3

Il problema della congestione

In assenza di particolari queueing disciplines, l'hop router gestisce il traffico in entrata secondo una politica FIFO (First In First Out). Questa è la soluzione più semplice e consiste nell'analizzare ed eventualmente trasmettere i pacchetti nell'ordine in cui essi arrivano al router.

Si può intuire inoltre che è assolutamente necessario prevedere un input buffer per un corretto funzionamento del router.

Il problema della congestione

Quando l'hop router riceve un pacchetto lo memorizza nell'input buffer e, quando arriverà il suo turno, lo processerà routandolo in base alla sua routing table.

Fino a quando c'è spazio nell'input buffer è facile capire che il meccanismo funziona molto bene in quanto il meccanismo di buffering tra l'altro aumenta il throughput del dispositivo in quanto tale.

Il problema della congestione

Ma nel caso in cui l'input buffer sia ormai pieno e un altro pacchetto arrivasse al router come dovrebbe comportarsi il router? Può scartare il pacchetto o deve prendere qualche accorgimento per gestire questa situazione?

Un buon conoscitore della suite di protocolli TCP/IP affermerebbe senza indugi che l'hop router può e deve scartare il pacchetto indipendentemente dal flusso cui esso appartiene o da quanto importante esso sia.

Il problema della congestione

Ipotizzando una drop policy di tipo drop tail, il pacchetto da droppare in questo caso sarà l'ultimo ricevuto, ossia quello che non trova spazio disponibile nell'input buffer.

E' importante non confondere la queueing discipline con la drop policy in quanto essi sono concetti fondamentalmente diversi. Non scenderemo nei dettagli della questione in questa sede.

Il problema della congestione

Arriving packet

Arriving packet

Next to transmit

Next free buffer

Il problema della congestione

A questo punto, si capisce che se gli host nello schema cominciassero a spedire senza alcun accorgimento sarebbe relativamente semplice saturare l'input buffer. E' facile capire che, in questa situazione, si avrebbe un utilizzo della rete molto al di sotto delle sue reali capacità. Questa situazione prende il nome di congestione ed è ragionevole pensare che essa vada evitata.

Prima dell'articolo di Van Jacobson, non vi era alcuna forma di congestion control implementata negli stack TCP/IP e quindi ogni host aveva la facoltà di trasmettere a un rate tale da “tramortire” i router lungo il path.

Il problema della congestione

D'altro canto, oltre ad evitare fenomeni congestivi, sarebbe auspicabile anche sfruttare la capacità della rete al pieno delle sue potenzialità. Infatti, se ogni host trasmettesse 10 bytes al minuto sicuramente si riuscirebbe ad evitare la congestione.... ma forse non sarebbe la maniera ottimale per sfruttare un link Gigabit!

Quindi l'obiettivo è chiaro. Un algoritmo di congestion control deve farmi sfruttare la rete al massimo delle sue potenzialità, garantendo che non si verifichino fenomeni congestivi e che, se proprio devono verificarsi, siano almeno abbastanza rari e soprattutto “risolvibili”.

Il problema della congestione

Nell'articolo “Congestion Avoidance and Control”, Van Jacobson propone una soluzione molto interessante. Questa soluzione rappresenta l' oggetto dell'RFC2581 “TCP Congestion Control” di Mark Allman, Vernie Paxton e W. Richard Stevens.

L'idea è di associare ad ogni connessione TCP due nuove variabili di stato ossia la congestion window (cwnd) e la slow start threshold (ssthresh), rappresentative dello stato della connessione.

Il problema della congestione

Cerchiamo di comprendere il significato di queste variabili.

cwnd rappresenta il massimo numero di pacchetti che l'host può avere in flight in quel determinato momento

ssthresh rappresenta una stima della banda disponibile del path

Cerchiamo di dare un significato a queste definizioni mediante un'analisi attenta della loro evoluzione durante la vita di una connessione.

Il problema della congestione

Inizialmente la capacità del path non è nota. Quindi, in base a quanto stabilito dall'RFC2581, si pone

cwnd = 1 (*)

ssthresh = valore arbitrariamente elevato (**)

(*) “The initial value of cwnd MUST be less than or equal to 2*MSS bytes and MUST NOT be more than 2 segments”

(**) Nelle implementazioni di Linux, FreeBSD, OpenBSD e NetBSD questo valore è fissato a 65535

Slow Start

Se cwnd < ssthresh, si dice che la connessione è in slow start phase. Per come sono scelti i valori iniziali delle variabili, si vede che una connessione parte sempre da questa fase.

RFC2581 afferma che “during slow start phase, a TCP increments cwnd by at most SMSS bytes for each ACK received that acknowledges new data”.

La realtà implementativa è appena diversa in quanto, durante questa fase, tutti i sistemi operativi incrementano cwnd di 1 per ogni ACK ricevuto che notifichi la ricezione di nuovi dati. Si nota che durante questa fase la crescita di cwnd è esponenziale.

Congestion Avoidance

Se cwnd > ssthresh la connessione si trova in congestion avoidance phase. Quando questo succede “cwnd is incremented by one full sized segment per RTT”. In questa fase, la crescita di cwnd è lineare.

Ma la domanda che dovrebbe sorgere adesso è :

“Come faccio a raggiungere la congestion avoidance phase se all'inizio cwnd vale 1 e ssthresh 65535 considerando che questi valori sono memorizzati tipicamente in variabili unsigned a 16 bit?”

TCP Congestion Control

La soluzione è semplice. A causa dell'incremento esponenziale di cwnd durante la slow start, ben presto si raggiunge una situazione in cui l'host spedisce un numero di pacchetti eccessivo causando un fenomeno congestivo.

Quando questo succede, un hop router dropperà uno o più pacchetti. Il TCP rileverà la perdita di questo pacchetto tramite il retransmission timer. Al riguardo, RFC2581 afferma testualmente quanto segue.

TCP Congestion Control

“When a TCP sender detects segment loss using the retransmission timer, the value of ssthresh MUST be set to no more than the value given in equation 3:

(3) ssthresh = max (FlightSize / 2, 2*SMSS)

As discussed above, FlightSize is the amount of outstanding data in the network. Furthermore, upon a timeout cwnd MUST be set to no more than the loss window, LW, which equals 1 full-sized segment (regardless of the value of IW). Therefore, after retransmitting the dropped segment the TCP sender uses the slow start algorithm to increase the window from 1 full-sized segment to the new value of ssthresh, at which point congestion avoidance again takes over.”

TCP Congestion Control

In questo modo, si ottiene in ssthresh una stima della capacità del path. Quindi, fino a quando, successivamente cwnd sarà al di sotto di questo valore, sarà opportuno farne aumentare il valore velocemente in modo da arrivare velocemente a spedire la giusta quantità di dati in base alla capacità del path (slow start).

Superato questo valore, si continua ad aumentare cwnd molto più lentamente in modo da continuare a fare probing della rete perchè le condizioni del path possono variare anche molto velocemente.

TCP Congestion Control

Citando ancora da RFC2581 : “A TCP receiver SHOULD send an immediate duplicate ACK when an out-of-order segment arrives. The purpose of this ACK is to inform the sender that a segment was received out-of-order and which sequence number is expected. From the sender's perspective, duplicate ACKs can be caused by a number of network problems. First, they can be caused by dropped segments. In this case, all segments after the dropped segment will trigger duplicate ACKs. Second, duplicate ACKs can be caused by the re-ordering of data segments by the network (not a rare event along some network paths [Pax97]).”

TCP Congestion Control

“The TCP sender SHOULD use the "fast retransmit" algorithm to detect and repair loss, based on incoming duplicate ACKs. The fast retransmit algorithm uses the arrival of 3 duplicate ACKs (4 identical ACKs without the arrival of any other intervening packets) as an indication that a segment has been lost. After receiving 3 duplicate ACKs, TCP performs a retransmission of what appears to be the missing segment, without waiting for the retransmission timer to expire. After the fast retransmit algorithm sends what appears to be the missing segment, the "fast recovery" algorithm governs the transmission of new data until a non-duplicate ACK arrives. The reason for not performing slow start is that the receipt of the duplicate ACKs not only indicates that a segment has been lost, but also that segments are most likely leaving the network (although a massive segment duplication by the network can invalidate this conclusion). In other words, since the receiver can only generate a duplicate ACK when a segment has arrived, that segment has left the network and is in the receiver's buffer, so we know it is no longer consuming network resources.”

TCP Congestion Control

“The fast retransmit and fast recovery algorithms are usually implemented together as follows.

1. When the third duplicate ACK is received, set ssthresh to no more than the value given in equation 3.

2. Retransmit the lost segment and set cwnd to ssthresh plus 3*SMSS. This artificially "inflates" the congestion window by the number of segments (three) that have left the network and which the receiver has buffered.

3. For each additional duplicate ACK received, increment cwnd by SMSS. This artificially inflates the congestion window in order to reflect the additional segment that has left the network.

4. Transmit a segment, if allowed by the new value of cwnd and the receiver's advertised window.

5. When the next ACK arrives that acknowledges new data, set cwnd to ssthresh (the value set in step 1). This is termed "deflating" the window.”

TCP Congestion Control

E' facile capire che questo modus operandi è senza dubbio corretto ma è sicuramente troppo conservativo per quanto riguarda il setting della ssthresh. Infatti, sia nel caso di retransmission timeout sia nel caso di fast recovery, questo valore viene aggiornato in maniera cieca al numero di outstanding packets diviso 2.

Questa scelta garantisce sicuramente stabilità all'algoritmo ma se l' update di ssthresh fosse legato a delle valutazioni e non ad una divisione per 2 (che per quanto corretta non ha valore teorico) forse si potrebbero ottenere delle performance migliori dal TCP.

Questa considerazione è alla base di tutte le varianti di TCP Reno tra cui anche TCP Westwood+.

Standard TCP (Van Jacobson)

time

ssthresh

cwnd

Congestion Avoidance

Timeout

Fast recovery

Exponential

increasing

Linear

increasing

Slow-start

La dinamica di cwnd segue il paradigma AIMD

TCP Reno - Known Drawbacks

Basso throughput su link wireless

(le perdite dovute all'inaffidabilità del link sono erroneamente interpretate come congestione)

Il throughput di TCP Reno è proporzionale a 1/RTT

(...TCP Reno non è fair?!)

Capacità del pipe

Host 1

Host 2

Indicando con RTT il round trip time e con Bandwidth la banda disponibile, è possibile esprimere la capacità del pipe come

Bandwidth * RTT

RTT

Inoltre, è possibile esprimere RTT come somma di due contributi

RTT = RTTdelay + RTT queue

Il primo contributo misura il tempo necessario affinchè il pacchetto si propaghi lungo il path mentre il secondo contributo è dovuto al fatto che il pacchetto è soggetto a queueing nelle code degli hop router durante la propagazione lungo il path.

E' intuitivo comprendere come il secondo termine dipenda fortemente dalle condizioni di congestione del path.

End-To-End Bandwidth
Estimation

L'idea di base di TCP Westwood+ è di utilizzare una stima di banda end-to-end allo scopo di settare adattativamente cwnd e ssthresh

invece di

realizzare una cieca multiplicative window decrease

TCP Westwood+

Congestion Avoidance

Slow start

cwnd

time

Timeout

ssthresh

BWE*RTTmin

Adaptive decrease

cwnd=ssthresh=BWE*RTTmin

End-To-End Bandwidth
Estimation

TCP Westwood+ è basato su una stima end-to-end della banda disponibile sul TCP connection path.

La stima è ottenuta filtrando lo stream degli ACK di ritorno e viene utilizzata per settare adattativamente la control window quando si verifica un episodio di congestione.

End-To-End Bandwidth
Estimation

ACKs

packets

Filter

RECEIVER

SENDER

Bandwidth

Estimate

ACKs

packets

Network

TCP Westwood+
Pseudo Code

Quando 3 DUPACKs sono ricevuti dal sender

ssthresh=max(2, (BWE*RTTmin) / MSS);

cwnd = ssthresh;

Quando scatta il coarse timeout

ssthresh=max(2, (BWE*RTTmin) / MSS);

cwnd = 1;

Quando gli ACKs vengono ricevuti normalmente

cwnd viene incrementata come stabilito in RFC2581;

viene valutata la stima di banda end-to-end BWE;

TCP Westwood+

TCP Westwood+ adotta un paradigma di tipo Additive Increase Adaptive Decrease (AIAD).

TCP Westwood+ migliora la stabilità dell'algoritmo standard di multiplicative decrease del TCP.

La congestion window viene decrementata maggiormente in presenza di fenomeni congestivi di entità rilevante e meno in presenza di fenomeni congestivi più lievi.

TCP Westwood+

Il setting adattativo delle control windows incrementa la fairness nell'allocazione della banda disponibile a differenti flussi TCP.

Settare cwnd a BWE*RTTmin sostiene un rate di trasmissione pari a ((BWE*RTTmin)/RTT) più piccolo della banda stimata nell'istante in cui si rileva la presenza di un fenomeno congestivo. Questo fa sì che flussi coesistenti possano usufruire di spazio nei buffer dei router creato da tale rate di trasmissione.

Tutto ciò incrementa fairness e statistical multiplexing.

Warning…

Gli ACKs raggiungono il sender TCP compressi

Bandwidth samples

Essi contengono componenti ad alta frequenza che non possono essere filtrati da un filtro passa-basso tempo discreto a causa del fenomeno dell'aliasing

Effetti dell'ACK compression

Gli ACK pairs forniscono informazioni circa la banda dell'ultimo link attraversato sul backward path.

Per filtrare l'effetto dell'ACK compression, TCP Westwood+ accumula gli ACK in un periodo pari a un RTT e successivamente si va a valutare un bandwidth sample.

End-To-End Bandwidth Estimate

TCP

Westwood+

Internet

Anti ACK

compression

Low pass

filter

Segments sent

Returning ACKs

BWE

Un filtro anti-aliasing nelle packet networks?!

Antialiased samples

ACK compression

A seguito di un'attenta analisi, abbiamo concluso che l'ACK compression ha effetti molto importanti sul comportamento del TCP.

Il fenomeno dell'ACK compression deve essere assolutamente considerato in fase di simulazione.

Attualmente si utilizza un classico filtro passa-basso del primo ordine tempo-discreto a coefficienti costanti

Bandwidth Estimation

TCP Westwood utilizza un bandwidth sample valutato ad ogni ACK (bandwidth overestimate in presenza di ACK compression).

TCP Westwood+ utilizza un bandwidth sample per ogni RTT.

Topologia con effetti di ACK compression
(10 Mbps)

20 TCP

R

R

Sink

10 TCP

Sinks

10 TCP

Connections

Reverse traffic:

10 TCP long-lived NewReno connections

Forward traffic:

20 TCP Westwood connection

Le 20 connessioni TCP Westwood+ stimano una banda disponibile best-effort che approssima ragionevolmente il fair share di 0.5Mbps

TCP Westwood sovrastima fino a 100 volte il fair share a causa dell'ACK compression

Implementazione di TCP Westwood+
in Linux

L'implementazione del TCP di Linux (kernel 2.4 e 2.6) supporta l'algoritmo di congestion control denominato Rate-Halving.

L'algoritmo di Rate-Halving consente di ottenere un effettivo dimezzamento del rate di trasmissione quando si verifica un episodio di congestione senza compromettere il self-clocking.

Implementazione di TCP Westwood+
in Linux

L'algoritmo di Rate-Halving consente di ottenere questo obiettivo facendo in modo che, durante la fase di Fast Recovery/Fast Retransmit, non ci siano inflating e deflating della finestra ma preoccupandosi di trasmettere un segmento per ogni due duplicate ACK ricevuti.

L'effetto globale è lo stesso ma questa volta il sender non resta bloccato dal nuovo valore di cwnd.

Implementazione di TCP Westwood+
in Linux

Quando si pensò ad un'implementazione in Linux di TCP Westwood+, il vostro relatore preferito pensò che Rate-Halving era un algoritmo semplicemente troppo intelligente per lasciarlo fuori...

Ne nacque un hack in cui si sfruttava Rate-Halving ma imponendo come limite minimo per il decremento di cwnd pari a BWE * RTTmin.

Implementazione di TCP Westwood+
in Linux

La patch è stata concepita e sviluppata con l'idea di essere quanto meno intrusiva possibile. Infatti, è possibile abilitare/disabilitare TCP Westwood+ mediante la sysctl net.ipv4.tcp_westwood.

La sysctl consente di switchare tra TCP NewReno e TCP Westwood+ senza che ci sia la necessità di rebootare la macchina.

Implementazione di TCP Westwood+
in Linux

Il supporto per TCP Westwood+ è stato ufficialmente incluso nel kernel a partire dalle release 2.4.26-pre1 (kernel 2.4) e 2.6.3-rc1 (kernel 2.6)

http://www.kernel.org

Per poter usufruire della patch su versioni precedenti del kernel

http://buffer.antifork.org/westwood/westwood.html

Westwood+, New Reno e Vegas TCP

TCP New Reno è una versione migliorata di TCP Reno che evita riduzioni multiple della cwnd quando più segmenti nella stessa finestra vengono persi.

RFC 3782, S. Floyd, T. Henderson, A. Gurtov, “The NewReno Modification to TCP's Fast Recovery Algorithm”

TCP New Reno è attualmente il protocollo di congestion control maggiormente utilizzato.

TCP Vegas

Analogamente a quanto fa TCP Westwood+, TCP Vegas si basa su meccanismo basato su misure di RTT per fare il throttling della congestion window.

TCP Vegas è anche alla base di Fast TCP, sviluppato a Caltech e balzato ingiustamente agli onori della cronaca di recente. Stando alle parole degli autori, “Fast TCP is a sort of high-speed version of Vegas”.

TCP Vegas

Analizziamo a questo punto, per sommi capi, il funzionamento di TCP Vegas.

TCP Vegas è stato il primo algoritmo di congestion control basato sulla valutazione delle condizioni della rete per decidere le sorti della congestion window.

TCP Vegas

Prima di tutto si definisce BaseRTT per un determinato flusso l'RTT di un pacchetto in assenza di congestione.

Nella pratica, TCP Vegas setta BaseRTT al più piccolo valore di RTT osservato e questo rende il concetto di BaseRTT estremamente simile al concetto di RTTmin già visto in TCP Westwood+

TCP Vegas

Se assumiamo che la nostra connessione non stia producendo fenomeni congestivi, è ragionevole capire che l'expected throughput (ossia il rate di trasmissione che il nostro host dovrebbe sostenere) sia pari a

ExpectedRate = cwnd/BaseRTT

TCP Vegas

Inoltre, TCP Vegas calcola il current sending rate ActualRate attraverso questa procedura :

1- memorizza l'istante di invio di un pacchetto

2- memorizza il numero di bytes ricevuti nell'intervallo di tempo intercorrente tra l'invio del pacchetto di cui al punto 1 e la ricezione dell'ACK relativo a quello stesso pacchetto

TCP Vegas

3- si valuta il valore di RTT per quel determinato pacchetto quando l'ACK viene ricevuto

4- si divide il numero di bytes precedentemente valutato al punto 2 per il RTT valutato al punto 3.

Questo calcolo viene fatto una volta ogni RTT e ci porta ad ottenere l'Actual Rate.

TCP Vegas

A questo punto, TCP Vegas confronta il valore di ExpectedRate con il valore di ActualRate.

Per comodità, indichiamo con Diff la seguente quantità

Diff = ExpectedRate – Actual Rate

TCP Vegas

Si noti che Diff può assumere soltanto valore positivo o al massimo 0 sempre in quanto

ActualRate > Expected Rate

implicherebbe che il valore dell'ultimo RTT valutato sarebbe inferiore a BaseRTT e questo significa che BaseRTT andrebbe aggiornato...

TCP Vegas

Inoltre si definiscono due valori di soglia indicati alfa e beta (con alfa < beta), corrispondenti rispettivamente alla situazione di “pochi dati nella rete” e “troppi dati nella rete”.

Quando si verifica che Diff < alfa, TCP Vegas incrementa linearmente il valore della congestion window nell'RTT successivo.

TCP Vegas

Quando si verifica che Diff > beta, TCP Vegas decrementa linearmente il valore della congestion window nell'RTT successivo.

Quando il valore di Diff è compreso tra alfa e beta, TCP Vegas non modifica il valore della congestion window.

TCP Vegas

Intuitivamente, si comprende che maggiore è la differenza tra il throughput attuale e il throughput atteso, maggiore è la congestione che sta sperimentando la rete in quel momento.

Questo implica che il rate di trasmissione deve essere ovviamente ridotto. Il parametro beta serve proprio a rilevare questo tipo di situazione.

TCP Vegas

D'altro canto, se il throughput attuale ha un valore molto prossimo al throughput atteso, è ragionevole pensare che le condizioni della rete stiano mutando a nostro favore e, quindi, che la connessione rischi di non sfruttare la banda effettivamente disponibile.

La soglia alfa serve a rilevare questa situazione.

Fast TCP

Fast TCP è attualmente in fase di test e, purtroppo, gli autori non hanno ancora rilasciato nè patch per il kernel nè moduli ns-2.

Essendo basato su misure di RTT, Fast TCP potrebbe ereditare tutti i difetti di TCP Vegas che provvederemo a illustrare nel dettaglio nel seguito (incapacità di grabbare la banda in presenza di traffico Reno o in presenza di reverse traffic).

Remark

La stima di banda realizzata da TCP Westwood+ è differente dal misurare la componente di bassa frequenza del sending rate cwnd/RTT (cwnd/RTT è la misura del throughput istantaneo utilizzata da TCP Vegas).

Infatti, il transmission rate cwnd/RTT utilizzato da TCP Vegas è una misura della banda disponibile basata sul numero di pacchetti spediti (cwnd) e non sul numero di pacchetti dk. Di conseguenza, i samples di TCP Vegas non portano in conto che una frazione dei pacchetti potrebbero essere persi portando così a una sovrastima della banda disponibile.

Steady State Throughput

Singola connessione + 10 connessioni TCP sul backward path che seguono un OFF-ON-OFF-ON pattern per investigare l'effetto del reverse traffic

TCP1

source

10 TCP

sources

Forward Traffic

Reverse Traffic

TCP1

Sink

10 TCP

Sinks

Dinamiche di cwnd e ssthresh

NewReno

Westwood+

Vegas

Reno

Intra-protocol Fairness

Si considerino M flussi TCP persistenti e controllati dallo stesso algoritmo su un single bottleneck. Inoltre, gli RTT degli M flussi sono uniformemente distribuiti nell'intervallo [20+230/M, 250] ms, con M compreso tra 10 e 200.

Questo scenario è utile per indagare l'intra-protocol fairness (the fairness with respect to the round trip time).

Intra-protocol Fairness (20 connessioni)

NewReno

Westwood +

Vegas

Wireless terrestrial scenario
TCP1 one way delay 125ms
20ms delay on the wireless link (2Mbps)

5 TCP sources

10 TCP

sources

Cross Traffic

Reverse Traffic

5 TCP

Sinks

10 TCP

Sinks

TCP1

source

Wireless link

TCP1

sink

Gli RTT delle 5 conessioni cross traffic e delle 10 connessioni New Reno backward traffic sono uniformemente distribuiti rispettivamente negli intervalli [66ms, 250ms] and [46ms, 250ms].

Il link wireless è affetto da perdite di tipo bursty segment in entrambe le direzioni.

Una Gilbert two-state Markov chain modella il processo di perdita

Loss probability P uguale a 0, quando il canale è in good state,

P =0.1 quando il canale è in bad state.

Tempo di permanenza nel good state deterministico e uguale a 1s

Tempo di permanenza nel bad state deterministico compreso tra 0.1 ms e 100 ms.

Quando si esaurisce il tempo di permanenza in uno stato, lo stato può transitare a good o bad state con probabilità P =0.5.

Single connection

Per ciascun caso considerato, sono state eseguite 10 simulazioni variando il seed del processo stocastico di perdita. Per ciascun valore di durata del BAD state sono riportati i valori minimo, medio e massimo del goodput.

Per analizzare soltanto l'impatto delle perdite bursty sul comportamento del TCP, dapprima sono state disattivate le sorgenti di cross traffic e di reverse traffic. Questo semplice scenario è particolarmente utile per investigare l'effettiva adeguatezza del paradigma di adaptive decrease quando le perdite non sono dovute a congestione sperimentata dal TCP.

Goodput della connessione TCP1 senza reverse traffic: DACK enabled

Goodput della connessione TCP1 senza reverse traffic: DACK disabled

Cwnd e ssthresh
(durata del BAD state 0.01s)

Westwood+

New Reno

Reverse and Cross Traffic

TCP Westwood+ condivide la porzione wired della rete con alcuni flussi TCP sia sul forward sia sul backward path (detto in altri termini cross e reverse traffic sono attivi).

I risultati mostrano che, in questo scenario, l'utilizzo dei delayed ACK gioca un ruolo estremamente importante per le performance.

Remarks

I protocolli che non utilizzano delayed ACK sono caratterizzati da throughput circa due volte più grande di quelli ottenuti quando i delayed ACK sono abilitati. La ragione di ciò è che i delayed ACK rallentano la fase di probing del TCP.

In questi scenari, TCP Westwood+ (DACK disabled) garantisce ancora improvement sul goodput rispetto a NewReno (DACK disabled) e SACK TCP, ma l'improvement è adesso soltanto di circa il 20%. La ragione risiede nel fatto che, in questo caso, la connessione TCP1 perde banda in favore del cross traffic che, essendo wired, non è penalizzato da perdite non dovute a congestione.

Satellite scenario

20 TCP

senders

20 TCP

sinks

10 TCP

sinks

10 TCP

senders

20 connessioni TCP forward in presenza di reverse traffic generato da 10 connessioni long-lived New Reno.

Large leaky pipe: 10Mbps bottleneck link con one-way delay pari a 275ms.

RTT delle connessioni forward pari a 590ms.

Implementazione di TCP Westwood+ in Linux 2.4.19
Risultati Sperimentali

Per qualche mese, il relatore ha provveduto a mettere a dura prova l'infrastruttura di rete del Politecnico di Bari realizzando più di 4000 upload FTP verso:

panther.cs.ucla.edu (UCLA)

signserv.signal.uu.se (Uppsala)

main.penguin.it (Parma)

panther.cs.ucla.edu (1)

panther.cs.ucla.edu (2)

panther.cs.ucla.edu (3)

panther.cs.ucla.edu (4)

Conclusioni

L'analisi e il confronto di TCP Westwood+, New Reno e Vegas usando ns-2 hanno mostrato

L'inter-protocol friendliness di Westwood+ e New Reno mentre Vegas non è in grado di grabbare il suo bandwidth share quando coesiste con New Reno o Westwood+

L'incremento della intra-protocol fairness nella bandwidth allocation di Westwood+ rispetto a New Reno

La migliore utilizzazione di links lossy fornita da Westwood+ rispetto a New Reno

Le misure collezionate nel mondo reale hanno mostrato che Westwood+ incrementa il goodput rispetto a New Reno quando la pipe size è più larga di alcuni segmenti

Riferimenti

S. Mascolo, L. A. Grieco, “Performance Comparison of Reno, Vegas, and Westwood+ TCP Congestion Control”, CCR Vol. 34 No. 2, April 2004

A. Dell’Aera, L. A. Grieco, S. Mascolo, “Linux 2.4 Implementation of Westwood+ TCP with Rate-Halving: A Performance Evaluation over the Internet”, IEEE International Conference on Communication 2004, Paris, France, 20-24 June

S. Mascolo, C. Casetti, M. Gerla, S. Lee, M. Sanadidi, “TCP Westwood: bandwidth estimation for enhanced transport over wireless links”, ACM Mobicom 2001

L. S. Brakmo, L. Peterson, “TCP Vegas : End to End Congestion Avoidance on a Global Internet”, IEEE Journal on Selected Areas in Communication, October 1995

PowerPoint Presentation

Angelo Dell'Aera

2004-08-16T13:02:22