Tecniche per la stima di banda: simulazioni su reti con traffico variabile in ambiente NS-2

CAPITOLO 1. TECNICHE DI STIMA DI BANDA 5
La stima della banda è un fattore chiave per molte tecnologie. Molte ap-
plicazioni beneficiano dalla conoscenza della banda disponibile sui propri col-
legamenti. Ad esempio i software peer-to-peer formano dinamicamente le reti
a livello utente basandosi su stime di banda tra i vari utenti. Gli overlay net-
work possono configurare le tabelle di routing basandosi su stime di banda dei
collegamenti di overlay. I network provider rilasciano collegamenti e relativi
costi basandosi sulla banda richiesta dagli utenti. I piani di upgrade nelle reti
possono essere pianificati in base alle stime di utilizzo dei vari collegamenti, con
un conseguente risparmio economico e una migliore utilizzazione delle risorse.
Il termine banda è spesso imprecisamente utilizzato in una serie di concetti
relativi al throughput. Definiremo di seguito le metriche e le relative caratter-
istiche utili per comprendere il concetto di banda. Verrà definita la differenza
tra la banda di un collegamento e la banda di una serie di collegamenti in
sequenza detto percorso end-to-end, saranno presentate le differenza tra la mas-
sima banda possibile che un link può supportare (capacità) e la massima banda
non utilizzata (banda disponibile) e infine il throughput massimo raggiungi-
bile attraverso una connessione TCP (bluk transfer capacity). Tutte queste
metriche sono estremamente importanti poichè differenti aspetti della banda
possono essere rilevanti per differenti applicazioni.
Verrano poi presentate le principali tecniche per la stima della banda con
relative difficoltà e problemi e infine quattro tool per la stima di questa metrica.
CAPITOLO 1. TECNICHE DI STIMA DI BANDA 6
1.2 Metriche per la stima di banda
In questa sezione verranno introdotte tre metriche per la banda: la capacità,
la banda disponibile e la Bulk-Transfer-Capacity (BTC). Le prime due sono
definite sia per collegamenti individuali sia per percorsi end-to-end, mentre la
BTC è solitamente definita solo per percorsi end-to-end.
Verranno distinti i collegamenti a livello data link layer (layer-2), i segmen-
ti, dai collegamenti a livello IP (layer-3), gli hop. Normalmente un segmento
corrisponde a un collegamento fisico point-to-point o ad un ciruito virtuale. Un
hop invece può consistere in una sequenza di uno o più segmenti connessi tramite
switch, bridge o altri dispositivi del layer-2. Si definisce un percorso end-to-end
P da un IP host SND (fonte) ad un altro host RCV (destinazione) la sequenza
di hop che connette il SND al RCV.
1.2.1 Capacità
Un collegamento a livello layer-2, un segmento, può normalmente trasferire dati
ad una bit rate costante chiamata rate di trasmissione del segmento. Ad
esempio questa rate è di 10 Mbps su un segmento 10BaseT Ethernet e 1.544
Mbps su un segmento T1. La rate di trasmissione di un segmento è limitata sia
dalla banda di livello fisico del mezzo trasmissivo sia dall'hardware elettronico
o ottico che i trasmettitori/ricevitori impiegano..
A livello IP un hop invia ad una rate leggermente minore di quella nominale
per la presenza degli overhead derivamenti dell'incapsulamento in frame di livello
CAPITOLO 1. TECNICHE DI STIMA DI BANDA 7
2. Se si suppone che la capacità nominale del segmento sia CL2, la rate di
trasmissione per un pacchetto IP di grandezza LL3 byte sarà
∆L3 = LL3 +HL2CL2
dove HL2 è la dimensione in byte dell'overhead totale di livello layer-2. La
capacità CL3 del segmento a livello IP è quindi
CL3 =
LL3
∆L3
= LL3LL3+HL2
CL2
= CL2
1
1 + HL2LL3
E' da notare che la capacità di livello IP dipende dalla dimensione dell'over-
head di livello 2. Per la 10BaseT Ethernet CL2 è 10 Mbps eHL2 è 38 byte, perciò
la capacità che l'hop può garantire a livello IP è di 7.24 Mbps per pacchetti da
100 byte e 9.75 Mbps per pacchetti da 1500 byte.
Si definisce in [1] la capacità Ci di un hop i come la massima rate di
trasmissione di un hop a livello IP. Dall'equazione riportata sopra la rate di
trasferimento massima a livello IP si ha con pacchetti MTU (Maximum Trasmission
Unit) e cioè minimizzano l'effetto dell'headerHL2; si definisce quindi la capacità
di un hop come la bit rate, misurata a livello IP, alla quale un hop può trasferire
pacchetti di dimensione pari a MTU.
Estendendo questa definizione ad un contesto più ampio la capacità C di
un percorso end-to-end è la rate massima di livello IP che un percorso può
supportare. In altre parole, la capacità di un percorso stabilisce la banda supe-
riore del troughtput di livello IP. Il collegamento a capacità minima del percorso
CAPITOLO 1. TECNICHE DI STIMA DI BANDA 8
determina la capacità end-to-end
C = min
i=1,...,H Ci
dove Ci è la capacità dell hop i -esimo e H è il numero di hop del percorso.
L'hop con la capacità più bassa è quello che viene definito collo di bottiglia
del collegamento.
Alcuni percorsi implementano limitatori di traffico o di rate complicando così
la definizione della capacità. Nello specifico un limitatore di traffico su un col-
legamento può trasferire picchi di traffico che presentano una certa dimensione
di burst B a rate P, mentre effettua trasferimenti di traffico più lunghi dei burst
ad una rate minore S. Definendo la capacità come una banda superiore alla
quale un percorso può trasferire traffico, è naturale definire la capacità di quel
collegamento in funzione di P piuttosto che di S. Un limitatore di rate può in-
vece far passare solamente una frazione della capacità dei segmenti ad un hop
a livello IP. Ad esempio gli ISP spesso usano limitatori di rate per dividere la
capacità di un collegamento OC-3 tra diversi utenti, definendo prezzi differen-
ziati a seconda dell'utilizzo della banda. In questo caso si definisce la capacità
di un hop come il limite di rate di livello IP di un certo hop.
E' da notare inoltre che alcune tecnologie di livello 2 non operano con una
rate di trasmissione costante. E' il caso ad esempio dello stantdard IEEE 802.11b
di trasmissione su wireless LAN, che trasmette i propri frame a 11, 5.5, 2, o 1
Mbit/s a seconda dell'errore riscontrato. La precendente definizione di capactià
CAPITOLO 1. TECNICHE DI STIMA DI BANDA 9
può essere utilizzata in queste tecnologie durante gli intervalli temporali durante
i quali la capacità rimane costante.
1.2.2 Banda disponibile
Un'altra importante metricha è la banda disponibile di un link o di un collega-
mento end-to-end. La banda disponibile di un collegamento si riferisce alla
capacità non utilizzata durante un certo periodo di tempo. Questo valore non
dipende quindi, al contrario della capacità, dal tipo di tecnologia utilizzata dalla
trasmissione o dal mezzo di propagazione, ma dipende dal carico di traffico del
collegamento ed è tipicamente una metrica tempo variante.
Ad un dato istante temporale un collegamento può trasmettere un pacchet-
to alla piena capacità o essere inattivo, quindi l'utilizzazione istantea di un
collegamento può essere solamente 0 o 1. Ogni definizione di banda disponibile
deve quindi contemplare una media temporale della utilizzazione istantanea su
un certo intervallo temporale. L'utilizzazione media u(t − τ, t) su un periodo
(t− τ, t) è data da
u(t− τ, t) = 1
τ
∫ t
t−τ
u(x)dx
dove u(x)è la banda disponibile istantanea del collegmaneto all'istante x. Ci
si riferisce a τ come al timescale medio di banda disponibile. In figura 1.1 è
illustrato l'effetto della media.
CAPITOLO 1. TECNICHE DI STIMA DI BANDA 10
Figura 1.1: Utilizzazione istantanea per un collegamento nell'intervallo
temporale (0,T)
In questo esempio il collegamento è utilizzato durante 8 dei 20 intervalli tra
0 e T portando l'utilizzazione media al 40%.
La banda disponibile media Ai di un hop i su un certo intervallo temporale,
dove Ci è la capacità dell'hop i-esimo e ui è l'utilizzazione media di quell'hop
in un dato intervallo temporale, è data dalla frazione di capacità non utilizzata,
Ai = (1− ui)Ci.
Estendendo la precedente definizione ad un percorso di H hop, la banda disponi-
bile di un percorso end-to-end è la minima banda disponibile degli H hop,
A = min
i=1,...,HAi
La figura 1.2 mostra un modello di percorso di rete dove in ogni collegamento
sono rappresentati i livelli di capacità e banda disponibile. Il collegamento con la
più bassa capacità è C1 e determina la capacità end-to-end del percorso, mentre
CAPITOLO 1. TECNICHE DI STIMA DI BANDA 11
la minima banda disponibile A3 determina la banda disponibile end-to-end.
Figura 1.2: Modello a pipe con traffico per un percorso a 3 hop
Molte metodologie per la misura della banda disponibile assumono che l'utilizza-
zione del collegamento rimanga costante assumendo un carico di traffico stazionario
sul percorso preso in analisi. Questa caratteristica può essere vera solamente su
intervalli di tempo relativamente brevi. E' da notare inoltre che l'utilizzazione
media costante non preclude repentine variazioni di traffico o effetti dipendenti
dalle lunghe distanze.
Poichè la banda disponibile media può variare nel tempo, è importante mis-
urarla in tempi brevi. Questo è particolarmente cruciale per le applicazioni
che usano stime di banda per l'adattamento delle loro rate di trasmissione. Al
contrario la capacità di un percorso rimane costante per lunghi intervalli tempo-
rali, ad esempio fino al cambio delle politiche di routing o upgrade dei collega-
menti. La capacità è quindi una metrica che non necessita di essere misurata
velocemente quanto la banda disponibile.
CAPITOLO 1. TECNICHE DI STIMA DI BANDA 12
1.2.3 Throughput TCP e Bulk Transfer Capacity (BTC)
Un'altra metrica molto importante nelle reti TCP/IP è il throughput di una
connessione TCP. Il TCP è il protocollo di trasporto più utilizzato e supporta
quasi il 90% del traffico mondiale.
Sfortunatamente non è così semplice definire il throughput atteso da una con-
nessione TCP. Molti fattori influenzano il throughtput TCP come la dimensione
di trasferimento, il tipo di traffico esterno (UDP o TCP), il numero di con-
nessioni TCP in competizione, la grandezza dei buffer, le congestioni lungo il
percorso di acknoledgement. Variazioni delle specifiche di implementazione del
TCP come il NewReno, Reno, Tahoe o l'utilizzo di SACK piuttosto che ACK
cumulativi, l'impostazione della dimensione di finestra iniziale e altri parametri
influenzano sensibilmente il TCP throughtput.
Ad esempio il throughtput di un piccolo trasferimento come quello di una
tipica pagina Web dipende essenzialmente dalla finestra iniziale di congestione,
dal Round Trip Time e dai meccanismi di slow-start del TPC, piuttosto che
dalla banda disponibile del percorso. Il throughput di un grande trasferimento
TCP può variare significativamente a seconda della diversa versione di TCP
utilizzata.
La capacità di trasferimento a bulk (Bulk Transfer Capacity, BTC) è una
metrica che definisce il throughtput raggiungibile da una connessione TCP. Il
BTC è il massimo throughput raggiungibile da una singola connessione TCP.
Il BTC e la banda disponibile sono due metriche fondamentalmente differenti
poichè il BTC è una metrica specifica dei collegamenti TCP, mentre la banda
CAPITOLO 1. TECNICHE DI STIMA DI BANDA 13
disponibile non dipende dal protocollo impiegato a livello trasporto. Il BTC
dipende inoltre da come la banda viene ripartita tra più connessioni TCP, men-
tre la banda disponibile assume che la media di traffico rimanga costante e stima
la banda che il percorso può ancora offrire. Se si suppone che un collegamento
singolo con capacità C sia saturato da una singola connessione TCP, la ban-
da disponibile del percorso sarà zero, ma la BTC potrebbe essere C2 nel caso
fosse presente una seconda connessione TCP con il round trip time uguale alla
precedente connessione TCP.
1.3 Tecniche per la stima di banda
In questa sezione verrano descritte le tecniche per la misura di capacità e banda
disponibile su singoli hop e collegamenti end-to-end. In particolare verranno
esaminate le quattro tecniche più importanti :
1. Variable packet size (VPS).
2. Packet Pair/Train Dispersion (PPTD).
3. Self-Loading Periodic Streams (SLoPS).
4. Train of Packet Pairs (TOPP).
La tecnica VPS stima la capacità dei singoli hops, quella PPTD stima la capacità
end-to-end di un collegamento, mentre le tecniche SLoPS e TOPP stimano
la banda disponibile su collegamenti end-to-end. Attualmente non esistono
tecniche per la misura di banda disponibile su singoli hop.
CAPITOLO 1. TECNICHE DI STIMA DI BANDA 14
Per l'analisi di queste tecniche su un cammino P assumeremo che il routing
non cambi e che il traffico sia stazionario. I cambiamenti dinamici nel routing
o nel traffico posso portare ad errori in tutte le metodologie di misura.
1.3.1 Variable packet size (VPS)
La tecnica VPS [1] [2] [3] mira a stimare la capacità di ogni passo di un collega-
mento tra un host che trasmette e un host che riceve. La chiave di questa tecnica
è la misura del RoundTripTime (RTT) dalla fonte al singolo hop come funzione
della dimensione del pacchetto impiegato per il probing. La metodologia VPS
utilizza il campo TimeToLive (TTL) dell'header IP per forzare i pacchetti a
scadere su un particolare hop. Il router corrispondente a quel particolare hop
scarta i pacchetti, inviando un segnale ICMP (Time-exceeded error) alla fonte.
E' quindi possibile calcolare il Round Trip Time su quel particolare hop.
Il RTT di ogni singolo passo è composto da tre differenti componenti di
ritardo nel senso di andata e nel senso di ritorno: il tempo di inoltro, il tempo di
propagazione e i tempi di coda. Il tempo di inoltro di un pacchetto di dimensione
L su un collegamento con frequenza di trasmissione o bit rate C è il tempo che
viene impiegato per trasmettere quel pacchetto su quel collegamento, dunque è
pari a LC . Il ritardo di propagazione di un pacchetto è il tempo che il pacchetto
impiega per attraversare un collegamento ed è indipendente dalla sua dimensione
dei pacchetti. Il ritardo di accodamento dipende dai buffer dei router o degli
switch quando ci sono contese nelle code in ingresso o in uscita.
La tecnica VPS invia pacchetti multipli di dimensione nota da un host ad