L'algoritmo CUBIC, come vedremo, rappresenta una evoluzione del precedente BIC. Attualmente è implementato come opzione prede nta nel kernel (dalla versione 2.6.19) del sistema operativo GNU/Linux, come documentato in [CP07]. CUBIC modi ca la funzione di crescita delle ver- sioni standard di TCP, in modo che questa sia rappresentata da una cubica aumentando cosi scalabilità e stabilità soprattutto nelle reti con lunghe latenze. Grazie ad alcuni accorgimenti, inoltre, è possibile sfruttare più equamente l'allocazione di banda disponibile per i vari ussi con diversi RT T , in modo che la nestra di congestione, CongW in, cresca indipendentemente da questi tempi.
L'evoluzione di Internet ha portato alla nascita di reti molto veloci, con distanze tra i nodi molto elevate; la caratteristica principale di queste connessioni è il cosiddetto BDP(Bandwidth and Delay Product) che rappresenta il numero totale di pacchetti necessari, in transito, per avere un utilizzo di banda pari alla saturazione. Nei paragra precedenti abbiamo visto che le connessioni standard TCP gestiscono la crescita della nestra di congestione, linearmente, ogni round trip time e che su trasmissioni veloci, questa procedura, rende l'eettivo consumo di banda sotto utilizzato, specialmente se la lunghezza dei dati da trasferire è inferiore al tempo con cui il protocollo ingrandisce la nestra, no a raggiungere il pieno BDP del link di comunicazione. L'implementazione di CUBIC nel kernel di Linux è stata graduale e dettata da vari rilasci; l'aggiornamento più interessante è sicuramente quello in cui si modi ca la modalità di calcolo della radice cubica della funzione, che ottimizza notevolmente le prestazioni.
2.3.1 La funzione cubica di crescita
Il protocollo BIC, come descritto, era in grado di raggiungere una buona scalabilità nelle reti ve- loci ed una buona stabilità, della dimensione della nestra di congestione, durante le oscillazioni; tuttavia la funzione di crescita risultava molto aggressiva se usata con connessioni TCP standard specialmente se quest'ultime avevano bassi RT T . Le dimensioni della CongW in di CUBIC sono regolate da una funzione cubica, simile a quella utilizzata per BIC. La funzione è composta da una parte concava ed una convessa, utilizzate entrambe all'interno dell'algoritmo. La Figura 2.4
mostra il tipico andamento della funzione in esame.
Figura 2.4: Funzione di crescita della CongW in nell'algoritmo CUBIC
Cerchiamo di capire come lavora questa procedura. Dal momento in cui si registra la perdita di un pacchetto si memorizza la dimensione corrente della nestra nel parametro Wmax(indicato anche in Figura2.4); questo evento segna anche il tempo in cui TCP entra nella fase di decremento moltiplicativo (quella dell'algoritmo AIMD) utilizzando il fattore β. Superata la fase di Fast Recovery, si inizia nuovamente ad incrementare la dimensione della nestra utilizzando il pro lo concavo della funzione. La cubica viene gestita in modo da utilizzare l'insieme dei valori che la compongono costanti a Wmax, in questo modo la parte concava continua a crescere no a che la dimensione della nestra non diventa proprio quest'ultimo valore. Terminata questa prima fase la funzione passa al pro lo convesso e continua a crescere.
E' proprio la de nizione di queste due parti funzionali che permette all'algoritmo di stabiliz- zarsi e di essere quanto più scalabile possibile.
Possiamo de nire la funzione di crescita di CUBIC come segue
W (t) = C (t − K)3+ Wmax (2.17)
dove C è un parametro proprio del protocollo, t è il tempo trascorso dall'ultima riduzione di nestra e K è il periodo che impiega la funzione per incrementare la nestra corrente a Wmax, quando non si registrano più eventi di perdita. Il fattore K viene calcolato attraverso la seguente equazione
K = 3 r
W maxβ
C (2.18)
Quando si riceve un ACK durante la fase di controllo di congestione, CUBIC calcola il tasso di crescita della nestra attraverso il successivo periodo di round trip, RT T , utilizzando la 2.17; sostanzialmente imposta W (t + RT T ) come il valore candidato alla dimensione della nestra di congestione da raggiungere.
Se supponiamo che la dimensione corrente della nestra sia CongW in, allora possiamo trovarci in una delle seguenti condizioni
se CongW in è minore della nestra di congestione che TCP ha raggiunto, trascorso il tempo t in seguito ad un evento di perdita, si lavora in modalità TCP stndard. Utiliz- zando una semplice analisi si può trovare un valore medio della nestra di congestione, ottenuta dal processo di incremento additivo e decremento moltiplicativo (AIMD) con un fattore additivo α e uno moltiplicativo β da utilizzare nella formula 1
RT T q α 2 2−β β 1 p. CUBIC incrementa la sua nestra di un α ogni RT T che possiamo calcolare, in termini di tempo trascorso t, come segue: Wtcp(t) = Wmax(1 − β) + 32−ββ RT Tt . Se CongW in è minore di Wtcp(t) il protocollo è in modalità TCP standard e CongW in viene impostata a Wtcp(t) ogni volta che si riceve un ACK
se CongW in è minore di Wmax, CUBIC si trova nella regione concava della sua funzione. Alla ricezione di un ACK se non siamo nella regione TCP standard possiamo aumentare CongW in di W (t+RT T )−CongW inCongW in
se CongW in è maggiore di Wmax, CUBIC si trova nella regione convessa della funzione. In questa condizione signi ca che la rete è perturbata dall'ultimo evento di perdita, ciò implica una possibile presenza di banda disponibile e se la connessione dati è altamente asincrona queste uttuazioni di larghezza di banda sono molto frequenti. Il pro lo convesso garantisce che la crescita della nestra sia molto lenta all'inizio e più rapida con il passare del tempo. In questa regione il valore di CongW in può essere aumentato di W (t+RT T )−CongW in
CongW in , come fatto in precedenza
2.3.2 Convergenza veloce
Per aumentare la velocità di convergenza spesso vengono aggiunte delle euristiche al protocollo. Quando un nuovo usso si unisce alla rete, quelli esistenti devono condividere un pò della loro banda per permettere all'ultimo arrivato di poter, eventualmente, crescere in modo equo. Per accelerare questo processo, CUBIC si avvale di una procedura che chiamiamo convergenza veloce (Quick Convergence). Con questa tecnica, quando si veri ca un evento di perdita, prima di ridurre la nestra corrente, il protocollo memorizza l'ultimo valore di Wmax nella variabile che chiama Wlastmax. Se successivamente si veri ca una nuova situazione di perdita e se il valore
corrente di Wmax è inferiore a quello di Wlastmax signi ca che il punto di saturazione conosciuto
dal usso è stato ridotto a causa della variazione di banda disponibile. Sostanzialmente, il processo con cui si gestisce la rete in CUBIC ricorda quello di BIC; come detto si tratta di una evoluzione, ciò che eettivamente fa la dierenza è l'utilizzo di una funziona cubica.
Le sue performance lo hanno incoronato come algoritmo di riferimento nei sistemi basati su GNU/Linux e pertanto rappresenta sicuramente una delle scelte migliori in ogni condizione di rete; vedremo in seguito se queste sue proprietà sono valide anche su protocollo IEEE 802.16.