Università degli Studi di Pavia
Facoltà di Ingegneria
Corso di Laurea in Ingegneria Informatica
Sviluppo di una tecnica
innovativa per la stima della
banda disponibile
Relatore:
Prof. Giuseppe F. Rossi
Elaborato di laurea di:
Alberto Torelli
Matricola: 337819/90
Correlatore:
Ing. Emanuele Goldoni
Anno Accademico 2007/08
Indice
Indice
i
Elenco delle figure
iii
Elenco delle tabelle
iv
1 Introduzione
1
2 Reti a pacchetto e dispositivi di interconnessione
2.1 La storia . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Il funzionamento . . . . . . . . . . . . . . . . . . .
2.3 Vantaggi della commutazione di pacchetto . . . . .
2.4 Dispositivi di interconnessione . . . . . . . . . . .
2.4.1 Il modello a code . . . . . . . . . . . . . . .
2.4.2 Tecniche per la gestione delle code . . . . .
3 Misurazioni sulle reti
3.1 L’assenza di standard . . . . . .
3.2 Modalità di misurazione . . . . .
3.2.1 Misurazioni attive . . . .
3.2.2 Misurazioni passive . . . .
3.2.3 Misurazioni miste . . . . .
3.3 Le metriche . . . . . . . . . . . .
3.3.1 Il prodotto banda ritardo
3.3.2 La capacità . . . . . . . .
3.3.3 La banda disponibile . . .
3.3.4 Altre Metriche . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4 Stima della banda disponibile e il tool pathChirp
4.1 Campi di applicazione della stima della banda disponibile
4.2 Lo stato dell’arte . . . . . . . . . . . . . . . . . . . . . . .
4.2.1 I modelli affini . . . . . . . . . . . . . . . . . . . .
4.2.2 I modelli di gap probing (PGM) . . . . . . . . . .
4.2.3 I modelli di rate probing (PRM) . . . . . . . . . .
4.3 I problemi della banda disponibile . . . . . . . . . . . . .
4.4 pathChirp . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.1 L’algoritmo di stima . . . . . . . . . . . . . . . . .
i
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4
4
5
6
7
7
7
.
.
.
.
.
.
.
.
.
.
9
9
9
9
10
10
11
11
11
12
13
.
.
.
.
.
.
.
.
14
15
15
16
17
19
21
22
22
ii
INDICE
4.4.2
4.4.3
Calcolo della stima della banda disponibile . . . . . . . . . .
Il problema della sovrastima . . . . . . . . . . . . . . . . . . .
5 ASSOLO
5.1 Modalità di funzionamento . . . . . . . . . . . . . . . . . . . .
5.2 L’algoritmo di stima . . . . . . . . . . . . . . . . . . . . . . . .
5.3 Correzione al problema della sovrastima . . . . . . . . . . . . .
5.4 Nuovo algoritmo di stima . . . . . . . . . . . . . . . . . . . . .
5.4.1 Profilo REACH . . . . . . . . . . . . . . . . . . . . . . .
5.4.2 Il modello teorico . . . . . . . . . . . . . . . . . . . . . .
5.5 Altre funzionalità implementate . . . . . . . . . . . . . . . . . .
5.5.1 Esecuzione di ASSOLO in Kernel Linux Soft Real-Time
5.5.2 Calcolo della stima della banda disponibile . . . . . . .
6 Prove in laboratorio e risultati ottenuti
6.1 La rete di prova . . . . . . . . . . . . . . . .
6.2 Configurazione utilizzata nei test . . . . . .
6.2.1 ASSOLO . . . . . . . . . . . . . . .
6.2.2 pathChirp . . . . . . . . . . . . . . .
6.2.3 D-ITG . . . . . . . . . . . . . . . . .
6.3 Risultati ottenuti . . . . . . . . . . . . . . .
6.4 Confronto invasività ASSOLO - pathChirp .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
23
24
.
.
.
.
.
.
.
.
.
25
25
25
27
28
28
30
32
32
34
.
.
.
.
.
.
.
35
35
36
36
37
37
38
39
7 Conclusioni
44
A Codice Sorgente
A.1 Implementazione Profilo REACH . . . . . . . . . . . . . . . . . . . .
A.2 Priorità real-time . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
46
47
Bibliografia
48
Elenco delle figure
1.1
1.2
Funzionamento delle misurazioni passive in una rete . . . . . . . . .
Profilo REACH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
3
2.1
2.2
2.3
La rete ARPANET nel settembre 1971 . . . . . . . . . . . . . . . . .
Condivisione di un canale da parte di più flussi dati (da [1]) . . . . .
Descrizione di un router con il modello a code (tratto da [2]) . . . .
5
6
8
3.1
3.2
3.3
3.4
Esempio di misurazione attiva su una rete . . . . .
Misurazioni passive su una rete (Fonte [3]) . . . . .
Andamento nel tempo dell’occupazione della banda
Round Trip Time (RTT) . . . . . . . . . . . . . . .
4.1
4.6
Esempio di un canale completamente utilizzato (a) e di un secondo
con ancora una porzione di banda disponibile (b) (Fonte [2]) . . . . .
Cammino di rete visto come una tubatura . . . . . . . . . . . . . . .
Principio di funzionamento dei metodi PGM (tratto da [5]) . . . . .
Principio alla base dei metodi PRM (Fonte [6]) . . . . . . . . . . . .
Metodo di individuazione della banda disponibile 𝐴 utilizzato da
pathChirp e ASSOLO . . . . . . . . . . . . . . . . . . . . . . . . . .
Tipico andamento dei ritardi in un chirp (Tratto da [7]) . . . . . . .
5.1
5.2
5.3
5.4
5.5
Metodo di funzionamento di ASSOLO . . . . . . . . . . . . . . .
Profilo a occhio di pesce (FEAT) (Fonte [8]) . . . . . . . . . . . .
Andamento dei Δ𝑟𝑎𝑡𝑒 . . . . . . . . . . . . . . . . . . . . . . . . .
Andamento rates invio con il profilo REACH . . . . . . . . . . .
Confronto fra le densità di misurazione fra ASSOLO e pathChirp
4.2
4.3
4.4
4.5
. . . . .
. . . . .
(da [4])
. . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
10
11
12
13
14
15
18
19
21
23
.
.
.
.
.
26
28
29
30
33
Rete di prova utilizzata in Laboratorio . . . . . . . . . . . . . . . . .
Esempio di grafico realizzato con ITGPlot (Tratto da [9]) . . . . . .
Architettura tool D-ITG (Fonte [10]) . . . . . . . . . . . . . . . . . .
Confronto ASSOLO-pathChirp su rete a 100 Mbps nominali in assenza
di cross-traffico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.5 Confronto ASSOLO-pathChirp con traffico CBR a 32 Mbps su rete a
100 Mbps nominali . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.6 Confronto ASSOLO-pathChirp con traffico CBR a 64 Mbps su rete a
100 Mbps nominali . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.7 Andamento delle varianze nelle misurazioni . . . . . . . . . . . . . .
36
38
39
6.1
6.2
6.3
6.4
iii
.
.
.
.
.
.
.
.
.
40
40
41
42
Elenco delle tabelle
4.1
Tool per la stima della banda attualmente disponibili. . . . . . . . .
16
6.1
6.2
Tabella configurazione di ASSOLO utilizzata in laboratorio. . . . . .
Tabella configurazione di D-ITG utilizzata per le prove. (Ulteriori
riferimenti da [11]) . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Tabella confronto invasivita ASSOLO-pathChirp con 𝛾=1,2 e 𝜎=5%.
Tabella accuratezze ASSOLO-pathChirp ipotizzando la banda disponibile centrata nell’intervallo di misura, con 𝜎=5% e 𝛾=1,2. I valori
in tabella sono espressi in Mbps . . . . . . . . . . . . . . . . . . . . .
37
6.3
6.4
iv
38
41
43
Capitolo 1
Introduzione
Una nuova verità scientifica non trionfa perché
convince i suoi oppositori facendo vedere loro la luce,
bensì perché i suoi oppositori alla fine muoiono e
nasce una nuova generazione a cui la nuova verità è
familiare.
Max Karl Ernst Ludwig Planck
A partire dagli anni ’60, grazie agli studi di Paul Baran, alle normali reti di
telecomunicazioni basate sulla commutazione di circuito (circuit switching) si andò
ad affiancare una nuova tecnologia: la commutazione di pacchetto (packet switching
[12]). Oggi le reti di calcolatori si basano proprio sulla commutazione di pacchetto,
che risulta più efficiente ed economica della commutazione di circuito, tecnologia
ancora utilizzata dalle normali reti telefoniche; queste caratteristiche hanno permesso
la realizzazione di sistemi di comunicazione su larga scala.
Una delle principali attività per chi si occupa della gestione di una rete di
telecomunicazioni è la possibilità di effettuare delle misurazioni sullo stato della
rete. Le prime pubblicazioni riguardanti le prestazioni di ARPANET, la rete da cui
nacque Internet, risalgono agli anni ’70 [13; 14]; tuttavia, a dispetto dell’importante
lavoro di ricerca svoltosi in questi decenni, non esiste ancora uno standard univoco
che definisca terminologia e strumenti da utilizzare per valutare le performance di
una rete a pacchetto.
Tra le numerose metriche utilizzate [15; 16; 17] per la descrizione di una rete di
telecomunicazioni la più utilizzata è la larghezza di banda, o semplicemente banda.
Per quanto riguarda le reti digitali, con il termine banda si indica la quantità di
dati che il canale riesce a trasmettere per unità di tempo; questa informazione viene
solitamente misurata in bit al secondo (bps o per le grandi capacità Mbps e Gbps).
Con il termine banda ci si può riferire anche a diverse proprietà: ad esempio si
definisce capacità la massima quantità di dati trasferibili nell’unità di tempo e si
denomina banda disponibile la quantità di capacità inutilizzata dal link in un periodo
di tempo.
In questo elaborato ci si occuperà della stima della banda disponibile: una
problematica che grazie anche allo sviluppo tecnologico delle reti, risulta di grande
interesse in molte realtà. La stima della banda disponibile risulta indispensabile per
le prestazioni di alcune applicazioni oggi molto diffuse come il VoIP e le reti peer1
CAPITOLO 1. INTRODUZIONE
2
to-peer; inoltre molti operatori fatturano ai clienti la quantità di banda disponibile
precedentemente definita in uno SLA (Service Level Agreement). Malgrado i numerosi
ambiti di applicazione della stima della banda disponibile i lavori di ricerca in questo
campo sono in numero esiguo rispetto a quelli su altre metriche caratterizzanti le
prestazioni di una rete di calcolatori.
Per quanto riguarda la stima della banda si è partiti dal lavoro degli autori di
pathChirp [7], un software sviluppato nel 2003 dai laboratori della Rice University e
di Stanford, e dal software ASSOLO (Available Bandwidth Smart Smoothing OnLine tOol) un applicativo derivante da pathChirp sviluppato nel Laboratorio Reti
dell’Università di Pavia che implementa alcune modifiche al software originale.
Il funzionamento di pathChrip e del suo derivato ASSOLO non richiede la
conoscenza a priori dello stato o delle caratteristiche della rete, che viene considerata
come una black box. Due processi compongono il sistema attivo di misura: il primo
processo, in esecuzione sul nodo sorgente, ed il secondo processo passivo, in ascolto sul
nodo di destinazione. La rilevazione viene effettuata end-to-end, inviando del traffico
apposito (probe traffic) dal mittente al ricevente. Supponendo nota la distribuzione
iniziale dei pacchetti inviati è possibile, analizzando come questa viene modificata
nell’attraversamento della rete, effettuare delle valutazioni sullo stato della rete
stessa.
Figura 1.1: Funzionamento delle misurazioni passive in una rete
Ambedue i software utilizzati si basano sul principio di auto-congestione: per un
breve periodo di tempo viene immesso in rete un traffico ad una velocità maggiore di
quella supportata dai nodi intermedi, causando quindi una temporanea congestione
del cammino. Per quanto riguarda il profilo del traffico inviato, pathChirp non invia
stream periodici di pacchetti ad un rate costante o linearmente crescente, bensì
utilizza treni (chirp) costituiti da un numero 𝑁 di pacchetti con distanze esponenzialmente decrescenti. La banda disponibile 𝐵 viene, quindi, calcolata individuando il
valore esatto in coincidenza del quale il traffico di misurazione inizia a sperimentare
un aumento dei ritardi.
Pur essendo considerato un ottimo prodotto, alcuni aspetti di pathChirp non
risultano molto approfonditi: in particolare, non esistono studi sull’invasività del
software ed inoltre vi è il problema della sovrastima, che è citato in letteratura e che
è stato possibile verificare anche nelle misurazioni eseguite in laboratorio.
CAPITOLO 1. INTRODUZIONE
3
Il software ASSOLO nasce dalla volontà di eliminare il problema della sovrastima [18; 19]: per fare ciò implementa un sistema di filtraggio on-line innovativo,
computazionalmente efficiente ed in grado di sfruttare efficacemente le correlazioni
esistenti tra misurazioni successive. Come affermato in precedenza, pathChirp utilizza un andamento esponenziale della distanza dei pacchetti in un chirp; tuttavia, in
letteratura, è possibile trovare altri andamenti implementabili, come l’andamento
cosiddetto fish-eye (ad occhio di pesce). Al contrario, per quanto riguarda la tecnica
implementata, si è preferito utilizzare un andamento che concentrasse la maggior
parte delle prove nei pressi del valore centrale del range di misura impostato. L’andamento rappresentato in Figura 1.2, è stato battezzato col nome REACH (Reflected
ExponentiAl CHirp).
Figura 1.2: Profilo REACH
Nei capitoli successivi verrà ampliato quanto brevemente indicato nell’introduzione. I successivi capitoli sono pertanto così strutturati: nel Capitolo 2 è presente
una panoramica sulle reti a pacchetto, mentre nel Capitolo 3 verrà introdotto il
problema delle misurazioni nelle reti. Il Capitolo 4 si occuperà della stima della
banda disponibile ed una illustrazione del software pathChirp; successivamente nel
Capitolo 5 ci si occuperà del software ASSOLO e delle modifiche implementate
nell’algoritmo. Infine nel Capitolo 6 e nel Capitolo 7 verranno illustrate le prove
effettuate in laboratorio, i risultati ottenuti e le conclusioni.
Capitolo 2
Reti a pacchetto e dispositivi di
interconnessione
The net isn’t a directed graph. It’s not a tree. It’s a
single point labeled G connected to 10 billion
destination pages.
Richard Skrenta
Le reti di telecomunicazioni si dividono in due macro famiglie: quelle a commutazione di pacchetto e quelle a commutazione di circuito. Le reti di calcolatori
appartengono alla prima famiglia in quanto l’approccio utilizzato risulta più economico ed efficiente rispetto alla commutazione di circuito, contribuendo, così, alla
realizzazione di sistemi di comunicazione su larga scala a costi contenuti.
2.1
La storia
Il concetto di rete a commutazione di pacchetto venne introdotto nei primi anni ’60
da Paul Baran, ricercatore della RAND Corporation, ed in contemporanea ma in
assoluta autonomia da Donald Davies, ricercatore gallese presso il National Physical
Laboratory di Teddington (UK). Entrambi i loro studi si basavano sulle prime
pubblicazioni riguardanti la commutazione digitale ad opera di Leonard Kleinrock
[20] dell’UCLA. Nel 1964 Baran, dopo alcune pubblicazioni negli anni precedenti,
pubblicò una raccolta di undici volumi [12] in cui descriveva una generica architettura
per la costruzione di una rete estesa su larga scala, distribuita ed in grado di operare
anche in caso di guasti o di caduta dei nodi di interconnessione.
L’idea di Baran era quella di utilizzare una rete decentralizzata, con più cammini
disponibili tra due punti qualsiasi della rete, dividere i messaggi degli utenti in blocchi
(poi identificati come pacchetti) e, infine consegnare i messaggi utilizzando tecniche
di inoltro come store-and-forward 1 . Come già detto negli stessi anni, in Inghilterra,
Donald Davies sviluppò del tutto autonomamente il principio della commutazione
di pacchetto.
Successivamente i due gruppi di ricerca si unirono, ed è curioso osservare che,
malgrado le ricerche indipendenti, Baran e Davies erano arrivati ad individuare
1
Cioè si attende la ricezione dell’intero pacchetto prima di effettuare l’inoltro dei dati
4
CAPITOLO 2. RETI A PACCHETTO E DISPOSITIVI DI INTERCONNESSIONE5
alcuni parametri del tutto analoghi tra loro. Questi studi influenzarono tra gli altri
Lawrence Roberts che, una volta incaricato dal Dipartimento della Difesa degli
U.S.A. di sviluppare ARPANET (da cui poi nascerà Internet), decise di adottare la
tecnologia a commutazione di pacchetto.
Figura 2.1: La rete ARPANET nel settembre 1971
Correva l’anno 1969 quando venne attivata sperimentalmente la rete ARPANET
[21]; da allora questa rete si è evoluta, divenendo una struttura complessa che collega
tra loro migliaia di reti: da quelle commerciali a quelle amministrative, da quelle
governative a quelle universitarie (ad esempio l’italiana GARR, che interconnette le
università e i centri di ricerca nazionali). Tutte queste reti costituiscono quello che
oggi è conosciuto come Internet. Tutte le network che costituiscono Internet sono
gestite da operatori indipendenti che, per ragioni di interesse economico, utilizzano
degli standard comuni e rispettano accordi per interesse reciproco. Da ciò si deduce
che in Internet non esiste un’unità principale di controllo del traffico cui tutti fanno
riferimento, infatti il controllo del traffico avviene end-to-end a differenza delle reti
telefoniche dove il controllo avviene nei nodi interni della rete.
2.2
Il funzionamento
Gli elementi che sono alla base di una rete di telecomunicazioni sono due: i canali
di comunicazione, comunemente detti link, e i nodi. Una rete può essere vista
come un insieme di canali che interconnettono tre loro gli end-system, cioè i nodi
mittente e destinatario di una comunicazione; tale sistema complesso può essere
visto come l’unione di più sottosistemi semplici fino a raggiungere il sistema più
elementare, il link. I nodi intermedi, devono quindi far colloquiare i vari sottosistemi
che compongono la rete. Per fare questo, in una rete di calcolatori, i nodi utilizzano
CAPITOLO 2. RETI A PACCHETTO E DISPOSITIVI DI INTERCONNESSIONE6
la tecnica della commutazione di pacchetto, una metodica di multiplexing statico
dove il link viene diviso in diversi canali logici, associati a diversi flussi (stream) di
dati.
Tutte le comunicazioni che partono da un end-system vengono suddivise in
parti, aventi una dimensione massima prestabilita; queste parti sono dette pacchetti.
Una volta creati, i pacchetti, devono essere inoltrati nella rete fino a raggiungere
l’end-system destinatario del messaggio. Al messaggio iniziale vengono poi aggiunte
informazioni necessarie per determinare il precorso dei nodi da attraversare lungo la
rete; questo accorgimento permette di inviare i singoli pacchetti in modo indipendente.
I dati vengono quindi instradati in base ad un algoritmo di routing, che, in virtù a
dei criteri stabiliti, opta per un percorso tra quelli disponibili.
Figura 2.2: Condivisione di un canale da parte di più flussi dati (da [1])
2.3
Vantaggi della commutazione di pacchetto
Come già detto nel capitolo introduttivo, le reti basate sulla tecnologia del packet
switching permettono di costruire reti su larga scala a costi contenuti più affidabili
delle reti a commutazione di circuito; i vantaggi di questa tecnologia consistono in
una ottimizzazione dell’utilizzo dei canali ed una minimizzazione delle latenze, tali
accorgimenti che permettono di aumentare la robustezza della rete.
La maggiore efficienza è dovuta al fatto che nelle normali reti telefoniche a
commutazione di circuito, tutte le risorse necessarie per una comunicazione vengono
riservate per tutta la durata della connessione; questo implica che per 𝑁 comunicazioni occorre utilizzare 𝑁 canali, mentre nelle reti a pacchetto la commutazione
viene effettuata sulla base del contenuto del pacchetto e quindi la banda è disponibile
per più comunicazioni contemporanee2 . Il secondo vantaggio è quello delle minori
latenze, conosciuto come pipelining: ossia i diversi nodi della rete possono trasmettere
contemporaneamente pacchetti. L’impiego simultaneo dei pacchetti permette un
elevato incremento di efficienza, un maggior utilizzo del link e la diminuzione del
ritardo totale di trasmissione rispetto ad una rete che non applica la divisione del
messaggio in pacchetti. Per quanto riguarda la maggior robustezza, questa è data
dal fatto che non esiste un controllo centralizzato e vi sono quindi più cammini
2
Per questo talvolta si dice che una rete a commutazione di pacchetto fornisce una connessione
logica tra gli end-system
CAPITOLO 2. RETI A PACCHETTO E DISPOSITIVI DI INTERCONNESSIONE7
alternativi per congiungere due punti della rete; la caduta di un nodo o di un canale
consente comunque al resto della rete di funzionare.
Inoltre vi è la possibilità di adottare alcuni algoritmi specifici che permettono alla
rete di riconfigurarsi dinamicamente per utilizzare nuovi percorsi. Questo fu uno dei
motivi principale che spinse i ricercatori di ARPANET ad adottare la soluzione della
commutazione a pacchetto, in quanto i collegamenti allora disponibili erano poco
affidabili e l’obiettivo era quello di permettere ai ricercatori di riuscire ad utilizzare i
pochi supercalcolatori allora disponibili in rete.
2.4
Dispositivi di interconnessione
Durante il percorso tra gli end-system del mittente e del destinatario, un pacchetto
deve solitamente attraversare diversi nodi intermedi. Ognuno di questi nodi può
essere pensato come un elemento avente più interfacce per la spedizione e la ricezione
dei pacchetti, ciascuna con una o più code associate, e una CPU che analizza i
pacchetti ricevuti e li instrada una volta che ha eseguito gli algoritmi opportuni. I
dispositivi in questione detti nodi, sono dispositivi che operano al livello 2 e 3 dello
standard OSI (Open System Interconnection) [22; 23]. Tali dispositivi sono i router
che operano a livello Network e per quanto riguarda il livello 2 ricordiamo gli switch
(bridge Ethernet3 ).
2.4.1
Il modello a code
Si prenda in considerazione il modello a code che descrive il funzionamento di un
nodo di commutazione intermedio: un pacchetto proveniente da un’interfaccia di
ingresso viene inserito in coda in attesa della commutazione e, dopo che la CPU
determina il percorso, lo sposta in un’altra coda, questa volta di un’interfaccia
d’uscita; una volta terminata l’attesa il pacchetto verrà inoltrato al nodo successivo.
L’impiego delle code è reso necessario dal fatto che, come detto alcuni paragrafi
sopra, non vi è un controllo centralizzato del traffico e quindi può succedere che
ad un host arrivino pacchetti con un tasso più alto di quello che riesce a smaltire
(sia per la sua capacità, che per quella del link successivo): questa situazione porta
al congestionamento del nodo. Per poter gestire questi sovraccarichi temporanei
senza perdere le informazioni vengono impiegati dei buffer di memorizzazione sulle
interfacce in ingresso e uscita. Quando i pacchetti rimangono in coda subiscono
comunque un ulteriore ritardo, che si va ad aggiungere al tempo di ritardo accumulato
dal segnale per la propagazione. Se la situazione di congestione permanesse per un
tempo sufficiente all’esaurimento delle capacità dei buffer, tutti i pacchetti successivi
ricevuti dal nodo verrebbero scartati, causando quindi una perdita di informazioni.
2.4.2
Tecniche per la gestione delle code
L’esistenza delle code comporta la necessità di attuare una politica per stabilire
l’ordine di prelievo dei pacchetti presenti in una coda; questi criteri prendono il
nome di politica di scheduling del router. Diverse sono le politiche utilizzate, la più
semplice e più utilizzata in Internet è la First Come First Served (FCFS); esistono
3
Meglio noti come switch
CAPITOLO 2. RETI A PACCHETTO E DISPOSITIVI DI INTERCONNESSIONE8
Figura 2.3: Descrizione di un router con il modello a code (tratto da [2])
comunque altre politiche molto più sofisticate come ad esempio Fair Queuing (FQ) e
Weighted Round Robin (WRR) [24]. Queste tecniche complesse vengono applicate
principalmente quando si ha la necessità di differenziare il servizio offerto a diversi
traffici (ad esempio garantire una certa capacità del link).
Capitolo 3
Misurazioni sulle reti
Le idee migliori sono proprietà di tutti
Lucio Anneo Seneca
Come già citato nel capitolo introduttivo, le misurazioni riguardanti le prestazioni
delle reti sono una delle principali necessità per chi opera nel settore.
3.1
L’assenza di standard
Per quanto riguarda Internet le prime pubblicazioni sulle prestazioni di ARPANET
risalgono agli inizi degli anni ’70 [13; 14]; malgrado ciò, non esistono ad oggi regole e
standard universalmente accettati per la descrizione delle performance delle network.
I gruppi di lavoro dell’IETF, del Global Grid Forum, delle università (CAIDA1 ) e di
altri centri di ricerca hanno, comunque, proposto convenzioni per definire metodologie
[15; 25; 17; 16] e metriche di misurazione.
3.2
Modalità di misurazione
Esistono diverse modalità per eseguire misurazioni in un network, queste modalità
vengono raggruppate in tre macro gruppi: Attive, Passive, Miste.
3.2.1
Misurazioni attive
In questa famiglia di misurazioni la rete viene considerata come una black-box e la
misurazione viene effettuata end-to-end. Il sistema di misurazione è costituito da un
processo in esecuzione sul nodo sorgente ed uno passivo, in ascolto sul destinatario;
la misurazione viene effettuata dal sorgente inviando del traffico di prova (probe
flow), spedito, esclusivamente per questo fine, verso il ricevente. Supponendo nota la
distribuzione iniziale dei pacchetti immessi sul percorso è possibile, analizzando come
questa viene modificata dall’attraversamento della rete, effettuare delle valutazioni
sullo stato della rete. Adottando questo tipo di misurazioni si rilevano informazioni
limitate ed incomplete poiché si ottengono dati su un percorso specifico e non
1
Cooperative Association for Internet Data Analysis, San Diego CA
9
CAPITOLO 3. MISURAZIONI SULLE RETI
10
sull’intera rete; inoltre dato che la conoscenza della rete avviene in maniera indiretta
è possibile rilevarne lo stato in cui si trova ma non i motivi per cui ci si trova. I vantaggi
di questa tecnica risiedono nel fatto che, variando la distribuzione, la dimensione o le
tempistiche di invio dei pacchetti, è possibile focalizzare la misurazione su differenti
aspetti e, rispetto ad una misurazione passiva, la quantità di dati da analizzare è
molto più contenuta. Lo svantaggio principale è dato dal fatto che le misurazioni
sono di carattere attivo e, quindi, invasivo.
Figura 3.1: Esempio di misurazione attiva su una rete
3.2.2
Misurazioni passive
Il principale vantaggio di queste misurazioni è quello di non perturbare il traffico
esistente e non sovraccaricare la rete, risultando quindi non invasive. Per effettuare
una misurazione passiva di un flusso occorre però che, lungo il percorso, siano presenti
dei rilevatori di traffico. Questi rilevatori devono poi essere in grado di determinare le
prestazioni della rete ed il comportamento dei vari flussi di pacchetti, semplicemente
osservando il traffico di passaggio, senza intervenire apportando delle modifiche. Per
effettuare una misurazione passiva si ha la necessità di avere hardware, software e
protocolli adeguati per raggiungere questo scopo, nonchè la possibilità di controllare
gli stessi nodi di misurazione lungo tutto il percorso. Per i motivi appena citati
questo approccio è applicabile a reti di dimensione limitata e sulle quali si ha il
pieno controllo. Le misurazioni passive, infatti, sono adottate principalmente nelle
reti locali [26], nei sistemi di prova controllati o simulati al calcolatore.
3.2.3
Misurazioni miste
Le misurazioni miste, a differenza di quelle attive, non prevedono l’invio di pacchetti
specifici, bensì sfruttano il traffico generato da altri protocolli per effettuare i calcoli.
Un esempio è il protocollo TCP Westwood/Westwood+ [27; 28; 29], un’estensione
del tradizionale Transmission Control Protocol, in grado di utilizzare i pacchetti
dati e gli ACKnoledgment (ACK) di conferma, ricevuti durante la connessione per
stimare la banda disponibile e regolare, di conseguenza, l’apertura della finestra di
congestione.
CAPITOLO 3. MISURAZIONI SULLE RETI
11
Figura 3.2: Misurazioni passive su una rete (Fonte [3])
3.3
Le metriche
La definizione di caratteristiche facilmente misurabili e confrontabili di una rete è
un passo fondamentale per poter valutare le prestazioni di una rete di comunicazioni
anche di una certa complessità. Pensiamo al cammino che congiunge due host
consistente, fisicamente, in una sequenza di canali e nodi di commutazione che
possono presentare caratteristiche anche molto differenti tra loro (ad esempio il filo
elettrico oppure lo spettro radio). Tra le metriche più diffuse verranno successivamente
discusse il prodotto banda-ritardo, la capacità, e la banda disponibile.
3.3.1
Il prodotto banda ritardo
Questa metrica viene utilizzata per descrivere le caratteristiche di un singolo link. Il
ritardo di propagazione di un canale (noto anche come ritardo) è il tempo necessario
per trasferire un bit da un capo all’altro del canale stesso ed è caratteristico dello specifico mezzo trasmissivo utilizzato. Nelle comunicazioni a livello fisico, con il termine
bandwidth (larghezza di banda o banda) si fa riferimento all’ampiezza spettrale del
segnale elettromagnetico o alle caratteristiche del sistema di comunicazione. Invece,
nelle reti digitali, con il termine banda viene indicata la quantità di dati che il link è
in grado di trasmettere nell’unità di tempo. Dal momento che l’unità base è il bit, la
banda viene misurata solitamente in bit per secondo (bps), per le linee con capacità
dell’ordine dei Megabit 2 e Gigabit 3 viene utilizzato il Megabit per secondo (Mbps) o
il Gigabit per secondo (Gbps).
3.3.2
La capacità
Un segmento di rete è normalmente in grado di trasmettere dati ad un bit rate
costante, limitato sia dalla larghezza di banda del mezzo di propagazione fisico che
dalle tempistiche dei dispositivi di ricezione/trasmissione ottici o elettronici. Inoltre,
a livello IP, un collegamento consegna i pacchetti ad una velocità inferiore a quella
2
Il Megabit (Mb) è l’unità di misura più utilizzata per descrivere la capacità delle reti di
comunicazione ed equivale a 106 bit = 1.000.000 bit
3
Un Gigabit, abbreviato in Gbit o Gb, equivale a 109 bit = 1.000.000.000 bit
12
CAPITOLO 3. MISURAZIONI SULLE RETI
nominale 𝐶𝑛𝑜𝑚 a causa dell’overhead di incapsulamento 𝐻𝐿2 introdotto al secondo
livello. E’ quindi possibile definire la massima capacità 𝐶𝑖 sperimentabile a livello
IP come funzione della capacità nominale 𝐶𝑛𝑜𝑚 , della quantità di overhead 𝐻𝐿2
introdotta e della massima dimensione del pacchetto IP supportata dal link (MTU):
𝐶𝑖 = 𝐶𝑛𝑜𝑚
1
1+
𝐻𝐿2
𝑀𝑇 𝑈
Questa definizione, relativa ad un singolo collegamento, può essere estesa ad un
intero cammino lungo la rete, per indicare il massimo rate di trasmissione supportato
per un trasferimento end-to-end. In questo caso è l’hop del percorso avente la capacità
inferiore, detto narrow link 4 , a determinare la capacità massima sperimentabile
end-to-end:
𝐶 = min 𝐶𝑖
𝑖=1,...,𝐻
3.3.3
La banda disponibile
La banda disponibile (available bandwidth) è definita come la quantità di capacità
inutilizzata di un link in un certo periodo di tempo ed è un’altro parametro per
caratterizzare le prestazioni di una rete. Mentre la capacità di un collegamento
dipende dallo specifico mezzo trasmissivo e dalle tecnologie impiegate, la banda
disponibile è un parametro tempo-variante anche legato alla quantità di traffico
presente sul link nel momento di osservazione. In un dato istante di tempo, infatti,
un link può generalmente essere impegnato nel trasferimento di un pacchetto al
massimo rate oppure essere inattivo (idle); l’utilizzo istantaneo 𝑈 del canale perciò
può essere solo 0 o 1.
Figura 3.3: Andamento nel tempo dell’occupazione della banda (da [4])
Ne consegue la necessità di definire la banda disponibile introducendo un intervallo
di tempo, sul quale verrà poi effettuata una media degli utilizzi istantanei. Detto
[𝑡 − 𝜏, 𝑡] l’intervallo di interesse, l’utilizzo medio nell’intervallo considerato 𝑈 (𝑡 − 𝜏, 𝑡)
è così definito:
𝑈 (𝑡 − 𝜏, 𝑡) =
1
𝑇
∫︁ 𝑡
𝑢𝑥 𝑑𝑥
𝑡−𝜏
4
Un termine molto utilizzato in questi casi è bottleneck, cioè collo di bottiglia; purtroppo
quest’ultimo in letteratura è stato alternativamente utilizzato per indicare sia il link avente la
capacità minima, sia quello con la banda disponibile minima.
CAPITOLO 3. MISURAZIONI SULLE RETI
13
A questo punto è immediato ricavare la banda media disponibile (o, più brevemente, banda disponibile) per l’𝑖-esimo hop in questione e riferita allo stesso intervallo
di tempo; questa infatti altro non è che la percentuale inutilizzata di capacità:
𝐴𝑖 = (1 − 𝑢𝑖 ) · 𝐶𝑖
Il concetto può poi essere esteso per un cammino composto da un numero qualsiasi
𝐻 di hop; in questo caso la banda disponibile sperimentabile dai due end point è
pari al valore minimo misurabile sui link attraversati dalla trasmissione.
𝐴 = min 𝐴𝑖
𝑖=1,...,𝐻
Il cammino avente maggior disponibilità di banda, cioè percentuale di utilizzo
maggiore, è detto tight link.
3.3.4
Altre Metriche
Oltre alle metriche citate in precedenza, esistono numerose altre metriche per
descrivere lo stato di una rete, ad esempio la Bulk Trasfer Capacity (BTC), una
misura della velocità di una rete nel trasferire dati attraverso una singola connessione
TCP ideale (sfrutta il protocollo TCP molto utilizzato in internet). Altre metriche
interessanti sono: la latenza in una direzione (OWD, One Way Delay), il Round Trip
Time (RTT) [30; 31] utilizzato in particolare per i cammini asimmetrici (Figura 3.4),
o il tasso di perdita dei pacchetti [32].
Figura 3.4: Round Trip Time (RTT)
Capitolo 4
Stima della banda disponibile e
il tool pathChirp
Ci sono soltanto due possibili conclusioni: Se il
risultato conferma le ipotesi, allora hai appena fatto
una misura. Se il risultato è contrario alle ipotesi,
allora hai fatto una scoperta.
Enrico Fermi
Quando un nodo genera pacchetti ad un rate inferiore a quello del link a cui è
collegato, una certa porzione della banda disponibile del canale rimane inutilizzata;
questo surplus, corrispondente in Figura 4.1 alla distanza tra i pacchetti, rappresenta
la banda disponibile che può essere teoricamente utilizzata per altre trasmissioni.
Figura 4.1: Esempio di un canale completamente utilizzato (a) e di un secondo con
ancora una porzione di banda disponibile (b) (Fonte [2])
Nel caso di un cammino di rete composto da più link, la banda disponibile
equivale, invece, al surplus inferiore tra tutti i link presi in considerazione. Per
mostrare in modo efficace questa situazione viene spesso utilizzato un grafico in cui
il traffico è modellizzato come un liquido e i link come tubature (Figura 4.2), in cui
la larghezza 𝐴𝑖 rappresenta la capacità del link e lo spazio libero 𝐶𝑖 rappresenta
la portata inutilizzata, ossia la banda disponibile. Grazie a questo tipo di grafico,
si può facilmente notare che non sempre il link con minore capacità coincide con
14
CAPITOLO 4. STIMA DELLA BANDA DISPONIBILE E IL TOOL PATHCHIRP15
quello con minor banda disponibile: infatti, una pecca di questa modellizzazione è
di introdurre una forte semplificazione del processo preso in esame, trascurando la
natura discreta dei pacchetti e la variabilità del traffico su diverse scale temporali.
Figura 4.2: Cammino di rete visto come una tubatura
4.1
Campi di applicazione della stima della banda disponibile
L’individuazione di metodi affidabili ed efficaci di stima della banda disponibile è
una necessità per molte applicazioni data-intensive, quali ad esempio il trasferimento
di file o la distribuzione di contenuti multimediali, ove la disponibilità della rete
ha un impatto diretto sulle performance degli stessi servizi. Altre applicazioni e
componenti tecnologiche possono poi utilizzare proficuamente la conoscenza della
banda, come ad esempio le applicazioni P2P, le quali formano dinamicamente la rete
tra gli utenti in funzione della banda disponibile tra i vari peers. Discorso analogo
alle reti peer-to-peer potrebbe valere per tutte le overlay network, che sono in grado
di configurare le proprie regole di instradamento in base alla banda dei diversi link.
Questo tipo di misurazioni, viene molto utilizzato anche dai diversi operatori
che pianificano incrementi nella capacità della rete, basandosi sul tasso di crescita
dell’utilizzo della stessa da parte degli utenti. I medesimi operatori di rete fatturano
spesso ai clienti in base alla quantità di banda disponibile acquistata, definita in un
Service Level Agreement. Un’ulteriore tecnologia, destinata a conquistare sempre
più utenti (e fette di mercato), nonchè in grado di trarre grandi benefici dalla stima
della banda è il Voice over IP (VoIP); grazie alla possibilità di variare il livello di
compressione della voce è infatti possibile adattare la qualità del suono in funzione
del traffico presente in rete, mantenendo così un buon livello di fluidità del parlato.
4.2
Lo stato dell’arte
Come si è potuto leggere nel capitolo precedente, i campi di applicazione della stima
della banda disponibile sono numerosi; al contrario sono pochi i lavori focalizzati
su di essa, se paragonati alla quantità di ricerche che hanno per cardine la misura
CAPITOLO 4. STIMA DELLA BANDA DISPONIBILE E IL TOOL PATHCHIRP16
della capacità. Per poter meglio illustrare lo stato attuale dell’arte, si è cercato di
individuare le caratteristiche di fondo dei diversi metodi proposti negli anni. Gli
strumenti (tool) di misura, attualmente disponibili, riassunti in 4.1, sono quindi stati
raggruppati in tre macro-categorie in base al principio di funzionamento.
Famiglia
Affini
PGM
PRM
Metodo
Packet-Pair
Cprobe
Coefficiente 𝛽
Delphi
IGI
Spruce
TOPP
PTR
pathChirp
Pathload
BART
ASSOLO
Anno
1995
1996
1998
2000
2003
2003
2000
2003
2003
2003
2006
2008
Tabella 4.1: Tool per la stima della banda attualmente disponibili.
4.2.1
I modelli affini
All’interno di questa categoria troviamo strumenti che, seppur differenti tra loro,
hanno la caratteristica comune di non individuare direttamente la banda disponibile
ma altri parametri ad essa collegati. I primi tentativi di misurare la banda disponibile
sono misure indirette: tra questi vanno elencati il metodo Packet Pair, proposto da
Keshav, i pionieristici tool Cprobe e pipechar, così come il coefficiente relativo di
banda disponibile 𝛽, definito da Paxson. Non tutte queste tecniche sono nate come
affini ma, ad una analisi più approfondita, hanno mostrato come in realtà quanto
misurato non fosse effettivamente la banda disponibile.
Packet Pair
Il primo tentativo di stima della banda disponibile effettuando misurazione end-toend risale al 1995 e si deve a Keshav [33; 34]. Il metodo Packet Pair da lui proposto
si basa sull’effetto di spaziatura introdotto dai router intermedi strozzanti: due
pacchetti, aventi uguale dimensione, vengono inviati in sequenza lungo la rete ed
il destinatario, una volta ricevuti, risponde inviando a sua volta due pacchetti di
conferma al mittente. La banda disponibile viene ricavata calcolando la dispersione,
cioè la differenza nei tempi di arrivo, dei pacchetti; questo è possibile solo se si
ipotizza che la dispersione dei pacchetti di ACKnoledgment sia la medesima di quelli
inizialmente spediti. In altre parole, occorre supporre che tutti i router intermedi
adottino una politica di Fair Queuing per-flow. L’idea di ottenere informazioni
dalle tempistiche dei pacchetti di conferma, anzichè direttamente da quelli di prova,
CAPITOLO 4. STIMA DELLA BANDA DISPONIBILE E IL TOOL PATHCHIRP17
nasconde delle insidie: per fare solo alcuni esempi, potrebbero esistere instradamenti
asimmetrici oppure fenomeni di interferenza su canali condivisi tra i pacchetti di
misura e gli ACK. L’ipotesi di gestione delle code con schedulazione FQ su tutti i
router è, poi, nella realtà, eccessivamente restrittiva; come già detto, la disciplina più
adottata in Rete è infatti FCFS. Poiché i flussi che attraversano i link non vengono
quindi trattati in maniera equa, il metodo proposto è sostanzialmente inutilizzabile
in Internet e nelle reti locali.
Cprobe
Cprobe [35], primo metodo effettivamente implementato in un software di misurazione, utilizza un approccio simile a Packet Pair: in entrambi viene infatti sfruttata
la dispersione dei pacchetti di probe, ricavando le tempistiche dalle conferme. La
principale differenza rispetto a Packet Pair è nel numero di pacchetti inviati: anzichè
una coppia, questo metodo prevede l’invio di un treno (train) di otto pacchetti
consecutivi, tutti back-to-back. Un approccio analogo è stato utilizzato nel software
pipechar, ipotizzando, anche in questo caso, che la dispersione dei treni di pacchetti
sia inversamente proporzionale alla banda disponibile. A differenza di Packet Pair,
gli autori di Cprobe non hanno ipotizzato l’impiego della disciplina FQ sui nodi
intermedi; in tempi più recenti, è stato dimostrato come, senza questa ipotesi, la
misura ottenuta si riferisca ad un valore più propriamente chiamato Asymptotic
Dispersion Rate (ADR), parametro legato alla banda disponibile, ma non coincidente
con essa.
Coefficiente 𝛽
Fra il 1997 e il 1998 Vern Paxson [36], dell’Università californiana di Berkley, ha
definito il coefficiente 𝛽, una misura relativa dell’utilizzo di un cammino di rete.
La definizione di questa metrica è basata sulla variazione del ritardo sperimentato
in una direzione da un flusso di pacchetti: 𝛽 riflette la percentuale del ritardo dei
pacchetti imputabile al carico introdotto in rete dal flusso stesso. Perciò, se ogni
pacchetto viene accodato direttamente dietro il predecessore, il percorso di rete
può essere considerato scarico e 𝛽 ≈ 1. Al contrario, se le variazioni nel ritardo
sono sostanzialmente tutte dovute alla presenza di cross-traffico, il percorso di rete
considerato è prossimo alla saturazione e 𝛽 ≈ 0. Rispetto alla classica concezione di
utilizzo, dove valori prossimi allo zero indicano scarso carico e viceversa, 𝛽 ha perciò
un significato opposto. Il coefficiente è ricavato ipotizzando che il tight link ed il
link con capacità inferiore coincidano, evento non sempre verificato. A questa ipotesi
limitativa si aggiunge il problema che, anche supponendo che ciò sia vero, non è
chiaramente definibile la relazione tra 𝛽 e la quantità effettiva di banda disponibile.
4.2.2
I modelli di gap probing (PGM)
Il PGM sfrutta le informazioni sulla distanza dei tempi che separano l’arrivo sul
destinatario di due pacchetti di probe. Una coppia di questi viene infatti inviata
con una distanza interna Δ𝑖𝑛 e, una volta giunta a destinazione, presenta un gap
temporale tra i due pacchetti pari a Δ𝑜𝑢𝑡 . Ipotizzando che vi sia una singola strozzatura e che la coda associata non venga svuotata nel tempo che intercorre tra l’arrivo
CAPITOLO 4. STIMA DELLA BANDA DISPONIBILE E IL TOOL PATHCHIRP18
del primo e del secondo pacchetto, Δ𝑜𝑢𝑡 corrisponde al tempo impiegato dal link
con banda disponibile minore per trasmettere il secondo probe packet ed il traffico
ricevuto nell’intervallo Δ𝑖𝑛 .
Figura 4.3: Principio di funzionamento dei metodi PGM (tratto da [5])
Pertanto, il tempo impiegato per trasmettere il cross-traffico è Δ𝑜𝑢𝑡 − Δ𝑖𝑛 e
(Δ𝑜𝑢𝑡 −Δ𝑖𝑛 )·𝐶 il relativo rate, dove 𝐶 indica la capacità del link strozzante, supposta
nota. La banda disponibile è pari a:
Δ𝑜𝑢𝑡 − Δ𝑖𝑛
𝐴=𝐶 · 1−
Δ𝑖𝑛
(︂
)︂
Tra i tools di questa categoria ricordiamo Delphi, IGI, Spruce e BART.
Delphi
Delphi [37] è un metodo che adotta un approccio interessante nel problema della
stima, utilizzando un modello statistico di descrizione del cross-traffico per calcolare
la banda disponibile. Utilizzando un modello multifrattale wavelet (MWM) e tecniche
di stima Bayesiane, il tool è in grado di descrivere le caratteristiche del traffico su
diverse scale temporali, nonchè il comportamento delle code, effettuando misurazioni
poco invasive. In particolare Delphi introduce il concetto di chirp, un treno di
pacchetti distanziati tra loro da un tempo esponenzialmente crescente; questa idea,
seppur utilizzata in tutt’altro modo, è stata ripresa successivamente da un altro
software. Delphi ipotizza però che gli accodamenti avvengano solamente sul canale
limitante, che deve essere contemporaneamente tight e narrow link. Inoltre, per
valutare la banda disponibile, la capacità di quest’ultimo deve essere nota a priori.
IGI
Initial Gap Increasing (IGI) è un metodo di stima ibrido proposto da Hu e Steenkiste
[38; 39], in grado di ricavare la stima in maniera diretta inviando treni di pacchetti
ma determinando il rate di trasmissione in maniera iterativa, come accade con TOPP
o PTR. Nonostante gli incoraggianti risultati ottenuti con IGI nei test in laboratorio,
prove effettuate sul campo in un secondo momento, hanno però fornito risultati poco
affidabili [5].
CAPITOLO 4. STIMA DELLA BANDA DISPONIBILE E IL TOOL PATHCHIRP19
Spruce
Spread PaiR Unused Capacity Estimate (Spruce) [5] è un altro tool basato sul Probe
Gap Model e quindi, analogamente a IGI e Delphi, presuppone l’esistenza di un
unico link strozzante nel cammino di rete. La differenza è che, al posto dell’utilizzo
di treni per ricavare i valori della banda disponibile, vengono inviate 100 coppie di
pacchetti ad un rate pari alla capacità del tight link (che si suppone nota). Inoltre,
per simulare campionamenti poissoniani, le coppie di pacchetti sono distanziate
da tempi di interarrivo esponenziali. Test condotti dagli stessi autori di Spruce,
dimostrano come questo approccio fornisca misurazioni più affidabili e sia meno
invasivo dei due strumenti precedentemente citati.
4.2.3
I modelli di rate probing (PRM)
I modelli PRM sono basati sul concetto di congestione autoindotta1 . L’idea di fondo
si basa su alcune evidenze empiriche, piuttosto che sulla costruzione di modelli
statistici di cross-traffico. Si suppone infatti che l’immissione in rete di traffico di
prova con un rate 𝑅, superiore alla banda disponibile 𝐴 del percorso, provochi
accodamenti lungo i router intermedi, fornendo così tempi di trasferimento crescenti.
Viceversa, come visibile in Figura 4.4, inviando un certo numero di pacchetti ad una
velocità 𝑅 < 𝐴, non verranno sperimentati ritardi crescenti.
Il modello di rate probing viene utilizzato da diversi software quali TOPP,
Pathload/SLoPS, PTR Pathchirp e ASSOLO.
Figura 4.4: Principio alla base dei metodi PRM (Fonte [6])
Train of Packet Pairs
Trains of Packet Pairs (TOPP) [40] è l’esempio classico di misurazione iterativa; uno
stream, costituito da più coppie di pacchetti e caratterizzato da un certo rate, viene
1
Autoindotta in quanto è lo stesso software di misura che volutamente immette, per un breve
periodo di tempo, un traffico ad una velocità maggiore di quanto possa essere gestito dalla rete
senza accodamenti
CAPITOLO 4. STIMA DELLA BANDA DISPONIBILE E IL TOOL PATHCHIRP20
spedito verso il destinatario. Basato sul principio della congestione autoindotta, questa tecnica incrementa linearmente il rate per le trasmissioni successive, individuando
così il rate massimo di invio oltre il quale si manifestano fenomeni di congestione. In
aggiunta a ciò, TOPP è anche in grado di stimare la capacità del tight link, che può
essere superiore a quella del cammino di rete considerato. DietTOPP [41] utilizza
una versione ridotta dell’algoritmo alla base di TOPP, implementando un algoritmo
di ricerca modificato per l’impiego nelle reti wireless.
Pathload
Pathload [42; 43] è un software piuttosto noto che implementa la metodologia di
misura Self-Loading of Periodic Streams (SLoPS). SLoPS prevede l’invio di flussi
periodici, composti da ≈ 100 pacchetti aventi dimensioni uguali, ad un determinato
rate 𝑅. Così come prevede TOPP, il valore 𝑅 di spedizione viene adattato in base
alla variazione dell’One Way Delay dei pacchetti di probe. Le differenze tra i due
metodi sono principalmente a livello di analisi statistica delle misurazioni; inoltre,
mentre TOPP incrementa il rate linearmente, SLoPS utilizza una ricerca binaria per
convergere ad un valore di 𝑅 il più possibile vicino alla banda disponibile. poiché
la disponibilità di banda stimata può variare durante la misurazione, il risultato
potrebbe non mostrare chiari trend crescenti o stabili; in questi casi Pathload fornisce
un’area di incertezza (grey region) corrispondente all’intervallo di variazione entro
cui è compresa la banda disponibile.
PTR
Packet Transmission Rate (PTR) [39] è una tecnica proposta dagli stessi autori di
IGI ed è molto simile a TOPP, poiché basata su misurazioni iterative con variazione
lineare del rate di invio e convergenza della stima ad unico valore. A differenza di
TOPP, vengono però utilizzati treni di 60 pacchetti anzichè coppie.
pathChirp
PathChirp [7] è un ulteriore software basato sul principio di autocongestione. Anzichè
inviare trasmissioni periodiche di pacchetti a rate costante, pathChirp utilizza però
dei treni costituiti da pacchetti con distanze esponenzialmente decrescenti detti
chirp. Questo approccio consente di sperimentare diversi rate inviando un numero
di pacchetti estremamente contenuto, riuscendo inoltre a fornire un risultato con
un’unica trasmissione. Come illustrato in Figura 4.5, la banda disponibile 𝐴 può essere
individuata trovando il pacchetto in coincidenza del quale il traffico di misurazione
inizia a sperimentare ritardi crescenti.
ASSOLO
Available Bandwidth Smart Smoothing On-Line tOol (ASSOLO) [44] come detto in
precedenza è un derivato di pathChirp, pertanto utilizza lo stesso metodo di invio dei
pacchetti. ASSOLO inoltre elimina i problemi di sovrastima dell’applicativo da cui
deriva ed implementa il filtro VHF per il calcolo della stima della banda disponibile.
CAPITOLO 4. STIMA DELLA BANDA DISPONIBILE E IL TOOL PATHCHIRP21
Figura 4.5: Metodo di individuazione della banda disponibile 𝐴 utilizzato da
pathChirp e ASSOLO
BART
Bandwidth Available in Real-Time (BART) [39] è uno degli strumenti più recenti
proposti in questo settore; sviluppato congiuntamente da Ericson e gruppi di ricerca
universitari svedesi, è utilizzato per esperimenti nell’infrastruttura di rete europea
per le misurazioni Etomic2 . BART si basa sul principio di TOPP ma invia treni
di packet pairs a rate casuali e, ad ogni spedizione, effettua una stima della banda
disponibile in real-time utilizzando un filtro di Kalman [45].
4.3
I problemi della banda disponibile
Oltre ai già citati limiti delle misurazioni attive effettuate tramite traffico di probing, è
necessario affrontare altri problemi. Esistono numerosi fattori che possono influenzare
in maniera significativa l’accuratezza delle rilevazioni e che devono quindi essere
considerati in fase di progettazione di algoritmi e di analisi dei risultati ottenuti
[46; 47]. Il primo problema consiste nella natura delle ipotesi alla base dei modelli di
stima, che non permettono di descrivere esattamente le caratteristiche del traffico, i
meccanismi interni dei dispositivi di commutazione o la topologia di rete. Inoltre le
tempistiche software, spesso considerate trascurabili, possono in realtà essere fonte
di errori difficilmente evitabili. Alle complicazioni appena indicate si aggiungono
le difficoltà nel validare le stime ottenute: le simulazioni di laboratorio, per quanto
precise, non consentono di rappresentare adeguatamente tutti gli aspetti della realtà
mentre le prove sul campo non permettono di verificare con certezza i risultati.
2
Etomic (http://www.etomic.org) è parte del progetto di ricerca europeo Evergrow
CAPITOLO 4. STIMA DELLA BANDA DISPONIBILE E IL TOOL PATHCHIRP22
4.4
pathChirp
Basato sul concetto di congestione autoindotta (Probe Rate Model), già presentato
nella sezione 4.2.3, pathChirp modellizza il cammino di una rete di comunicazione
come una sequenza di nodi store-and-forward, ciascuno dei quali dotato di code
FCFS e caratterizzato da un tasso di servizio 𝜇 costante. Nonostante la semplicità del
modello, esso risulta, comunque, in grado di descrivere con sufficiente approssimazione
il comportamento di Internet. Lo schema utilizzato da pathChirp per determinare
la banda disponibile è innovativo e si basa sull’invio di sequenze, dette chirp, di
pacchetti distribuiti esponenzialmente. Questo pattern risulta estremamente efficiente,
dal momento che consente di inviare un minor numero di dati se confrontato con
altri algoritmi. Infatti i metodi derivati da Packet Pairs devono inviare 2𝑁 pacchetti
(cioè 𝑁 coppie) per poter studiare gli effetti su 𝑁 diverse spaziature; con un chirp è
possibile invece ottenere risultati analoghi spedendo solo 𝑁 + 1 messaggi. Inoltre,
decrementando esponenzialmente il tempo che separa due pacchetti successivi, la
quantità di traffico inviato cresce meno rapidamente del range della banda oggetto di
indagine. Un ulteriore vantaggio di tutti gli strumenti che inviano treni di pacchetti,
anzichè coppie, è la possibilità di sfruttare la correlazione esistente tra i ritardi
sperimentati dai vari pacchetti. PathChirp consente perciò di ottenere una stima
della banda disponibile in maniera rapida, relativamente affidabile e senza risultare
eccessivamente invasivo.
4.4.1
L’algoritmo di stima
Prima di procedere nella descrizione dell’algoritmo è opportuno introdurre la notazione che verà utilizzata nel resto della trattazione. Detto 𝑚 un generico chirp,
costituito da 𝑁 pacchetti di 𝑃 byte e distanziati esponenzialmente, si definisce 𝛾 il
fattore di spaziatura temporale tra essi. Il 𝑘-esimo pacchetto del chirp 𝑚, inviato
al tempo 𝑡𝑘 , sperimenta lungo il percorso un tempo di accodamento 𝑞𝑚 ; inoltre
la distanza tra il pacchetto 𝑘 ed il successivo è detta Δ𝑘 e, pertanto, il rate di
trasmissione istantaneo per il 𝑘-esimo pacchetto è
𝑅𝑘 =
𝑃
Δ𝑅
Ipotizzando uno scenario con cross-traffico fluido ideale e a bit rate costante
(CBR), si ha che
𝑞𝑘 = 0,
𝑞𝑘 > 𝑞𝑘 − 1,
se 𝐵[𝑡1 , 𝑡] ≥ 𝑅𝑘
altrimenti
Da questo si può ricavare facilmente la stima della banda media disponibile
nell’intervallo di tempo occupato dalla misurazione come
𝐴𝑎𝑣𝑔 = [𝑡1 , 𝑡𝑁 ] = 𝑅𝑘
corrispondente cioè alla velocità di trasmissione del pacchetto 𝑘 * , in corrispondenza del quale i ritardi di accodamento iniziano a mostrare un trend crescente. L’ipotesi
CAPITOLO 4. STIMA DELLA BANDA DISPONIBILE E IL TOOL PATHCHIRP23
di cross-traffico fluido CBR per l’intera durata della misurazione è ovviamente una
forte semplificazione della realtà che, per quanto efficace, non contempla la possibilità di sporadici picchi istantanei di traffico (burst) e l’esistenza di interazioni
tra i pacchetti. Per questo motivo gli autori di pathChirp hanno introdotto alcuni
accorgimenti, riuscendo a gestire in maniera efficace le interferenze di uno o più burst
con il treno di pacchetti di prova. Il grafico in Figura 4.6 rappresenta il profilo di un
chirp (signature), cioè l’andamento caratteristico dei tempi di accodamento rilevabili
per una misurazione.
Figura 4.6: Tipico andamento dei ritardi in un chirp (Tratto da [7])
Tipicamente è possibile individuare diversi spostamenti (più propriamente detti
escursioni) rispetto all’asse zero, in corrispondenza di ritardi imputabili a crosstraffico temporaneo. In questi casi, poiché il rate istantaneo 𝑅𝑘 non è comunque
superiore alla capacità del link strozzante, all’esaurirsi del picco di traffico le code
riescono ad accorciarsi e la signature ritorna a zero. L’ultima escursione invece, dal
momento che ha un rate 𝑅𝑘 maggiore di quello massimo supportato dal percorso
di rete attraversato, è la causa stessa dell’aumento della spaziatura tra i pacchetti.
PathChirp utilizza proprio il profilo per calcolare una stima 𝐸𝑘 della banda disponibile
per ogni coppia di pacchetti consecutivi. Successivamente viene trovato il surplus
di banda per-chirp 𝐷(𝑚) attraverso una media pesata dei vari valori 𝐸𝑘 ed infine è
fornita una stima, ottenuta calcolando una media delle varie misure 𝐷 ricavate in
una finestra temporale ampia 𝜏 .
La segmentazione binaria del profilo appena citata, è la stessa implementata
in ASSOLO, pertanto ulteriori e più approfondite spiegazioni sono reperibili nel
paragrafo 5.2.
4.4.2
Calcolo della stima della banda disponibile
Per quanto riguarda il calcolo della stima della banda disponibile pathChirp, utilizza
un semplice filtro a media mobile (MA). Questo sistema risulta estremamente
semplice ed equivale ad effettuare una media degli ultimi 𝑛 valori3 .
𝑀𝑡 + 𝑀𝑡 − 1 + ... + 𝑀𝑡−𝑛+1
𝐴𝑡 =
𝑛
3
il valore n é detto anche apertura della finestra
CAPITOLO 4. STIMA DELLA BANDA DISPONIBILE E IL TOOL PATHCHIRP24
La dimensione della finestra è quindi un parametro fondamentale per la caratterizzazione del comportamento del filtro. Sono infatti possibili due casi: quando 𝑛 assume
un valore elevato, l’effetto di misurazioni rumorose viene attenuato maggiormente
ma il sistema risulta piuttosto lento a reagire a bruschi cambiamenti; nella situazione
opposta , un numero minore di campioni considerati nella media consente di seguire
le variazioni molto rapidamente ma, allo stesso tempo, presenta maggior instabilità
e fluttuazioni, inseguendo anche i valori outlier. Il valore di default utilizzato da
pathChirp è pari a undici misurazioni. Il filtro a media mobile proposto dagli autori
di pathChirp risulta estremamente inefficiente poiché, nel calcolo della media, viene
assegnato lo stesso peso a misurazioni rumorose e rilevazioni esatte. Inoltre, variando
il numero di dati storici considerati nel calcolo della media, è possibile aumentare la
stabilità dei risultati o la velocità di risposta. Come già citato in precedenza questi
due aspetti risultano concorrenti, non è quindi possibile privilegiarne uno senza
danneggiare l’altro.
4.4.3
Il problema della sovrastima
Diversi studi comparativi tra i software per la stima della banda disponibile [18; 48],
pur confermando l’efficienza di pathChirp, hanno evidenziato come le stime ottenute
con questo software forniscano valori superiori del 10-20% rispetto all’effettiva
disponibilità di banda. Questa sovrastima, peraltro, persiste anche in totale assenza
di cross-traffico: su un cammino completamente scarico ad 1 Gb/s, il tool ha fornito
stime anche pari a 1100 Mbps. L’unica spiegazione fornita in passato [19] per questo
problema è purtroppo insoddisfacente: l’ipotesi di errori nel calcolo delle tempistiche
giustificherebbe infatti, come indicato dagli stessi ricercatori, misurazioni errate
in presenza di cammini con scarsa banda disponibile. Al contrario, il problema è
presente anche in reti completamente scariche e con quantità molto elevate di banda
disponibile; inoltre non è chiaro per quale motivo questi errori dovrebbero presentarsi
sistematicamente e comportare solo sottostime nel calcolo dei tempi. Anche nelle
prove effettuate in laboratorio, così come i risultati ottenuti dagli altri gruppi di
ricerca, si sono ottenuti risultati sovrastimati. In particolar modo, connettendo il
ricevente ed il destinatario con un link diretto a 100 Mbps e variando il tasso d’invio
dei chirp tra 10 e 200 Mbps (𝛾 = 1, 2), sono state ottenute misure sovrastimate di
circa il 15%. Questo problema è come è possibile verificare nel paragrafo 5.3 stato
corretto nel tool ASSOLO.
Capitolo 5
ASSOLO
Un esperto è uno che conosce alcuni dei peggiori errori
che può compiere nel suo campo, e sa come evitarli.
Werner Heisenberg
ASSOLO (Available Bandwidth Smart Smoothing On-Line tOol) è un applicativo
derivato da pathChirp per la stima della banda disponibile di una rete di calcolatori,
sviluppato presso il laboratorio reti dell’Università degli Studi di Pavia.
5.1
Modalità di funzionamento
Per effettuare una misurazione, ASSOLO necessita di tre host: come si può vedere
in Figura 5.1 vi è un host in cui viene eseguito il runner che chiama il reciver e
comunica le impostazioni per l’effettuazione della misura, a sua volta il reciver
contatta il sender, fornendogli le opportune informazioni per l’inizio delle operazioni.
A questo punto il sender inizierà l’invio dei chirp ed il reciver, una volta ricevuti i
pacchetti ed effettuati i calcoli, fornirà all’utente i risultati dell’operazione di misura.
In laboratorio, per evitare l’utilizzo di un ulteriore calcolatore, il runner è stato
mandato in esecuzione sullo stesso host del reciver, sfruttando l’interfaccia di rete
locale 127.0.0.1 o localhost.
Per quanto riguarda il metodo per la stima della banda disponibile, ASSOLO
invia attraverso la rete diversi treni chirp di pacchetti; i rate dei pacchetti all’interno
del chirp aumentano secondo un profilo innovativo denominato Reflected ExponentiAl
CHirp (REACH). Tale profilo permette una densità maggiore delle misurazioni nel
centro del range impostato dall’utente. ASSOLO elimina anche il problema della
sovrastima di pathChrip, problema di cui si è parlato nel capitolo quattro.
5.2
L’algoritmo di stima
Per poter calcolare con precisione 𝐸𝑘 , ASSOLO utilizza un algoritmo di segmentazione binaria del profilo, in grado di distinguere le sequenze corrispondenti ad una
escursione da quelle con un profilo costante; questo algoritmo è stato mutuato da
pathChirp. Dal momento che il principio su cui esso si basa è quello della congestione
autoindotta, vale il discorso precedentemente affrontato: ritardi crescenti dovuti ad
25
26
CAPITOLO 5. ASSOLO
Figura 5.1: Metodo di funzionamento di ASSOLO
accodamenti indicano che la banda disponibile è inferiore al rate istantaneo del chirp,
così come vale anche il contrario.
𝐸𝑘 ≥ 𝑅𝑘 ,
se 𝑞𝑘 ≥ 𝑞𝑘+1
(5.1)
𝐸𝑘 ≤ 𝑅𝑘 ,
altrimenti
(5.2)
La 5.2 vale solo nel caso in cui i pacchetti 𝑘 e 𝑘+1 possano effettivamente condurre
ad uno stato di temporanea congestione1 un nodo, ovvero che siano sufficientemente
ravvicinati. Pertanto, affinchè la 5.2 sia verificata, occorre segmentare ogni profilo
nelle regioni di escursione ed applicare la formula solamente ad esse. Intuitivamente,
se 𝑞𝑘 aumenta e rimane al di sopra dello zero per diversi pacchetti consecutivi, è
allora probabile che questi appartengano al medesimo busy period. Nello specifico,
l’algoritmo di segmentazione implementato da ASSOLO opera nel seguente modo
per riuscire a determinare l’𝑖-esimo ed il 𝑗-esimo pacchetto di 𝑚, rispettivamente
corrispondenti al primo e all’ultimo di un’escursione:
1. Il primo pacchetto 𝑖 della sequenza 𝑚 per cui vale 𝑞𝑖 < 𝑞𝑖+1 è un potenziale
inizio per l’escursione
2. Il punto 𝑗 di fine dell’escursione è definito come il primo pacchetto per cui vale
𝑞(𝑗)− <
𝑀𝑡 + 𝑀𝑡 − 1 + ... + 𝑀𝑡−𝑛+1
𝐹
dove 𝐹 è un parametro detto fattore di discesa. In altre parole, in 𝑗 la spaziatura
dovuta agli accodamenti relativa a 𝑞(𝑖) è diminuita di un fattore 𝐹 rispetto al
massimo ritardo sperimentato nell’intervallo [𝑖, 𝑗].
1
Questa situazione viene detta anche busy period poiché la coda, per il periodo di tempo
considerato, non è mai vuota e il servente è sempre occupato
27
CAPITOLO 5. ASSOLO
3. Se la regione 𝑗 − 1 è sufficientemente lunga, ad esempio maggiore di un certo
valore 𝐿, allora la regione individuata corrisponde ad un’escursione e non ad
un errore isolato.
poiché l’ultima escursione è dovuta ad una congestione non-temporanea, esisterà
solitamente un pacchetto 𝑙 oltre il quale il profilo non tornerà mai a 0; questa
escursione verrà considerata diversamente nel calcolo di 𝐸𝑘 , come spiegato di seguito.
L’algoritmo calcola inizialmente 𝐸𝑘 , cioè la stima della banda relativa a ciascun
pacchetto 𝑘; questi valori sono quindi utilizzati, per la valutazione della disponibilità
di banda 𝐷 relativa all’intero chirp 𝑚, secondo tre modalità:
Caso I Se 𝑘 appartiene alla parte crescente, cioè 𝑞𝑘 > 𝑞𝑘+1 , di un’escursione che
torna a zero, allora vale
𝐸𝑘 = 𝑅𝑘
Caso II dove 𝑙 corrisponde all’inizio dell’escursione. Questo caso dovrebbe quindi
includere tutti i rate superiori alla banda disponibile del sistema: in realtà,
nel caso in cui il trend dei ritardi 𝑞𝑘 considerati sia decrescente seppur non
tornando a 0, si potrebbe ottenere una stima 𝐸𝑘 conservativa.
𝐸𝑘 = 𝑅𝑙 ,
∀𝑘 > 1
Caso III Per tutti i 𝑘 non compresi nei casi precedenti, ovvero quando 𝑘 non
appartiene ad una escursione o comunque nella parte con trend decrescenti
della spaziatura, 𝐸𝑘 viene posto:
𝐸𝑘 = 𝑅𝑙
Nel caso in cui l’ultima escursione della signature termini, 𝑙 viene scelto pari a
𝑁 . Il verificarsi di questa condizione significa che il range [𝑅𝑚𝑖𝑛 , 𝑅𝑚𝑎𝑥 ] di probe non
è sufficientemente ampio da includere il valore corrispondente alla banda disponibile:
in questo caso il software provvede ad aumentare e traslare lo spettro delle velocità
testate.
5.3
Correzione al problema della sovrastima
Come già descritto nei capitoli precedenti, un problema affligge l’applicativo pathChirp: la sovrastima [18; 48; 19]. In ASSOLO questo problema è stato corretto:
grazie all’analisi del codice si è notato come, curiosamente, tra i diversi tempi di
accodamento venisse erroneamente considerato anche quello sperimentato dal primo
pacchetto; poiché tutti i ritardi dei successori vengono calcolati utilizzando il primo
come riferimento, è facile intuire come questo non possa che valere sempre zero.
L’introduzione di questo valore superfluo, nell’analisi del profilo dei chirp, non ha
conseguenze rilevanti sul calcolo della media; occorre tuttavia considerare che, poiché
ad esso non è associato alcun rate di spedizione, il vettore contenente le velocità
di invio dovrebbe essere conseguentemente traslato di una unità. In altre parole,
l’introduzione del valore inutile tra i tempi di ritardo ha comportato un’errata
corrispondenza tra il profilo del chirp ed i valori di banda utilizzati.
CAPITOLO 5. ASSOLO
5.4
28
Nuovo algoritmo di stima
L’obiettivo principale di questo elaborato è quello di proporre un nuovo profilo dei
rate di invio dei pacchetti all’interno di un chirp; il profilo utilizzato da pathChirp
prevedeva l’aumento esponenziale della velocità di invio all’interno del treno di
pacchetti: questa situazione porta ad una maggiore densità di rilevazioni nella parte
bassa del range, scelto per effettuare le misure. Si è quindi pensato di creare un profilo,
che permettesse di avere una maggiore densità di misure nel centro del range scelto
per la stima della banda disponibile. In letteratura è presente un profilo comunemente
chiamato “a occhio di pesce” (FEAT) [8], il quale propone una densità maggiore di
rilevazioni nel centro del range. Questo profilo, rappresentato in Figura 5.2, prevede
l’invio di 1 pacchetto in corrispondenza dei rate precedenti e seguenti la regione
centrale (detta focus region), mentre all’interno di tale regione invia 𝑀 pacchetti.
Questo profilo risulta, quindi, più invasivo di ASSOLO, che invia un pacchetto
per ogni rate. Un secondo problema di FEAT è la mancanza di una formula per il
calcolo della banda disponibile (non viene definito il peso delle misurazioni della
focus region); infine, ma di non minore importanza, non viene descritto il metodo per
l’invio dei pacchetti all’interno del chirp. Si è quindi optato per un profilo innovativo
denominato Reflected ExponentiAl CHirp (REACH) che verrà esposto nei successivi
paragrafi.
Figura 5.2: Profilo a occhio di pesce (FEAT) (Fonte [8])
5.4.1
Profilo REACH
Il profilo REACH, risponde pienamente alla richiesta di avere una densità maggiore
di rilevazioni nel centro del range impostato per la misurazione; fornendo, quindi,
una maggiore precisione nella stima della banda disponibile nel centro del range
di misura. Questo viene realizzato facendo si che l’aumento dei rate di invio dei
29
CAPITOLO 5. ASSOLO
pacchetti di un chirp tenda a diminuire con l’avvicinarsi del valore centrale del
range, per poi aumentare una volta superato tale valore. Nello specifico partendo
dal valore centrale 𝐻 andando verso il valore massimo 𝑈 la distanza dei pacchetti
è esponenziale, così come sempre partendo da 𝐻 ed andando verso il minimo 𝐿 la
distanza tra i pacchetti aumenta esponenzialmente.
Preso quindi un istante 𝑧 nella parte superiore del range di misurazione, il
Δ𝑟𝑎𝑡𝑒 rispetto a quello precedente sarà crescente (decrescente se nella parte inferiore
dell’intervallo) ed è rappresentato matematicamente come:
𝑈 − 𝐿 |𝑧−1|
𝛾
2
Dove 𝜎 corrisponde alla soglia percentuale (default 5%) riferita al range di
misurazione, 𝑈 ed 𝐿 rappresentano i limiti inferiore e superiore del range, 𝛾 (default
1,2) rappresenta invece lo spread-factor. Da ciò che è stato detto si può notare dal
grafico in Figura 5.3 l’andamento dei Δ𝑟𝑎𝑡𝑒 assomiglia a due esponenziali riflesse
dall’asse delle ordinate.
Δ𝑧 = 𝜎
Figura 5.3: Andamento dei Δ𝑟𝑎𝑡𝑒
Il presupposto è quello di fare 𝑘 misurazioni nella parte bassa del range e
altrettante 𝑘 nella parte compresa tra 𝐻 e 𝑈 .
𝑌𝑗 = 𝐻 −
𝑘
∑︁
𝑈 − 𝐿 |𝑖|
𝜎
𝛾 ,
𝑖=1
2
se 𝑗 = 1
(5.3)
𝑈 − 𝐿 |𝑘−𝑗|
𝛾
,
∀𝑗 > 1
(5.4)
2
Dove 𝐻 corrisponde al valore centrale del range di misurazione e il valore 𝑘
corrisponde al numero dei rate provati in metà banda; se ne deduce che dati 𝑈 ed 𝐿
𝑌𝑗 = 𝑌𝑗−1 + 𝜎
30
CAPITOLO 5. ASSOLO
per sapere il numero dei pacchetti inviati, risulta necessario ricavare prima il numero
𝑘 di rate da provare per entrambe le aree di misurazione. Il risultato di quanto detto,
ossia la sequenza dei rate utilizzati per ottenere la banda disponibile, è visibile in
Figura 5.4.
Figura 5.4: Andamento rates invio con il profilo REACH
5.4.2
Il modello teorico
Si consideri la distribuzione caratteristica di un REACH inviato da ASSOLO per la
misurazione rappresentata in Figura 5.4 .
Supponendo che la banda di misurazione sia compresa tra 𝑈 e 𝐿, supposto 𝐻 il
valore centrale di tale range, in base a quanto detto sul funzionamento dell’algoritmo
di ASSOLO nelle equazioni 5.3 e 5.4, si può facilmente ricavare che:
𝑈 =𝐻+
𝑘
∑︁
Δ𝑖 =⇒ 𝑈 − 𝐻 = 𝜎
𝑖=1
𝑘
𝑈 − 𝐿 ∑︁
𝛾 |𝑖−1|
2 𝑖=1
(5.5)
da cui si ricava:
𝑈 − 𝑈 +𝐿
2
𝜎 𝑈 −𝐿
2
=
𝑈 −𝐿
2
𝜎 𝑈 −𝐿
2
=
𝑘
∑︁
𝑖=1
𝑘
∑︁
𝑖=1
𝛾 |𝑖−1|
(5.6)
𝛾 |𝑖−1|
(5.7)
31
CAPITOLO 5. ASSOLO
Semplificando opportunamente si ottiene:
1
𝜎
𝑘
∑︁
=
𝛾 |𝑖−1|
(5.8)
𝑖=1
A questo punto, definiamo 𝑆𝑘 come:
𝑆𝑘 =
𝑘
∑︁
𝛾 |𝑖−1|
(5.9)
𝑖=1
𝑆𝑘 = 1 + 𝛾 + 𝛾 2 + .... + 𝛾 𝑘
𝑆𝑘 𝛾 = 𝛾 + 𝛾 + 𝛾 + .... + 𝛾
2
3
(5.10)
𝑘+1
(5.11)
Raccogliendo quindi 𝑆𝑘 (𝛾 − 1) si ottiene:
𝑆𝑘 (𝛾 − 1) = 𝛾 𝑘+1 − 1
1
𝛾 𝑘+1 − 1
=
𝑆𝑘 =
𝛾−1
𝜎
𝛾
−
1
𝛾 𝑘+1 =
+1
𝜎
(5.12)
(5.13)
(5.14)
Da cui ricaviamo il risultato finale 𝑘
𝑘 = 𝑙𝑜𝑔𝛾
(︂
𝛾−1
+1 −1
𝜎
)︂
(5.15)
Tuttavia, si è pensato di tenere come ultimo valore da provare, l’ultimo precedente
i limiti impostati, per cui:
𝑘 ∈ N 𝑡.𝑐. 𝑈 ≥ 𝐻 +
𝑘
∑︁
Δ𝑖
(5.16)
𝑖=1
Pertanto la formula 5.15 viene corretta come di seguito:
𝑘 =
⌊︂
(︂
𝑙𝑜𝑔𝛾
𝛾−1
+1 −1
𝜎
)︂
⌋︂
(5.17)
Il numero di pacchetti rate provati è quindi 2𝑘 + 1, dove 2𝑘 è il numero dei rate
prima e dopo il valore centrale, a cui va aggiunto il rate 𝐻. Per quanto riguarda
invece il numero dei pacchetti inviati per ogni REACH si ricava aumentando di 1 il
numero dei rate testati, in quanto al primo pacchetto inviato non viene associato
alcun rate; pertanto il numero di pacchetti 𝑁 inviati per ogni REACH risulta
𝑁 = 2𝑘 + 2
32
CAPITOLO 5. ASSOLO
Se ne evince, quindi, che il numero di pacchetti inviati da ASSOLO per ogni REACH
non dipende dalla larghezza del range di misura impostato dall’utente, ma solamente
dal valore percentuale della soglia. Questa situazione dimostra che l’invasività del tool
è molto contenuta; altresì va ricordato che, in presenza di intervalli di misurazione
significativamente ampi, la precisione risulta non ottimale.
Ora, ricavato 𝑁 e utilizzando la formula 5.5 anche per la metà sinistra dell’intervallo di misurazione, la descrizione matematica dell’𝑖-esimo rate è la seguente:
𝑁
𝑅𝑖 = 𝐻 + sign 𝑖 −
2
(︂
)︂
𝑁
𝛾 |𝑖− 2 | − 1
·𝑆·
,
𝛾−1
𝑈 −𝐿
con 𝑆 = 𝜎
2
(︂
)︂
(5.18)
Da questa formula si può ricavare che l’andamento della densità dei pacchetti è
il seguente:
1
𝛼 − 𝑅𝑖
1
𝜌=
𝑅𝑖 − 𝛼
𝜌=
𝐿 < 𝑅𝑖 < 𝐻,
𝛼∈R
(5.19)
𝐿 < 𝑅𝑖 < 𝑈,
𝛼∈R
(5.20)
Nel grafico di Figura 5.5 si può notare come la densità di rilevazioni cresca nella
prima metà del range per poi diminuire nella parte dopo il valore 𝐻, mentre per
pathChirp risulta alta all’inizio e poi sempre decrescente. Si nota inoltre come per
ASSOLO la densità maggiore si ha in corrispondenza del centro dell’intervallo di
misurazione, e poiché una maggiore densità implica una maggiore precisione, si
evince che, ASSOLO risulta più preciso di pathChirp nel centro dell’intervallo di
misurazione.
5.5
Altre funzionalità implementate
Oltre alla già citata modifica del profilo di invio dei pacchetti, sono stati apportati
ulteriori cambiamenti a pathChrip. La modifica principale riguarda l’implementazione del filtro VHF, che si va ad affiancare all’originale filtro a media mobile. Di
rilevante importanza segnaliamo anche che l’applicazione è stata fatta eseguire su un
calcolatore in cui era presente il kernel Linux soft Real-Time. Inoltre, con le nuove
modifiche, è possibile, da parte dell’utente, inserire il valore di soglia per il calcolo
del numero dei pacchetti da inviare, e lo stesso utente può anche scegliere quale
filtro utilizzare per il calcolo della stima della banda disponibile.
5.5.1
Esecuzione di ASSOLO in Kernel Linux Soft Real-Time
Il kernel di Linux non è in grado di garantire prestazioni nativamente real-time,
anche se esistono diverse soluzioni che consento di ovviare a questa limitazione. RTAI
e RTLinux [49] sono due estensioni che trasformano GNU/Linux in un kernel hard
real time, inserendo anche il supporto per algoritmi di scheduling specifici per questo
ambito quali, ad esepio, EDF (Earliest Deadline First) e RM (Rate Monotonic). Per
poter sfruttare le funzionalità offerte da queste soluzioni è però necessario modificare
CAPITOLO 5. ASSOLO
33
Figura 5.5: Confronto fra le densità di misurazione fra ASSOLO e pathChirp
pesantemente il kernel ed il codice originariamente scritto per operare all’interno di
un ambiente non real-time.
Recentemente sono state sviluppate tecniche alternative per ridurre i tempi
di risposta delle applicazioni e rendere GNU/Linux un sistema soft real-time e
completamente prelazionabile (preemptable) [50]. Nel kernel Linux 2.6 è presente
l’opzione di configurazione CONFIG_PREEMPT_VOLUNTARY, che introduce
dei controlli per le più comuni cause che generano lunghi periodi di latenza, in modo
che il kernel possa cedere, volontariamente, il controllo ad un processo avente un più
elevato grado di priorità in attesa di esecuzione. Questo permette di limitare i lunghi
periodi di latenza (anche superiori al secondo), ma non eliminarli definitivamente.
Nello stesso kernel è presente un ulteriore opzione di configurazione, CONFIG_PREEMPT, che imposta la maggior parte del codice del kernel al di fuori della regione
di spinlock-protected. Con questa opzione, nel caso peggiore la latenza non supera
la decina di millisecondi, fornendo così ragionevoli garanzie sui tempi massimi di
attesa sperimentabili da un processo.
Inoltre, all’interno di questi kernel è stato introdotta anche la modalità tickless 2
[51], che consente alle chiamate di sistema POSIX timers e nanosleep() di avere
risoluzioni elevate (circa 1𝜇𝑠 su hardware comune). Questa funzione è trasparente ai
processi e, se attivata, rende i timer di sistema molto più precisi rispetto ai kernel
tradizionali.
Il kernel real-time utilizzato introduce una coppia di politiche di scheduling dei
processi: FIFO (First-In-First-Out) e RR (Round Robin) [52]. La seconda tecnica
assegna equamente la CPU a tutti i processi aventi la stessa priorità. Al contrario, lo
2
L’opzione àttivabile in fase di compilazione del kernel abilitando l’opzione CONFIG_HIGH_RES_TIMERS
34
CAPITOLO 5. ASSOLO
scheduler FIFO cede il controllo dell’intera CPU al processo avente massima priorità,
che non potrà essere interrotto da processi aventi priorità inferiore o uguale ad esso.
In Linux la politica di scheduling FIFO ha priorità maggiore di quella RR.
Per dare ad ASSOLO la massima priorità all’interno del sistema, è stata utilizzata
la funzione int set_real_time_priority() [53], che inserisce il processo nella coda
di scheduling FIFO con la massima priorità possibile. Ulteriori riferimenti sono
reperibili nell’appendice A.
5.5.2
Calcolo della stima della banda disponibile
ASSOLO, a fianco del filtro a media mobile utilizzato da pathChirp, implementa il
filtro VHF, un filtro lineare molto utilizzato nel campo economico.
VHF
Il filtro VHF (Vertical Horizontal Filter) [54] è un algoritmo utilizzato in abito
finanziario, settore a prima vista lontano dalle reti di comunicazione ma che ha
quotidianamente a che fare con problematiche analoghe. VHF è stato proposto dall’economista Adam White, è un filtro utilizzato per individuare i trend e l’affidabilità
nelle misurazioni. Considerando sempre una finestra storica di 𝑛 misurazioni, il
coefficiente proposto da White si calcola nel seguente modo:
𝑉 𝐻𝐹 =
| max𝑛 𝑀𝑡 − min𝑛 𝑀𝑡 |
∑︀
| 𝑛 𝑀𝑡 |
Il valore di VHF è tanto maggior quanto più marcato è il trend che stanno
iniziando ad assumere i dati in ingresso. La stima della banda 𝐴 all’istante 𝑡 è
valutata con la formula:
𝐴𝑡 = 𝑘 · 𝑉 𝐻𝐹 · 𝑀𝑡 + (1 − 𝑘 · 𝑉 𝐻𝐹 )𝐴𝑡−1
In ASSOLO è stato introdotto il parametro 𝑘, che permette di variare la velocità
di risposta.
Capitolo 6
Prove in laboratorio e risultati
ottenuti
Se hai mille idee e soltanto una risulta essere buona,
sii soddisfatto.
Alfred Nobel
Una volta terminata l’implementazione delle modifiche già citate nei capitoli
precedenti, si è passati alle prove su dei calcolatori effettivamente presenti su di una
rete reale. L’utilizzo di una rete reale è stato preferito a quello di un simulatore
di rete, in quanto quest’ultimo, pur di indubbia utilità in molte situazioni, è stato
ritenuto non in grado di rappresentare con sufficiente realismo tutte le componenti
rumorose ed i comportamenti imprevedibili del traffico e dei dispositivi di rete. Le
numerose prove eseguite hanno avuto come obiettivo principale quello di verificare
la validità del profilo REACH di ASSOLO. Successivamente sono stati confrontati i
risultati ottenuti con quelli forniti da alcune prove effettuate con il tool pathChirp.
6.1
La rete di prova
Presso il Laboratorio Reti dell’Università degli Studi di Pavia è stato organizzato un
testbed di sei calcolatori, collegati come in Figura 6.1, aventi come sistema operativo
Linux Ubuntu Server 8.04 LTS. Sui due host utilizzati per effettuare la misurazione
è stato istallato il kernel real-time 2.6.24: questo per permettere ai due tool utilizzati,
ASSOLO e pathChirp, di avere la massima priorità durante le prove di misurazione
della stima della banda disponibile. La relativa semplicità della rete è motivata dalla
necessità di poter disporre di un elevato controllo sul sistema di prova. Proprio
per questa ragione non sono stati effettuati test attraverso Internet: non potendo
conoscere l’esatta banda disponibile in ogni istante, sarebbe stato impossibile valutare
con precisione l’accuratezza delle misure.
Non va poi dimenticato che in una misurazione per la stima della banda disponibile, la possibilità di poter controllare la quantità ed il tipo di cross-traffico
immesso in rete permette di valutare con precisione i risultati ottenuti e garantisce la
riproducibilità degli stessi, componenti aleatorie permettendo. Esistono, a tale scopo,
numerosi strumenti in grado di generare diversi tipi di traffico: tra questi necessitano
35
CAPITOLO 6. PROVE IN LABORATORIO E RISULTATI OTTENUTI
36
di segnalazione il Poisson-traffic generator della Rice University (dagli stessi autori
di pathChirp), Iperf sviluppato dall’Università dell’Illinois e l’italiano Distributed
Internet Traffic Generator (D-ITG). Tra i tre tool citati la scelta è caduta su D-ITG.
Figura 6.1: Rete di prova utilizzata in Laboratorio
6.2
Configurazione utilizzata nei test
In questo paragrafo verranno elencate (anche grazie all’ausilio di tabelle) le impostazioni dei tre tool: ASSOLO, pathChirp e D-ITG, utilizzati per le prove svolte in
laboratorio.
6.2.1
ASSOLO
Per effettuare la stima, ASSOLO invia un treno di pacchetti UDP aventi dimensione
𝑃 e contenenti un timestamp inserito dal mittente in fase di spedizione. poiché non
è sempre possibile ipotizzare che gli orologi presenti sul mittente e sul destinatario
siano sincronizzati, il ritardo sperimentato da ciascun pacchetto viene calcolato
utilizzando come riferimento l’istante di ricezione del primo. Inoltre, poiché l’effettiva
durata ed entità degli accodamenti può variare notevolmente da link a link, non
viene utilizzato un livello prefissato per discriminare le varie sezioni del profilo. In
ASSOLO i parametri configurabili dall’utente sono numerosi: il fattore di dispersione
temporale 𝛾, il fattore di discesa 𝐹 ed la soglia 𝐿 per l’individuazione di un’escursione
provocata da un busy period. Analogamente, è possibile impostare il range di velocità
istantanee associate ad un chirp o l’occupazione media di banda associata al traffico
di prova. Altri parametri impostabili dall’utente sono la soglia percentuale 𝜎 riferita
al range di misurazione per il calcolo dei rate di invio (parametro -e da riga di
comando) e la scelta del filtro da applicare per il calcolo della stima della banda
disponibile (-f ).
L’applicativo affronta, inoltre, gli effetti indesiderati di comportamenti anomali
del sistema operativo o delle interfacce di rete. Ritardi nella gestione del traffico
di rete da parte del sistema operativo potrebbero, infatti, alterare la spaziatura
CAPITOLO 6. PROVE IN LABORATORIO E RISULTATI OTTENUTI
37
effettiva tra i diversi pacchetti, causando pesanti errori nella stima della disponibilità
di banda. Per questo motivo il programma scarta tutti i treni contenenti pacchetti
con tempi di interarrivo inferiori ad una certa soglia 𝑑. Il valore 𝑑 utilizzato nel
software è pari a 30𝜇𝑠; attualmente questo dato è modificabile solo intervenendo
sui sorgenti del programma e ricompilando l’applicativo. Occorre tuttavia precisare,
sebbene i risultati ottenuti in laboratorio siano soddisfacenti, che quella operata è
indubbiamente una scelta sub-ottima: per l’individuazione dei parametri ottimali si
dovrebbero tenere in dovuta considerazione la caratteristiche statistiche del crosstraffico e delle code intermedie, nonchè ipotizzare che queste non varino in alcun
modo durante le misurazioni.
Impostazione
high rate
low rate
packet sender
packet reciver
duration
treshold
filter
spread-factor
packet size
Opzione
(-u)
(-l)
(-S)
(-R)
(-t)
(-e)
(-f)
(-s)
(-p)
Valore Assegnato
200 [Mbps]
10 [Mbps]
192.168.3.1
127.0.0.1
30/60 [s]
5%
0
1,2
1000 [byte]
Tabella 6.1: Tabella configurazione di ASSOLO utilizzata in laboratorio.
6.2.2
pathChirp
Per quanto riguarda le prove effettuate con pathChirp, i parametri utilizzati sono
gli stessi del suo derivato ASSOLO, ad eccezione della scelta del filtro e del valore di
soglia percentuale riferito al range.
6.2.3
D-ITG
D-ITG [55; 9]è stato sviluppato presso il Dipartimento di Informatica e Sistemistica
dell’Università Federico II di Napoli e consente di inviare diversi tipi di traffico con
diverse possibili distribuzioni dello stesso; inoltre fornisce all’utente di impostare
ulteriori parametri quali il rate di invio e la durata. D-ITG fornisce anche un
dettagliato report riguardo l’invio del traffico con indicazioni sulla capacità, sul jitter
e sul tasso di perdita dei pacchetti spediti. Nello stesso applicativo è presente anche
la possibilità di creare dei grafici sull’andamento del cross-traffico durante le prove
effettuate; ne è un esempio il grafico di Figura 6.2. Come rappresentato in Figura 6.3
l’architettura del programma [10] si compone di sei parti: ITG Send, ITG Recv,
ITG Log, ITG Manager, TSP per l’azione di invio del cross traffico e ITG Dec per
l’analisi dei risultati. Per le prove in laboratorio si è scelto di inviare del traffico UDP
ad un bit rate costante 𝑋, sebbene il flusso Constant Bit Rate (CBR) generato sia
il più semplice tipo di traffico non ideale esistente. Occorre considerare, infine, che
CAPITOLO 6. PROVE IN LABORATORIO E RISULTATI OTTENUTI
38
qualsiasi software per la stima della banda deve essere in grado di fornire misurazioni
accurate, in presenza di cross-traffico costante prima di poter essere utilizzato in
reti più complesse.
Figura 6.2: Esempio di grafico realizzato con ITGPlot (Tratto da [9])
Opzione
-t
-a
-T
-x
-U
-c
-l
Significato
duration
destination address
protocol type
log file
uniformly distributed IDT
packet size
reciver logfile
Valore Assegnato
30000/60000 [ms]
2.06
UDP
nomefile
4000-4100 [pps]
1000 [pps]
nomefile
Tabella 6.2: Tabella configurazione di D-ITG utilizzata per le prove. (Ulteriori
riferimenti da [11])
6.3
Risultati ottenuti
Nelle pagine seguenti si possono trovare alcuni grafici, rappresentanti i risultati
ottenuti in laboratorio con diverse quantità di cross-traffico CBR presente sulla rete
di prova. Come si può facilmente verificare, nei grafici di Figura 6.4, Figura 6.5 e
CAPITOLO 6. PROVE IN LABORATORIO E RISULTATI OTTENUTI
39
Figura 6.3: Architettura tool D-ITG (Fonte [10])
Figura 6.6, ASSOLO fornisce ottimi risultati e se confrontati con il risultati ottenuti
da pathChirp, si nota una maggiore precisione ed una maggiore stabilità. Questi
miglioramenti sono dovuti, in particolare, all’utilizzo del nuovo profilo REACH
ed alla correzione apportata al codice originale; ciò per evitare la sovrastima che
affliggeva l’applicativo sviluppato dalle Università Rice e Stanford.
In Figura 6.7 si nota come la varianza nelle misurazioni di ASSOLO risulta
molto minore di quella delle misure effettuate con pathChirp. Inoltre il valore medio
misurato dal tool della Rice è meno preciso di quello rilevato con ASSOLO.
6.4
Confronto invasività ASSOLO - pathChirp
Oltre a verificare sperimentalmente la bontà delle misurazioni effettuate con ASSOLO,
nel capitolo precedente, si è cercato di ricavare formule in grado di descrivere con
precisione il traffico di prova utilizzato.
Come si può notare nel 5.4.2 l’invasività di ASSOLO è rappresentata con la
seguente formula:
⌊︂
𝑁
= 2 · 𝑙𝑜𝑔𝛾
(︂
𝛾−1
+1 −1 +2
𝜎
)︂
⌋︂
Da una precedente tesi [44] su pathChirp si può ricavare che l’invasività del tool
è rappresentabile secondo la formula :
𝑁
=
⌊︂
2+
1
𝑈
𝑙𝑜𝑔
𝑙𝑜𝑔𝛾
𝐿
(︂
)︂⌋︂
CAPITOLO 6. PROVE IN LABORATORIO E RISULTATI OTTENUTI
40
Figura 6.4: Confronto ASSOLO-pathChirp su rete a 100 Mbps nominali in assenza
di cross-traffico
Figura 6.5: Confronto ASSOLO-pathChirp con traffico CBR a 32 Mbps su rete a
100 Mbps nominali
CAPITOLO 6. PROVE IN LABORATORIO E RISULTATI OTTENUTI
41
Figura 6.6: Confronto ASSOLO-pathChirp con traffico CBR a 64 Mbps su rete a
100 Mbps nominali
Come si può facilmente notare il numero di pacchetti inviati da ASSOLO, non
dipende, a differenza di pathChirp, dalla larghezza del range di misurazione ma dalla
soglia percentuale (𝜎) inserita nel nuovo algoritmo.
Ipotizzando quindi di avere un range di misura [10 − 500]𝑀 𝑏𝑝𝑠, uno spread-factor
(𝛾) pari a 1,2 e la soglia 𝜎 = 5% per etrambi i tool, il risultato sarà che ASSOLO
invierà 18 pacchetti per ogni REACH, mentre il rivale 24 per ogni chirp. Aumentando
la larghezza del range di misura si può notare come il numero di pacchetti inviati
da ASSOLO rimane costante, mentre per pathChirp i pacchetti inviati aumentano.
La ridotta invasività di ASSOLO, tuttavia, porta ad una minore accuratezza dei
risultati della misurazione all’aumentare del range di misurazione; questa situazione
può essere corretta grazie al parametro 𝜎.
Rate min [Mbps]
10
10
10
50
50
Rate max [Mbps]
200
80
500
200
400
N ASSOLO
18
18
18
18
18
N pathChirp
18
13
24
10
14
Tabella 6.3: Tabella confronto invasivita ASSOLO-pathChirp con 𝛾=1,2 e 𝜎=5%.
Per quanto riguarda l’accuratezza nelle misure, per ASSOLO la massima si ha
se la banda disponibile è centrata con la metà dell’intervallo di misurazione, mentre
per quanto riguarda pathChirp, la migliore accuratezza si ottiene quando la banda
CAPITOLO 6. PROVE IN LABORATORIO E RISULTATI OTTENUTI
42
(a) ASSOLO
(b) pathChirp
Figura 6.7: Andamento delle varianze nelle misurazioni: a)ASSOLO b)pathChirp
CAPITOLO 6. PROVE IN LABORATORIO E RISULTATI OTTENUTI
43
disponibile è coincidente con la banda minima dell’intervallo di misura. Quindi,
ipotizzando di centrare l’itervallo di misurazione con la presunta banda disponibile,
ASSOLO fornirà una migliore accuratezza di pathChirp.
Ipotizzando quindi, che la banda disponibile 𝐴 sia centrata circa in 𝐻 (dove 𝐻
rappresenta il centro dell’intervallo di misurazione). Definendo 𝜀 come il massimo
errore possibile della misura corrispondente, sia ha che:
• per quanto riguarda ASSOLO
𝜀=
(︂
𝑈 −𝐿
𝜎
2
)︂
• per pathChirp invece
⃒
⃒
(︂
𝜀 = ⃒⃒−𝐵𝑚𝑖𝑛 𝛾 𝑛−2 1 −
1 ⃒⃒
𝛾 ⃒
)︂⃒
dove 𝑛 rappresenta l’𝑛-esimo pacchetto oltre per il quale la misura corrisponde
alla banda disponibile.
𝑅𝑎𝑡𝑒𝑚𝑖𝑛
10
10
10
50
50
𝑅𝑎𝑡𝑒𝑚𝑎𝑥
200
80
500
200
400
Available Bw
105
45
255
125
225
𝜖 ASSOLO
4,75
1,75
12,25
3,75
8,75
𝜖 pathChirp
17,83
10,32
53,25
29,86
51,59
Tabella 6.4: Tabella accuratezze ASSOLO-pathChirp ipotizzando la banda disponibile centrata nell’intervallo di misura, con 𝜎=5% e 𝛾=1,2. I valori in tabella sono
espressi in Mbps
Capitolo 7
Conclusioni
Sono convinto che l’informatica abbia molto in
comune con la fisica. Entrambe si occupano di come
funziona il mondo a un livello abbastanza
fondamentale. La differenza, naturalmente, è che
mentre in fisica devi capire come è fatto il mondo, in
informatica sei tu a crearlo. Dentro i confini del
computer, sei tu il creatore. Controlli - almeno
potenzialmente - tutto ciò che vi succede. Se sei
abbastanza bravo, puoi essere un Dio. Su piccola scala.
Linus Torvalds
I risultati ottenuti nelle prove di laboratorio hanno mostrato che l’innovativo
profilo REACH, implementato in ASSOLO, fornisce risultati stabili e, a differenza
di pathChirp, non presenta errori di sovrastima. Come è stato visto nella trattazione
di questo elaborato, ASSOLO eredita da pathChirp la caratteristica della poca
invasività nella misurazione, aumentando invece la precisione nella parte centrale del
range di misurazione, caratteristica non propria dell’applicativo della Rice. Tuttavia,
pathChirp ha dimostrato, ancora una volta, di essere uno strumento estremamente
valido e versatile, nonostante sia già passato un lustro dalla sua nascita.
La maggior precisione di misurazione nel centro del range di misurazione, è
una proprietà presente anche nel già citato profilo FEAT; ma, come è stato spiegato nei capitoli precedenti, numerosi sono i problemi di questa tecnica, a partire
dall’invasività, sesibilmente maggiore di quella di ASSOLO.
L’utilizzo in ASSOLO del sistema di filtraggio VHF, ha dimostrato come sia
possibile sfruttare le correlazioni esistenti tra misurazioni successive e ridurre notevolmente l’effetto di errori sporadici sui risultati finali. Sempre a questo riguardo,
sarebbe poi interessante approfondire il rapporto esistente tra i parametri di configurazione del filtro, le caratteristiche del traffico e le tempistiche di misurazione, per
poter così rendere automatica la taratura del sistema.
Come è stato visto, ASSOLO fornisce una migliore precisione quando la banda
disponibile è centrata col range di misurazione. Al momento, i due estremi dell’intervallo di misurazione vengono inseriti manualmente in avvio del programma:
uno sviluppo futuro del tool potrebbe essere quello di implementare una ritaratura
automatica del range, centrarandolo in base al valore fornito in un primo esperimento. Qualora invece la prima misura effettuata risultasse già appartenente all’area
44
CAPITOLO 7. CONCLUSIONI
45
centrale del range impostato, si potrebbe intervenire modificando la soglia 𝜎 (sempre
rimanendo nei limiti stabiliti), diminuendo così la quantità dell’errore.
Rimanendo, invece, sull’argomento della banda disponibile, possiamo tranquillamente affermare che il problema rimane ancora aperto e capace di offrire numerosi
spunti per nuove ricerche. A margine di ciò, riferiamo comunque che i risultati
ottenuti con ASSOLO e altri tool sono propri di una sufficiente precisione, e quindi
utilizzabili in diverse applicazioni presenti oggi sulle reti (streaming, VoIP, ecc.).
In questi ultimi anni, si è potuto assistere ad un notevole sviluppo delle applicazioni multimediali e ad una altrettanto notevole migrazione dei servizi (banche,
assicurazioni, enti, ecc.) verso procedure on-line; questo comporta un aumento delle
problemtiche legate alla qualità del servizio (Quality of Service o QoS). Quanto
appena citato risulta in aperto contrasto con il ridotto numero di strumenti di
misurazione sviluppati ed il nuemro di ricerche intraprese.
Ritornando, infine, ad ASSOLO, è ragionevole credere, che, mediante un utilizzo
opportuno dei protocolli di routing e di allocazione delle risorse e sfruttando le sue
caratteristiche, potrebbe essere impiegato con buoni risultati nella gestione della
qualità del servizio. Nello specifico, fornendo alle applicazioni che lo richiedono, un
servizio stabile e predicibile che permetterebbe di fornire all’utenza un aumento
dell’efficienza ed un costante controllo del servizio in rete.
Appendice A
Codice Sorgente
In questa appendice è presente l’implementazione del nuovo profilo REACH di
ASSOLO e la funzione per l’assegnazione della massima priorità real-time scheduling
al programma in esecuzione.
A.1
Implementazione Profilo REACH
Implementazione del profilo REACH (tratta dal file alloc_rcv.c)
/*update the chirp bit rates and interarrival times*/
void update_rates_iat()
{
int count;
double thr;
int k;
if (debug)
fprintf(stderr,"low rate=%f, high_rate=%f\n",
low_rate,high_rate);
thr=(soglia/100)*((high_rate-low_rate)/2);
k=(num_interarrival-1)/2;
/*caricamento dei vettori*/
rates[k] = ((high_rate + low_rate)/2);
for (count=0;count < k ;count++)
{
rates[k+count+1]=(rates[k+count]+
(thr*pow(spread_factor,count)));
rates[k-count-1]=(rates[k-count](thr*pow(spread_factor,count)));
46
APPENDICE A. CODICE SORGENTE
47
}
for (count=0;count<num_interarrival;count++)
{
rates[count]=rates[count]*1000000.0;
iat[count]=8*((double) pktsize)/rates[count];
if(debug)
fprintf(stderr,"count %d iat %.8f rates %f\n",
count,iat[count],rates[count]);
}
return;
}
A.2
Priorità real-time
Funzione che permette di dare al programma la priorità di real-time. Questa funzione
è stata implementata in assolo_rcv.c, assolo_run.c e assolo_snd.c.
int set_real_time_priority(void)
{
struct sched_param schp;
/*
* set the process to real-time privs
*/
memset(&schp, 0, sizeof(schp));
schp.sched_priority = sched_get_priority_max(SCHED_FIFO);
if(sched_setscheduler(0, SCHED_FIFO, &schp) != 0)
{
perror("sched_setscheduler");
return -1;
}
return 0;
}
Bibliografia
[1] Hui Zhou, Yongji Wang, Xiuli Wang, and Xiaoyong Huai. Difficulties in
estimating available bandwidth. In Communications, 2006. ICC ’06. IEEE
International Conference on, June 2006.
[2] Andreas Johnsson. Modeling, Implementation and Evaluation of IP Bandwidth
Measurement Methods. PhD thesis, Department of Computer Science and
Electronics, Mälardalen University, 2007.
[3] A. Pasztor. Accurate Active Measurement in the Internet and its Applications.
PhD thesis, Department of Electrical and Electronic Engineering, The University
of Melbourne, Feb 2003.
[4] Ravi Prasad, Manish Jain, and Constantinos Dovrolis. Effects of interrupt coalescence on network measurements. In Passive and Active Network Measurement,
volume Volume 3015/2004, pages 247–256. Springer Berlin / Heidelberg, 2004.
[5] Jacob Strauss, Dina Katabi, and Frans Kaashoek. A measurement study
of available bandwidth estimation tools. In IMC’03: Proceedings of the 3rd
ACM-SIGCOMM Conference on Internet Measurement, New York, NY, USA,
2003.
[6] R. Prasad, M. Murray, C. Dovrolis, and K. Claffy. Bandwidth estimation:
Metrics, measurement techniques, and tools, 2003.
[7] V. Ribeiro, R. Riedi, R. Baraniuk, J. Navratil, and L. Cottrell. pathchirp:
Efficient available bandwidth estimation for network paths. In Proceedings of
4th PAM Workshop, San Diego, CA, USA, April 2003.
[8] Qiang Wang and Liang Cheng. FEAT: Improving accuracy in end-to-end
available bandwidth measurement. In Global Telecommunications Conference
GLOBECOM ’06, pages 1–4, November 2006.
[9] Pescapè, Avallone, and Ventre. Analysis and experimentation of internet traffic
generator. New2an 2004, International Conference on Next Generation Teletraffic and Wired/Wireless Advanced Networking - St. Petersburg (Russia),
February 2004 ( http://www.new2an.org/ ), February 2004 2004.
[10] Antonio Pescapè, Donato Emma, Stefano Avallone, Alessio Botta, and Giorgio
Ventre. Presentation of d-itg, August 2008.
48
BIBLIOGRAFIA
49
[11] Stefano Avallone, Alberto Dainotti Alessio Botta, Walter de Donato, and Antonio
Pescapè. D-ITG2.6.1d-manual. University of Naples Federico II, May 2008.
[12] P. Baran.
On Distributed Communications.
Memorandum RM-3420-PR, 1964.
The Rand Corporation,
[13] G.D. Cole. Computer network measurements: techniques and experiments.
Technical report, University of California, Los Angeles, October 1971.
[14] L. Kleinrock and W.E. Naylor. On measured behavior of the arpa network. In
AFIPS Press, editor, National Computer Conference, volume 43, pages 767–780,
1974.
[15] V. Paxson, G. Almes, J. Mahdavi, and M. Mathis. Framework for IP Performance
Metrics. RFC 2330 (Informational), May 1998.
[16] Nevil Brownlee and Chris Loosley. Fundamentals of internet measurement: A
tutorial. CMG Journal of Computer Resource Management, Issue 201, 2001.
[17] Bruce B. Lowekamp, Brian Tierney, Les Cottrell, Richard Hughes-Jones, Thilo
Kielmann, , and Martin Swany. A hierarchy of network performance characteristics for grid applications and services. Global Grid Forum Proposed
Recommendation, May 2004.
[18] A. Shriram, M. Murray, Y. Hyun, N. Brownlee, A. Broido, and K. Claffy
M. Fomenkov. Comparison of public end-to-end bandwidth estimation tools
on high-speed links. In Proceedings of 6th PAM Workshop, Boston, MA, USA,
March 2005.
[19] A. A. Ali, F. Michaut, and F. Lepage. End-to-end available bandwidth measurement tools : A comparative evaluation of performances. ArXiv e-prints, June
2007.
[20] L. Kleinrock. Information Flow in Large Communication Nets - RLE Quarterly
Progress Report. PhD thesis, Massachusetts Institute of Technology, 1961.
[21] Janet Abbate. From ARPANET to INTERNET: a history of ARPA-sponsored
computer networks, 1966–1988. Thesis (ph. d.), University of Pennsylvania,
Philadelphia, PA, USA, 1994.
[22] R. Popescu-Zeletin. Implementing the iso-osi reference model. In SIGCOMM
’83: Proceedings of the eighth symposium on Data communications, pages 56–66,
New York, NY, USA, 1983. ACM Press.
[23] B. Schott, Alexander Clemm, and Ulf Hollberg. An iso/osi based approach
for modeling heterogeneous networks. In Martti Tienari and Dipak Khakhar,
editors, INDC, volume C-6 of IFIP Transactions, pages 377–389. North-Holland,
1992.
[24] Nan Ni and Laxmi Narayan Bhuyan. Fair scheduling in internet routers. IEEE
Transactions on Computers, 51(6):686–701, 2002.
BIBLIOGRAFIA
50
[25] J. Mahdavi and V. Paxson. IPPM Metrics for Measuring Connectivity. RFC
2678 (Proposed Standard), September 1999.
[26] Tobias Oetiker. Mrtg - the multi router traffic grapher. In LISA ’98: Proceedings
of the 12th USENIX conference on System administration, pages 141–148,
Berkeley, CA, USA, 1998. USENIX Association.
[27] A. Zanella, G. Procissi, M. Gerla, and M. Y. Sanadidi. TCP westwood: analytic
model and performance evaluation. In Global Telecommunications Conference,
2001. GLOBECOM ’01. IEEE, volume 3, pages 1703–1707, San Antonio, TX,
USA, 2001.
[28] Saverio Mascolo, Claudio Casetti, Mario Gerla, M. Y. Sanadidi, and Ren Wang.
Tcp westwood: Bandwidth estimation for enhanced transport over wireless links.
In MobiCom ’01: Proceedings of the 7th annual international conference on
Mobile computing and networking, pages 287–297, New York, NY, USA, 2001.
ACM Press.
[29] M. Gerla, M. Y. Sanadidi, Ren Wang, A. Zanella, C. Casetti, and S. Mascolo.
TCP westwood: congestion window control using bandwidth estimation. In Global Telecommunications Conference, 2001. GLOBECOM ’01. IEEE, volume 3,
pages 1698–1702, San Antonio, TX, USA, 2001.
[30] Anurag Acharya and Joel Saltz. A study of internet round-trip delay. Technical
Report CS-TR-3736, UM Computer Science Department, dec 1996.
[31] Srinivas Shakkottai, R. Srikant, Nevil Brownlee, Andre Broido, and kc claffy.
The rtt distribution of tcp flows on the internet and its impact on tcp based flow
control. Technical report, Cooperative Association for Internet Data Analysis CAIDA, feb 2002.
[32] Jean-Chrysotome Bolot. End-to-end packet delay and loss behavior in the
internet. In SIGCOMM ’93: Conference proceedings on Communications architectures, protocols and applications, pages 289–298, New York, NY, USA, 1993.
ACM Press.
[33] S. Keshav. Congestion Control in Computer Networks. PhD thesis, UC Berkeley,
sep 1991.
[34] S. Keshav. A control-theoretic approach to flow control. SIGCOMM Comput.
Commun. Rev., 25(1):188–201, 1995.
[35] Robert Carter and Mark Crovella. Measuring bottleneck link speed in packetswitched networks. Technical report, Boston University, Boston, MA, USA,
1996.
[36] Vern Paxson. End-to-end internet packet dynamics. In SIGCOMM ’97: Proceedings of the ACM SIGCOMM ’97 conference on Applications, technologies,
architectures, and protocols for computer communication, pages 139–152, New
York, NY, USA, 1997. ACM Press.
BIBLIOGRAFIA
51
[37] V. Ribeiro, M. Coates, R. Riedi, S. Sarvotham, B. Hendricks, and R. Baraniuk.
Multifractal cross-traffic estimation. In Proc. of ITC Specialist Seminar on IP
Traffic Measurement, September 2000.
[38] Ningning Hu and Peter Steenkiste. Estimating available bandwidth using packet
pair probing. Technical Report CMU-CS-02-166, School of Computer Science,
Carnegie Mellon University, Pittsburgh, PA 15213, Sep 2002.
[39] Ningning Hu and P. Steenkiste. Evaluation and characterization of available bandwidth probing techniques. IEEE Journal on Selected Areas in
Communications, 21(6):879–894, August 2003.
[40] B. Melander, M. Bjorkman, and P. Gunningberg. A new end-to-end probing
and analysis method for estimatingbandwidth bottlenecks. In GLOBECOM
’00, San Francisco, CA, USA, 2000.
[41] Andreas Johnsson, Bob Melander, and Mats Björkman. Diettopp: A first
implementation and evaluation of a simplified bandwidth measurement method.
In 2nd Swedish National Computer Networking Workshop, Karlstad, November
2004.
[42] Manish Jain and Constantinos Dovrolis. End-to-end estimation of the available
bandwidth variation range. In SIGMETRICS ’05: Proceedings of the 2005
ACM SIGMETRICS international conference on Measurement and modeling of
computer systems, pages 265–276, New York, NY, USA, 2005. ACM Press.
[43] Manish Jain and Constantinos Dovrolis. End-to-end available bandwidth: measurement methodology, dynamics, and relation with tcp throughput. IEEE/ACM
Trans. Netw., 11(4):537–549, 2003.
[44] Emanuele Goldoni. Nuovi approcci nella stima della banda disponibile in una
rete a pacchetto. Master’s thesis, Università degli Studi di Pavia, 2007.
[45] E. Hartikainen and S. Ekelin. Tuning the temporal characteristics of a kalmanfilter method for end-to-end bandwidth estimation. In End-to-End Monitoring
Techniques and Services, 2006 4th IEEE/IFIP Workshop on, pages 58–65, 03-03
April 2006.
[46] Manish Jain and Constantinos Dovrolis. Ten fallacies and pitfalls on end-to-end
available bandwidth estimation. In IMC ’04: Proceedings of the 4th ACM
SIGCOMM conference on Internet measurement, pages 272–277, New York,
NY, USA, 2004. ACM Press.
[47] V. Paxson and S. Floyd. Wide area traffic: the failure of poisson modeling.
IEEE/ACM Transactions on Networking, 3(3):226–244, June 1995.
[48] Yu-Chen Huang, Chun-Shien Lu, and Hsiao-Kuang Wu. Queuing delay propagation model (qdpm)-based queuing region determination for available bandwidth
estimation of multimedia qos. Technical Report TR-IIS-05-004, Institute of
Information Science, Academia Sinica, Taipei, Taiwan, 2005.
52
BIBLIOGRAFIA
[49] Ismael Ripoll. Rtlinux versus rtai. http://rtportal.upv.es/comparative/rtl_vs_rtai.html, 2002.
[50] Real-time f.a.q wiki.
ed_Questions.
http://rt.wiki.kernel.org/index.php/Frequently_Ask-
[51] Linux: High-res timers and ticketless. http://kerneltrap.org/node/6750.
[52] Round-robin task scheduling. http://www.cs.ru.nl/lab/rtai/exercises/6.RoundRobinScheduling/Exercise-6.html.
[53] Achieving
low-latency
response
times
under
linux.
http://www.linuxdev.com/pub/a/linux/2000/11/17/low_latency.html?page=4.
[54] Adam White. The vertical horizontal filter. Futures Magazine, Volume XX, No.
10:1–10, 1991.
[55] Stefano Avallone, S. Guadagno, Donato Emma, Antonio Pescapè, and Giorgio
Ventre. D-itg distributed internet traffic generator. In QEST, pages 316–317.
IEEE Computer Society, 2004.