Il bisogno di mezzi di comunicazione sempre pi `u veloci e performanti richiede uno sviluppo con-tinuo dell’intera struttura di comunicazione. Il potenziamento e la diversificazione dei dispositivi hardware dedicati allo scambio di dati `e sicuramente di fondamentale importanza nel migliorare le prestazioni di rete, ma non basta se ci sono delle inefficienze in altre parti del sistema. Purtrop-po all’innovazione degli strumenti fisici non sempre corrisPurtrop-ponde una ristrutturazione dell’architet-tura software, con il risultato di prestazioni sub ottimali anche con l’uso delle ultime innovazioni tecnologiche.
Gli argomenti di ricerca discussi in questa tesi affrontano i problemi legati alle inefficienze che il software pu `o introdurre in un sistema di comunicazione e l’ottimizzazione delle risorse a disposizione, e in particolare riguardano: i) strumenti di validazione e ottimizzazione distribuiti e ii) un framework ottimizzato per l’I/O dei pacchetti di rete.
I contributi di questo lavoro sono molteplici. Innanzitutto `e stata realizzata un’estensione del-l’emulatore di rete “dummynet” in grado di supportare canali di comunicazione tempo varianti. La possibilit `a di poter emulare un ritardo variabile apre la strada alla validazione di numerose ap-plicazioni, in particolare gli ormai diffusi link wireless, o di emulare il comportamento di nuove tecnologie delle quali non si ha a disposizione il dispositivo hardware, ma si conosce il protocollo di comunicazione.
Un ulteriore contributo `e stato l’integrazione dell’emulatore dummynet nel testbed di rete Plan-etLab. Questo nuovo strumento permette di sfruttare tutti i vantaggi dell’emulazione, senza perdere la possibilit `a di eseguire gli esperimenti in condizioni realistiche, che costituisce uno dei principali vantaggi di un sistema di testbed distribuito.
Infine, l’ultimo contributo ha riguardato l’analisi del framework “netmap” per l’ottimizzazione delle comunicazioni di rete e due casi di studio sull’argomento: OpenVSwitch e Click. L’inte-grazione della nuova libreria in tali strumenti ha fatto emergere come una semplice sostituzione della libreria libpcap con una versione ottimizzata permetta di raggiungere prestazioni notevoli, in particolare su OpenVSwitch si ottengono prestazioni da 780 Kpps fino a 3 Mpps, mentre con Click i miglioramenti vanno da 490 Kpps a 3.95 Mpps.
Il software realizzato comprende: l’estensione dell’emulatore dummynet al supporto di canali tempo varianti; il port dell’emulatore dummynet su sistemi Linux (fino alla versione pi `u recente 3.0) e Windows; le ottimizzazioni a dummynet in modo da poter ottenere delle buone prestazioni sul sistema multiutente PlanetLab e l’integrazione del framework netmap su Click e OpenWSwitch tramite la libreria netmapcap.
Indice
I
Emulazione
3
1 L’emulatore dummynet 7
1.1 Stato dell’arte sugli strumenti di emulazione . . . 8
1.1.1 Emulatori di link . . . 9
1.1.2 Emulazione di reti multihop . . . 10
1.2 Componenti dell’emulatore . . . 11
1.2.1 Pipes . . . 11
1.2.2 Selezione dei pacchetti: il classificatore ipfw . . . 13
1.2.3 Reti di tipo multipath e multihop . . . 14
1.2.4 Perdita dei pacchetti . . . 15
1.2.5 Gestione delle code . . . 16
1.2.6 Scheduling dei pacchetti . . . 16
1.2.7 Emulazione del MAC layer . . . 17
1.3 Emulazione di canali tempo varianti . . . 19
1.3.1 Realizzazione dell’estensione in dummynet . . . 20
1.3.2 MAC overheads . . . 20
1.3.3 Rumore . . . 21
1.3.4 Competizione per l’accesso al mezzo . . . 23
1.3.5 Link tempo varianti . . . 23
1.4 Il port su sistemi Linux . . . 24
1.4.1 Uno sguardo generale alle modifiche effettuate . . . 25
1.4.2 Agganciarsi allo stack di rete di Linux . . . 25
1.4.3 Rappresentazione del pacchetto nel kernel . . . 27
1.4.4 Altri servizi di sistema . . . 27
1.5 Il port su sistemi Windows . . . 28
1.5.1 Analisi dei requisiti . . . 28
1.5.2 Meccanismi di comunicazione tra kernel e user space . . . 29
1.5.3 Struttura dei pacchetti nel kernel di Windows . . . 30
1.5.4 Scelta del driver di intercettazione del traffico . . . 30
1.5.5 Operazioni di manipolazione dei pacchetti . . . 32
1.5.6 Gestione del timer e granularit `a di sistema . . . 32
1.5.7 Sytem time . . . 33
2 PlanetLab 35
2.1 Introduzione . . . 35
2.2 Il bisogno dell’emulazione su un testbed di rete . . . 35
2.3 Stato dell’arte sui testbed di rete . . . 36
2.3.1 Network testbed . . . 36
2.3.2 Emulazione di reti wireless . . . 37
2.4 Architettura della piattaforma PlanetLab . . . 37
2.4.1 Gestione dei nodi e degli sliver . . . 38
2.4.2 Il servizio vsys . . . 38
2.4.3 Integrazione con dummynetbox . . . 38
2.5 L’emulatore come componente software . . . 39
2.5.1 Vsys per dummynet: backend server . . . 40
2.5.2 Scelta dell’engine di emulazione . . . 40
2.5.3 Utilizzo in PlanetLab . . . 41
2.5.4 Isolamento tra gli utenti . . . 42
2.6 Ottimizzazione delle prestazioni . . . 43
2.6.1 Overhead dovuto al lookup delle regole . . . 43
3 Validazione 45 3.1 Studio sull’accuratezza e le prestazioni . . . 45
3.1.1 Accuratezza dell’emulatore . . . 45
3.1.2 Prestazioni . . . 48
3.2 Validazione emulatore wireless e planetlab . . . 49
3.2.1 Overhead dell’emulatore . . . 50
3.2.2 Accuratezza dell’emulatore . . . 52
3.2.3 Validazione dell’emulatore wireless . . . 53
II
Il framework netmap
57
3.3 Definizione del problema . . . 593.4 L’architettura . . . 60
3.5 libpcap, e libpcap su netmap . . . 61
3.6 Case studies . . . 63
3.6.1 Integrazione con OpenvSwitch . . . 63
3.6.2 Integrazione con Click . . . 68
3.7 Lavori correlati . . . 71
Introduzione
L’integrazione di dispositivi di comunicazione in oggetti di uso comune si sta diffondendo sempre pi `u e il bisogno di scambiare, memorizzare, manipolare dati ha portato alla necessit `a di mezzi di comunicazione sempre pi `u veloci, richiedendo uno sviluppo continuo dell’infrastruttura di comuni-cazione. Negli anni abbiamo anche assistito ad una diversificazione degli strumenti di accesso alla rete, con l’obiettivo di garantire una copertura capillare e con velocit `a nominali sempre maggiori.
Per far fronte alla maggiore richiesta di banda, si cerca di di potenziare i dispositivi di comu-nicazione, sottovalutando la presenza di possibili colli di bottiglia locati altrove. Infatti, il potenzia-mento dei dispositivi hardware dedicati allo scambio di dati, non sempre porta a dei miglioramenti nelle prestazioni, perch ´e se all’innovazione tecnologica degli strumenti fisici non corrisponde un opportuno adeguamento del software, questi miglioramenti non possono che essere limitati.
Per poter sfruttare al massimo le potenzialit `a offerte dalle nuove tecnologie occorrer `a quindi rinnovare tutti gli aspetti coinvolti nella comunicazione, strumenti fisici, canali di comunicazione, protocolli e applicazioni, individuando e risolvendo le possibili fonti di inefficienze.
Uno dei principali temi di ricerca del corso di dottorato ha riguardato l’ottimizzazione del flus-so dei dati negli strumenti flus-software, e ha cercato di fornire degli strumenti che aiutano ad indi-viduare eventuali malfunzionamenti e, in alcuni casi, di migliorare le prestazioni del sistema di comunicazione.
Per la validazione e l’ottimizzazione del software, gli argomenti trattati hanno riguardato il testbed di rete PlanetLab e l’emulatore dummynet. I testbed di rete sono tra gli strumenti pi `u utilizzati dai ricercatori nello sviluppo di protocolli di rete e sistemi distribuiti. Nel riprodurre il com-portamento di una rete, i testbed si dividono in due categorie: si affidano all’utilizzo di una rete completamente basata sull’emulazione, o fanno uso di una piattaforma di nodi distribuiti su Inter-net. Il primo approccio permette di ottenere risultati riproducibili, ma ha lo svantaggio di essere poco rappresentativo della situazione reale, mentre il secondo approccio mette a disposizione un ambiente realistico ma non fornisce uno scenario riproducibile. L’integrazione dell’emulazione in PlanetLab permette di sfruttare i vantaggi dell’emulazione senza perdere la possibilit `a di eseguire gli esperimenti in condizioni realistiche. Inoltre l’emulatore permette di validare il comportamento di nuove tecnologie, delle quali si ha solo la definizione formale del comportamento, ma non il dispositivo fisico o il software che le implementa.
Nelle ottimizzazioni che riguardano il sistema di comunicazione dei pacchetti dati, gli argomenti trattati hanno riguardato le inefficienze introdotte dal sistema nel forwarding dei pacchetti nello stack di rete del sistema. Il forwarding dei pacchetti a livello software `e stato da sempre utilizzato su sistemi operativi general purpose, ma in generale non viene considerata una valida alternativa a sistemi dedicati, a causa delle scarse prestazioni a rate elevati, causati dai troppi overhead del sistema operativo e dei device driver coinvolti nelle operazioni. Un approccio alternativo alla
gestione della comunicazione e dello scambio di pacchetti tra l’applicazione e il dispositivo fisico di comunicazione `e dato dal framework “netmap” e dalla libreria “netmapcap” che lo rende disponibile alle applicazioni pi `u diffuse.
Il software realizzato
L’analisi teorica sulle prestazioni di rete, sia nelle applicazioni che nel sistema operativo e nei device driver, ha portato alla realizzazione di strumenti software in grado di validare le applicazioni e migliorare le prestazioni delle stesse.
Nel campo degli emulatori `e stata realizzata un’estensione di dummynet in grado di supportare canali tempo varianti, permettendo di emulare canali wireless, o MAC layer arbitrari.
L’integrazione di tale emulatore in PlanetLab ha richiesto il port dell’emulatore sul sistema op-erativo Linux (anche nella versione per sistemi embedded basati su OpenWRT, e su Windows), nonch ´e dei programmi di backend e frontend per gestire la comunicazione e l’allocazione delle risorse agli utenti PlanetLab.
Il frameworknetmap `e stato invece integrato in due strumenti molto diffusi che fanno un in-tenso uso delle risorse di rete di un sistema. L’integrazione ha portato alla realizzazione di una libreria “netmapcap” che implementa la stessa API della nota libreria libpcap. Dal lavoro sono anche emersi dei colli di bottiglia, non legati all’I/O dei pacchetti che sono stati poi integrati nelle distribuzioni ufficiali delle applicazioni.
Organizzazione di questo documento
Il lavoro svolto viene presentato in due sezioni, una prima parte descrive il lavoro volto nell’am-bito degli emulatori e una seconda parte orientata all’analisi delle prestazioni di rete. La prima parte tratta l’emulatore di rete dummynet, ne dettaglia la struttura per componenti, i miglioramenti apportati al software, l’estensione all’emulazione di link tempo varianti e il port sul sistema Linux. Viene poi dedicato un capitolo al testbed di rete PlanetLab, alla sua architettura e all’integrazione di dummynet nella piattaforma. Infine viene analizzata l’accuratezza dell’emulatore e vengono af-frontati i problemi prestazionali (e la loro risoluzione) nell’integrazione con il sistema multiutente e distribuito di PlanetLab. Nella seconda parte viene presentato il lavoro sul frameworknetmap, la re-alizzazione della libreria “netmapcap” ed i problemi, soluzioni e prestazioni della sua integrazione in due software di rete largamente diffusi.
Il proliferare di servizi e applicazioni che utilizzano la rete su sistemi, piattaforme, mezzi trasmissivi diversi tra loro, porta con s ´e il problema della validazione delle applicazioni realizzate. La fase di testing del software ha come obiettivo quello di assicurare che il software realizzato svolga corret-tamente il compito per cui `e stato progettato. Un test ideale `e un test completo, dove si prendono in analisi tutti i possibili casi in tutte le possibili circostanze che si possono verificare. Come `e facile immaginare effettuare un test del genere richiederebbe un investimento non indifferente di risorse e non potrebbe comunque riprodurre tutti i mezzi di comunicazione e le situazioni che si possono verificare durante una comunicazione reale.
Per risolvere il problema ci si affida all’aiuto di emulatori di rete e testbed distribuiti. Gli em-ulatori di rete permettono di riprodurre il comportamento di canali trasmissivi partendo da una descrizione analitica o empirica del modello, e permettono di capire come si comporta il software in base al modello fornito. I testbed di rete invece forniscono una rete distribuita ed eterogenea di nodi, topologie ed applicazioni, permettendo di testare l’interazione dell’applicazione con il mondo esterno.
Nei capitoli che seguono verranno descritti alcuni dei pi `u utilizzati emulatori di rete, dummynet e un testbed di rete distribuito, PlanetLab. Nel primo capitolo vedremo in dettaglio cosa `e dummynet e cosa permette di fare, nel secondo capitolo vedremo i miglioramenti apportati al codice, in par-ticolare la realizzazione di un’estensione in grado di supportare un canale tempo variante. Nel terzo capitolo verr `a presentato il lavoro svolto sui testbed distribuiti, lo stato dell’arte nel campo degli emulatori e i testbed di rete, e uno studio sull’accuratezza e le performance dell’emulatore dummynet.
Capitolo 1
L’emulatore dummynet
Dummynet `e un emulatore che permette di eseguire degli esperimenti sul software in un ambiente di rete configurabile in base ai bisogni dell’utente. Questo software `e stato sviluppato tanti anni fa e grazie alla sua semplicit `a e versatilit `a si `e presto affermato tra uno degli strumenti pi `u noti ed uti-lizzati nell’ambito degli emulatori di rete. Inizialmente `e stato sviluppato su FreeBSD e Mac OS X, recentemente `e stato portato su sistemi basati su Linux e Windows.
Uno degli argomenti di questo studio sono gli emulatori di rete e in particolare dummynet [57], sviluppato una decina di anni fa e integrato nel sistema operativo FreeBSD, che ormai risulta essere uno degli strumenti pi `u diffusi ed utilizzati [2]. Alla base della sua diffusione ci sono tre fattori fondamentali, la disponibilit `a immediata, la curva di apprendimento e l’insieme di funzionalit `a di cui dispone.
Per quanto riguarda la disponibilit `a dummynet `e un componente standard di FreeBSD da pi `u di dieci anni, e di Mac OS X dal 2006. Oltre alla disponibilit `a immediata in tali sistemi, sin dal-l’inizio del suo sviluppo `e stato distribuito in un sistema live, in grado di creare dei bridge abilitati con dummynet senza distruggere il contenuto installato sui dischi dei PC. In questo modo, il sis-tema di emulazione risulta installato ed operativo immediatamente, come illustrato in Figura 1.1, a prescindere dal sistema operativo installato sulle macchine.
Figura 1.1: Un bridge con delle immagini di dummynet installate a bordo `e immediatamente operativo e pu `o essere inserito con facilit `a in una topologia di rete gi `a esistente.
Per quanto riguarda la curva di apprendimento, l’interfaccia utente `e stata accuratamente pro-gettata in modo da permette la configurazione l’emulatore con dei semplici comandi, come ad
esempio:
# define bandwidth and delay of the emulated link ipfw pipe 1 config bw 3Mbit/s delay 32ms
# pass all traffic through the emulator ipfw add pipe 1 ip from any to any
Partendo da questa semplice configurazione, si possono aggiungere ulteriori opzioni e configu-razioni del link, in modo da arrivare gradualmente ad una configurazione completa del link.
Sin dalla sua versione originale dummynet `e stato ampliato, le funzionalit `a disponibili agli utenti sono state estese, specialmente dalla sua prima implementazione in [57]. La versione pi `u recente include un classificatore dei pacchetti molto pi `u flessibile, implementa vari schemi per la gestione delle code (FIFO, RED, GRED), ha la possibilit `a di creare topologie complesse, ed `e in grado di riprodurre gli effetti del multipath. Recentemente `e stato anche aggiunto il supporto per caricare in modo dinamico diversi scheduler (con varie opzioni compreso DRR, WF2Q+ e varianti), e un
supporto migliore per l’emulazione del MAC.
Grazie alle ricerche di altri sviluppatori e ricercatori [37, 59] sono inoltre state realizzate altre estensioni, in modo da introdurre alterazioni e perdite sui pacchetti sia programmabili, che guidate da tracce esterne.
L’utilizzo e la diffusione di dummynet `e andato oltre ogni aspettativa iniziale. Oltre all’uso come componente per ricerche individuali, dummynet `e anche un componente fondamentale del testbed di rete Emulab [61] ed `e anche abbastanza popolare nel suo utilizzo come traffic shaper. I recenti lavori, (supporto per l’emulazione MAC, decritto nel Paragrafo 1.2.7, supporto per il caricamento dinamico degli scheduler, Paragrafo 1.2.6; e l’inclusione nei nodi PlanetLab [23] come parte del progetto Onelab2 project [6]) hanno incrementato ulteriormente la sua diffusione.
Di seguito verr `a presentato lo stato dell’arte per quanto riguarda gli strumenti di emulazione, i vari componenti dell’emulatore dummynet, l’estensione a canali tempo varianti e il port su Linux. L’ultima versione di dummynet e il port fino all’ultima versione stabile del kernel di Linux (3.2.7) al momento della scrittura di questo documento, `e disponibile sulla pagina:
http://info.iet.unipi.it/∼luigi/dummynet/.
1.1
Stato dell’arte sugli strumenti di emulazione
Fino alla met `a degli anni 90 e a volte anche fino ai nostri giorni i ricercatori hanno utilizzato delle reti e dei sistemi privati per validare le proprie applicazioni. Per lo studio di argomenti particolari, come schemi per il recupero di errori, a volte basta riuscire a controllare e provocare una perdita di pacchetti sul traffico. Per questo motivo, alcuni sistemi di emulazione causano la perdita dei pacchetti, in base ad alcuni pattern ben precisi, definiti da una traccia fornita dall’utente. Tuttavia, le perdite sono dipendenti dal traffico del sistema, e nell’analisi di un protocollo (come il TCP) che reagisce alle perdite alterando il traffico che produce, una perdita guidata da una traccia pu `o non essere sufficiente. Questo ha portato allo sviluppo di emulatori in grado di emulare il comportamento di link con code finite, larghezza di banda limitata e ritardo di propagazione.
1.1.1
Emulatori di link
Due emulatori di link molto diffusi sono Dummynet [57], che `e disponibile da pi `u di 10 anni come parte di FreeBSD, e NISTNet [24], che `e un componente da aggiungere come modulo su Linux. Oltre alle caratteristiche che permettono di emulare un link, (rate programmabile, ritardi e dimen-sione delle code), sia Dummynet che NISTNet sono in grado di creare pi `u di un link di emulazione e di selezionare i pacchetti soggetti ad emulazione, inoltre entrambi supportano la gestione di perdi-ta dei pacchetti, policy di gestione delle code, e altro. Entrambi sono immediaperdi-tamente disponibili, con poco o nessuno sforzo di installazione, su piattaforme software molto diffuse.
Uno strumenti interessante `e Netpath [14], che si affida al software Click per costruire link di emulazione. Click [42] `e un sistema che permette al programmatore di costruire dei “datapath” per i pacchetti tramite la composizione di vari elementi. Tali “elementi” possono rappresentare diversi oggetti, come interfacce di input/output, classificatori, code, linee di ritardo. Partendo da un grafo definito con gli elementi di Click, Netpath `e in grado di costruire un emulatore con tutte le funzionalit `a richieste, simile a dummynet. L’approccio di Netpath risulta interessante per il fatto che l’emulatore pu `o essere esteso con facilit `a scrivendo semplicemente dei componenti Click che implementano le funzionalit `a desiderate. Inoltre la possibilit `a di escludere il sistema operativo e i suoi device driver rende questa una soluzione interessante dal punto di vista delle prestazioni.
L’importanza di avere un classificatore dei pacchetti risulta evidente se consideriamo le limi-tazioni che hanno i sistemi che non ne sono dotati. Ad esempio EMPOWER [65] non implementa un classificatore dei pacchetti e per la selezione del traffico si affida alle diverse interfacce di rete. Esistono anche dei prodotti commerciali, come LANforge-ICE [3] che implementano sistemi di emulazione completi, forniscono pi `u link di emulazione, permettono di configurare il rate, la latenza e le perdite dei pacchetti. Anche questi strumenti dispongono di caratteristiche che li rendono particolare, come ad esempio LANforge-ICE che permette all’utente di configurare un valore per il jitter, e fornisce un vasta scelta di opzione che permettono di configurare nel dettaglio la corruzione dei pacchetti.
Gli emulatori basati su dispositivi hardware hanno il vantaggio di poter offrire un’accuratezza molto elevata. Inoltre supportano elevati data rate e una emulazione dettagliata delle caratteris-tiche del livello MAC. Un esempio di tali dispositivi `e dato dall’emulatore Ethernet AnueSystem [1] in grado di fornire una emulazione dettagliata di reti Ethernet multiple, includendo anche delle opzioni di registrazione e playback del traffico presente su un segmento di rete.
Simulatori ricchi di feature come Ns-2 [5] e Ns-3 [9], includono anche una modalit `a di emu-lazione per guidare degli esperimenti simulati con del traffico live, o al contrario, sono in grado di generare traffico live a partire da esecuzioni del simulatore.
Infine, alcuni emulatori non usano un modello analitico del sistema da riprodurre, ma si basano su delle tracce di traffico, o sul monitoraggio di sistemi live, per guidare l’emulazione. Due sistemi che appartengono a questa categoria sono ENDE [63] e SatelliteLab [32]: entrambi effettuano il monitor del comportamento di un link di comunicazione da emulare, e utilizzano in real time i risultati delle misure effettuate per riprodurne il sul link emulato.
L’emulazione di un link `e relativamente vicina al traffic shaping, una funzionalit `a disponibile in diversi sistemi e router per gestire le limitazioni (o garanzie, a seconda dei punti di vista) dei link degli utenti. A causa di queste somiglianze, molti sistemi di emulazione sono realizzati a partire da traffic shapers, aggiungendoci le funzionalit `a mancanti. Come esempio netem [39] che implementa ritardi sui link e si affida al pacchetto “tc” di Linux per la classificazione e lo shaping dei pacchetti.
Alcuni ricercatori hanno invece esteso le funzionalit `a di dummynet utilizzando diverse tecniche, ad esempio:
• l’utilizzo di programmi esterni per riconfigurare dinamicamente l’emulatore, come cambiare la larghezza di banda nel tempo. Questo approccio non richiede modifiche al kernel, ma presenta lo svantaggio che il programma esterno non ha nessuna informazione del traffico che attraversa l’emulatore;
• implementare nel kernel delle estensioni all’emulatore come ad esempio aggiungere dei drop dei pacchetti guidati da delle tracce esterne. Questo approccio `e pi `u intrusivo del precedente per quanto riguarda le modifiche da effettuare al sistema, ma ha a disposizione le informazioni sul traffico e gli stati dell’emulatore.
In letteratura ci sono diversi esempi che si basano su questi approcci. Nella prima categoria troviamo il lavoro svolto sul testbed SEDLANE [59], che esegue delle simulazioni Ns-2 per es-trarre il valore di parametri dipendenti dal tempo (ritardi e perdite) di una rete ad-hoc. I risultati di queste simulazioni sono poi utilizzati per cambiare nel tempo la configurazione di una macchina basata su dummynet, facente parte del testbed stesso, dove vengono poi lanciati gli esperimen-ti. Un esempio che utilizza l’approccio del secondo tipo `e invece lo strumento KauNet [37], che estende dummynet per forzare errori e pattern di drop nel kernel, e poi li applica ai pacchetti men-tre attraversano l’emulatore. L’estensione fornisce inolmen-tre uno strumento che permette di gener-are particolari pattern, permettendone una rappresentazione compatta che verr `a poi utilizzata dal kernel.
1.1.2
Emulazione di reti multihop
Una caratteristica desiderata negli strumenti di emulazione `e la possibilit `a di avere pi `u link con-nessi da router o da nodi intermedi. Dummynet implementa queste funzionalit `a supportando la reinserzione multipla del traffico nell’emulatore. Delle regole ad hoc del classificatore si preoccu-peranno di unire o dividere il traffico ad ogni passo, e dirottare i pacchetti ai link opportuni. Con questo approccio, una singola macchina `e in grado di emulare delle reti con pi `u network hop, sebbene sia in grado di supportare carichi di rete leggeri.
Quando le funzioni del router non possono essere modellate dalle regole del classificatore, pu `o invece essere utile ricorrere ad una forma di virtualizzazione, in grado di modellare un’intera rete in un solo sistema. Imunes [64] implementa stack di rete multipli virtuali, utilizzando una sola istanza del sistema operativo FreeBSD. Ogni stack virtuale `e in grado di rappresentare un nodo in una topologia emulata, e connettersi ad altri nodi attraverso una istanza di dummynet. L’estensione naturale di questo concetto `e l’esecuzione di pi `u istanze di emulazione in macchine virtuali, come (Xen, VMWare, VirtualBox, Qemu) che verranno poi connesse insieme in base alle necessit `a dell’utente e alla topologia che intende rappresentare.
Per configurazioni pi `u complesse, come ad esempio il modello di reti di grandi dimensioni e con carichi di rete considerevoli, sarebbe opportuni distribuire l’emulazione su pi `u sistemi fisici. Modelnet [60] supporta la definizione di topologie complesse utilizzando un cluster di router dove `e in esecuzione una versione di dummynet modificata. Il preprocessore Modelnet, utilizzando una descrizione della topologia della rete, mappa i link in pipe dummynet (Paragrafo 1.2.1), locate su router diversi, in modo tale da distribuire il carico, e calcola la sequenza di nodi/pipe che un
pacchetto deve attraversare. Se le pipe sono su diversi router, Modelnet trasferisce solo le infor-mazioni di controllo (non il payload) da un router ad un altro, riducendo l’overhead a run-time e permettendo al sistema di funzionare correttamente.
Il testbed Emulab [61] funziona in un modo simile. Il sistema utilizza una descrizione della topologia per programmare una serie di switch configurabili, connessi a nodi FreeBSD che utiliz-zano dummynet per emulare i vari link. I nodi Planetlab [26] sono stati recentemente estesi [23] integrando l’emulatore dummynet, anche in questo caso con l’obiettivo di rendere programmabile il comportamento dei vari nodi.
1.2
Componenti dell’emulatore
L’emulatore dummynet `e formato da due componenti: il vero e proprio emulatore, che si occupa di modificare l’andamento dei pacchetti di rete, e un classificatore di pacchetti, che si occupa di selezionare il traffico e di dirigerlo alla giusta pipe di emulazione.
In questa sezione verranno descritti i componenti del sistema di emulazione dummynet, l’engine di emulazione, dummynet, e il classificatore di pacchetti ipfw.
Entrambi i componenti sono configurabili da un’unica interfaccia, il programma ipfw. Nella trattazione seguente utilizzeremo il termine Dummynet (con l’iniziale maiuscola) per indicare il sistema di emulazione nel suo complesso, intendendo quindi entrambi i componenti.
Sia il classificatore che l’engine di emulazione con il tempo sono stati oggetto di estensioni e adattamenti. La versione iniziale di dummynet `e descritta in [57]. Il principio sul quale si basa dummynet `e quello di riprodurre i componenti fondamentali di un link di comunicazione, e fornire strumenti di configurazione semplici e flessibili che permettono di intervenire modificando il com-portamento della rete.
1.2.1
Pipes
Alla base del funzionamento dell’emulatore dummynet c’ `e un oggetto chiamato pipe (Figure 1.2). Una pipe `e formata ad una coda, con una dimensione finita e configurabile e un link di comuni-cazione, con una larghezza di banda fissa e un ritardo di propagazione configurabile. Ogni pipe `e identificata univocamente da un numero, ed il numero di pipe configurabile `e limitato dalla memoria disponibile del sistema.
Figura 1.2: La struttura di una pipe in dummynet. I parametri configurabili sono la larghezza di banda, il ritardo di programmazione e la dimensione della coda.
Le pipe vengono configurate dall’utente e hanno la caratteristica di poter variare dinamica-mente il loro comportamento. Questo vuol dire che possono essere riconfigurate dinamicadinamica-mente
anche mentre l’emulatore `e in esecuzione. Il comando utilizzato per configurare una pipe `e molto semplice, si tratta di una linea di comando simile alla seguente:
ipfw pipe 3 config bw 640Kbit/s delay 30ms queue 20
Quello che succede nel sistema a causa dell’esecuzione di questo comando `e che i pacchetti verranno intercettati durante loro percorso attraverso lo stack di rete, e verranno inviati alle rela-tive pipe. Una descrizione dettagliata di funzionamento del meccanismo di classificazione verr `a descritta nel Paragrafo 1.2.2.
Appena un pacchetto viene inviato ad una determinata pipe si controlla se ci sono slot liberi in base alla capacit `a della pipe. Se la pipe non `e piena, il pacchetto viene accodato, mentre la coda viene liberata ad un rate corrispondente alla larghezza di banda configurata per il link associato alla pipe. Una volta fuori dalla coda il pacchetto subisce un ritardo ulteriore, simulando cos`ı il tempo di propagazione del link. Successivamente il pacchetto viene reinserito nuovamente nello stack di rete, da dove riprende il suo percorso verso la destinazione.
Il risultato finale porter `a il pacchetto a subire un ritardo totale di: Ti= (li+ Qi)/B + tD
doveli `e la lunghezza del pacchetto,Qi `e l’occupazione della coda nel momento in cui il pacchetto
viene accodato, infineB etD sono la larghezza di banda e il ritardo di propagazione del mezzo
trasmissivo.
Il traffico di rete viene classificato e inviato alle pipe in base ad alcuni parametri specifici della connessione, in alcuni casi risulta invece utile aggregare in traffico in flussi, e inviare ogni flusso in una specifica pipe. L’emulatore dummynet `e in grado di creare pipe associate a flussi di pacchetti. Questa funzionalit `a `e chiamata “pipe dinamica” e si configura mediante il parametro “mask”, che indica i bit, nella quintupla di un pacchetto (protocollo, indirizzi e porte) che deve essere utilizzata per aggregare il traffico. La maschera viene quindi applicata ai vari pacchetti, e per ogni pattern risultante viene creata una nuova pipe. I pacchetti con lo stesso pattern apparterranno allo stesso flusso e verranno cos`ı inviati alla stessa pipe. Ad esempio, la seguente regola:
ipfw pipe 4 config mask src-ip 0x000000ff bw 1Mbit/s
raggrupper `a i pacchetti aventi lo stesso valore degli ultimi 8 bit dell’indirizzo sorgente di un pac-chetto, e dirotter `a il traffico di ogni flusso ad una nuova istanza della pipe 4. La larghezza di banda di ogni istanza della pipe sar `a di 1 Mbit/s.
Costo di Emulazione
Il costo del passaggio attraverso una pipe `e costante per pacchetto, con qualche ottimizzazione nel caso in cui la pipe abbia un ritardo nullo e nessun limite di banda. La presenza di pipe multiple, sia statiche che dinamiche, `e caratterizzata da un componente logaritmico (O(log N )) che aumenta in base al numero di pipe attive, a causa della coda con priorit `a utilizzata per determinare la pipe da servire. Gli studi effettuati sulle performance di dummynet sono discussi nel Paragrafo 3.1.2.
Figura 1.3: Il flusso dei pacchetti attraverso lo stack di rete viene inviato al classificatore, che invia i pacchetti alle relative pipe. All’uscita della pipe, il traffico viene reinserito nello stack di rete.
1.2.2
Selezione dei pacchetti: il classificatore ipfw
Come accennato nel precedente paragrafo, il traffico di rete viene selezionato in base ad alcune regole e inviato alla rispettiva pipe. Il classificatore di pacchetti utilizzato da dummynet si chiama ipfw e si basa su una lista di regole ordinate (note anche come “ruleset”) che si applicano ai vari pacchetti determinandone il loro destino.
Il comando utilizzato per inserire una regola nel ruleset `e semplice: ipfw addrule-number action options
Ogni volta che arriva un pacchetto, viene invocato il classificatore, che confronta il pacchetto con ogni regola in base all’ordinamento definito nel ruleset. Ogni regola `e formata da una parte rela-tiva alle “azioni” dove possono essere definite zero o pi `u opzioni che permettono di classificare il pacchetto. Nelle “opzioni” `e possibile indicare ad esempio indirizzi IP, porte, protocolli, o addirit-tura metadati, come la direzione di un pacchetto, l’interfaccia di ricezione, etc. . . Le opzioni sono valutate sul singolo pacchetto, e se tutti i controlli danno esito positivo, viene applicata l’azione definita nella seconda parte della regola. Le azioni specificano cosa fare con il pacchetto, e pos-sono decidere se accettarlo e farlo proseguire attraverso lo stack di rete, bloccarlo, inviarlo ad una pipe etc. . .
Il traffico pu `o essere intercettato e passato al classificatore in vari punti dello stack di rete. (Fig-ure 1.3) – in genere il classificatore viene invocato durante il passaggio del layer 2 e/o del layer 3, in entrambe le direzioni. In base alle loro azioni le regole potranno essere inviate a diverse pipe. All’uscita della pipe i pacchetti saranno reinseriti nello stack (o anche nel classificatore stesso, come descritto nel Paragrafo 1.2.3) in un punto successivo a quello dove erano stati intercettati inizialmente. Di seguito viene presentato un esempio di un ruleset e di alcune pipe che emulano due link distinti:
ipfw add 100 pipe 10 out dst-ip xy.it ipfw add 200 pipe 11 in src-ip xy.it
ipfw add 300 pipe 24 out dst-ip 192.168.4.0/24 ipfw add 400 pipe 24 in dst-ip 192.168.4.0/24 ipfw pipe 10 config bw 2000Kbit/s delay 3ms ipfw pipe 11 config bw 256Kbit/s delay 12ms ipfw pipe 24 config bw 10Mbit/s
In questo caso, le regole 100 e 200 passano il traffico destinato all’host xy.it (il nome viene risolto nel momento in cui la regola viene inserita nel ruleset) attraverso due pipe distinte, una per ogni direzione. Questa configurazione rappresenta un link bidirezionale, con caratteristiche diverse in base alla direzione del traffico. Questo esempio `e la tipica situazione di un link di tipo asimmetrico, come ad esempio l’ADSL.
Le regole 300 e 400 invece dirigono alla pipe 24 tutto il traffico della sottorete 192.168.4.0/24, indipendentemente dalla direzione. Utilizzare una singola pipe per del traffico bidirezionale viene spesso utilizzato per emulare un mezzo di trasmissione condiviso, quale ad esempio una rete di tipo Ethernet.
Costi della classificazione
Il classificatore dei pacchetti `e basato su microistruzioni, con un costo computazionale per regola che risulta essere proporzionale al numero e alla complessit `a delle opzioni in essa definite. Il costo di un confronto di indirizzi e porte `e una operazione abbastanza veloce, in quanto tali valori sono immediatamente disponibili nel classificatore. Nel caso in cui occorra controllare lo stato di un socket, o le informazioni associate al routing dei pacchetti, la complessit `a dell’operazione aumenta, in quanto le informazioni richieste sono memorizzate in strutture dati del kernel. La maggiore latenza richiesta per l’accesso alle strutture dati del kernel `e dato dal fatto che queste sono condivise con altri componenti, e possono essere manipolate/interrogate previa acquisizione dell’opportuno lock, che risulta essere una operazione costosa.
Il costo dell’operazione di ricerca nell’intero ruleset cresce linearmente con il numero delle re-gole configurate, ma in ipfw esistono dei meccanismi di ottimizzazione, come le tabelle di lookup e il meccanismo delle stateful entries , che permettono di selezionare il traffico in un tempo costante. Un’accurata misura del tempo impiegato nel processare una regola `e riportato nel Paragrafo 3.1.2.
1.2.3
Reti di tipo multipath e multihop
L’esistenza di un percorso multiplo tra una sorgente e una destinazione in reti cablate pu `o causare riordinamento e/o perdita dei pacchetti. L’emulatore dummynet permette di modellare una rete con percorsi multipli impostando un coefficiente di probabilit `a nelle varie regole. Questo permette di modellare un ritardo addizionale e variabile che possono subire i vari pacchetti a causa del multi-path. Ad esempio le seguenti regole:
ipfw add 1000 prob 0.2 pipe 10 src-port 80 in ipfw add 1010 prob 0.7 pipe 20 src-port 80 in ipfw add 1020 pipe 30 src-port 80 in
permettono di inviare il 20% del traffico HTTP in ingresso alla pipe 10, il 56% (0.7 del restante 80%) alla pipe 20, e la restante parte alla pipe 30. Una volta in grado di redirigere il traffico in modo probabilistico su diverse pipe, la semplice configurazione delle pipe coinvolte nella comu-nicazione permette di emulare un’ampia casistica di situazioni. Ad esempio le pipe, oltre a poter avere una larghezza di banda e un ritardo variabile, possono essere destinazione di traffico di tipo diverso, emulando cos`ı interferenze con la comunicazione principale.
L’emulazione di topologie di rete dove i pacchetti attraversano link multipli, ognuno con carat-teristiche diverse, pu `o essere effettuata intercettando i pacchetti in uscita da una pipe e reindiriz-zandoli su un’altra pipe. Per poter abilitare il reinserimento dei pacchetti nello stack di rete occorre controllare il comportamento di dummynet intervenendo sul valore di alcune variabili messe a dis-posizione dal sistema operativo. Su FreeBSD e Mac OS X si utilizza il meccanismo delle sysctl, su Linux si utilizza l’analogo procfs, mentre su Windows si usano delle entry nel registry. La vari-able che controlla il reinserimento dei pacchetti nel classificatore `enet.inet.ip.fw.one pass. In questo modo i pacchetti che escono da una pipe, anzich `e essere inviati nello stack di rete, ven-gono nuovamente confrontati con le restanti regole del ruleset, dove hanno la possibilit `a di essere nuovamente rediretti ad una nuova pipe.
1.2.4
Perdita dei pacchetti
Durante la comunicazione tra vari dispositivi pu `o succedere che uno o pi `u pacchetti non arrivino a destinazione. In una rete cablata questo pu `o essere sintomo di errori nella configurazione del routing, di overflow nelle varie code dei dispositivi o dalla politica utilizzata per la gestione delle code1
Il meccanismo utilizzato da dummynet per riprodurre la perdita dei pacchetti cerca di emulare le cause stesse delle perdite, principalmente l’accodamento e il routing. Il classificatore dei pac-chetti fornisce invece gli strumenti necessari per combinare insieme il tutto, dando ad esempio la possibilit `a di redirigere ulteriormente il traffico in uscita da una pipe.
Le perdite dovute alla congestione della rete possono essere riprodotte immettendo del traffico aggiuntivo nelle pipe. Questo traffico pu `o essere generato dalla stessa applicazione che genera i pacchetti dati, o da altre sorgenti che simulano dispositivi in competizione sullo stesso mezzo trasmissivo. Le perdite dovute ad altre cause possono essere riprodotte con una percentuale probabilistica che influenza il verdetto del classificatore, come descritto nella sezione 1.2.3.
Ad esempio per emulare un link con una perdita di pacchetti distribuita in modo uniforme si pu `o usare il comando:
ipfw add 400 prob 0.05 deny src-ip 10.0.0.0/8
Inoltre la precedente istruzione pu `o anche accettare diversi valori per la probabilit `a in base al valore degli indirizzi, delle porte, della lunghezza del pacchetto o di altri attributi. La struttura del codice di ipfw pu `o anche essere modificata con facilit `a in modo da aggiungere nuove opzioni o implementare diversi pattern per la perdita dei pacchetti, cos`ı come `e stato realizzato in passato da altri ricercatori [37, 51].
1Una politica di gestione delle code che causa la perdita di pacchetti `e RED (Random early detection). L’algoritmo che
implementa tale politica scarta i pacchetti in ingresso alle code con una probabilit `a che dipende dall’occupazione della coda stessa. In questo modo la perdita dei pacchetti viene distribuita equamente sull’intera coda, anzich `e coinvolgere solo i pacchetti in eccesso.
In reti di tipo wireless, ai fenomeni gi `a descritti, si sommano le perdite dovute ad una bassa qualit `a del canale trasmissivo, alla presenza di eccessivo rumore del canale o ad interferenze dovute ad altri dispositivi trasmittenti.
1.2.5
Gestione delle code
Dummynet include varie politiche di gestione delle code e un algoritmo per lo scheduling dei pacchetti, il tutto tramite parametri configurabili dall’utente. La gestione di default delle code `e FIFO, con una dimensione configurabile in bytes o in slot. Dummynet rende disponibili anche politiche di gestione delle code di tipo RED e GRED, i cui parametri restano sempre configuraibili dell’utente.
1.2.6
Scheduling dei pacchetti
Lo scheduling dei pacchetti `e implementato utilizzando degli oggetti chiamati code, utilizzate per creare uno o pi `u code che memorizzano i pacchetti appartenenti a diversi flussi di rete, e un mec-canismo per leggere e configurare degli algoritmi specifici di scheduling a runtime. La connessione tra code, pipe e scheduler `e illustrata in Figura 1.4.
Figura 1.4: La connessione tra code, scheduler e le corrispondenti pipe.
Una “coda” pu `o essere creata o configurata con il comando ipfw queue N config sched X weight Y mask ...
che permette anche di definire lo scheduler (pipe) a cui la coda `e attaccata, impostare i parametri rilevanti per l’algoritmo di scheduling (come il peso e le priorit `a) e definire come i pacchetti devono essere raggruppati in flussi. Il meccanismo di aggregazione `e simile a quello utilizzato per le pipe dinamiche, discusse nel Paragrafo 1.2.1: una maschera viene applicata alla tupla del pacchetto, e una nuova istanza di coda viene creata per ogni pattern positivo risultate dal confronto.
La seguente configurazione permette di definire una pipe con una larghezza di banda di 4 Mbit/s, per una coda con peso 20 e code dinamiche con un peso di 10 unit `a ognuna.
ipfw pipe 5 config bw 4Mbit/s
ipfw sched 5 config type wf2q+ # sends to pipe 5 ipfw queue 10 config weight 20 sched 5
ipfw queue 8 config weight 10 sched 5 mask src-ip 0xffffffff ipfw add 1000 queue 10 out proto udp
ipfw add 1010 queue 8 out proto tcp src-ip 10.8.5.0/24
Il parametro mask src-ip 0xffffffff indica quale istanza dell’oggetto queue creare per ogni sorgente IP. La configurazione del tipo di scheduler e del link di output `e fatta utilizzando il coman-do:
ipfw sched/pipe X config ...
Al momento gli scheduler supportati sono FIFO, DRR, WF2Q+ e QFQ [25], ma l’API semplice
ed intuitiva richiede solo poche centinaia di linee di codice per implementare un nuovo scheduler. Grazie alla sua modularit `a, lo scheduler ha inoltre la possibilit `a di essere testato in userspace, semplificando la fase di sviluppo e agevolando il test dello scheduler stesso.
Costi relativi allo scheduling
Il costo di pipe multiple nella stessa pipe dipende dallo specifico algoritmo di scheduling utilizzato. La complessit `a degli algoritmi di scheduling `e stata ampiamente trattata in letteratura, si parte da O(1)per FIFO, DRR e QFQ, aO(log N )per WF2Q+. Il costo di questi algoritmi `e riportato in [25],
ed `e compreso tra i 100 e i 1000 ns per una configurazione standard, anche su una macchina di tipo desktop.
1.2.7
Emulazione del MAC layer
Dummynet non implementa una emulazione dettagliata del livello MAC, infatti l’emulazione dei frame (gaps, preambolo, checksums), scheduling dei pacchetti sul canale, o ritrasmissioni a livello di link non sono presenti in dummynet. Emulare in modo dettagliato le cause che sono alla base dei ritardi, delle perdite o dei riordini a livello MAC `e un’attivit `a abbastanza complessa e costosa in termini di risorse. Questo `e vero in particolare per i mezzi condivisi, dove il comportamento di un canale di comunicazione `e fortemente dipendente dall’interazione tra il MAC layer e il compor-tamento specifico di tutti i dispositivi di comunicazione che condividono il mezzo. Infatti, senza modellare anche tutti gli attori addizionali coinvolti in questa comunicazione, porterebbe ad avere comunque risultati approssimati, emulazioni parziali e di conseguenza non corrette.
La diffusione di reti non cablate ha portato all’aumento della richiesta di poter emulare link di tipo wireless. In questo tipo di link, a differenza di quelli cablati, i pacchetti subiranno un ritardo di tipo variabile, dovuto alla variazione delle condizioni del canale nel tempo. Per emulare questo tipo di canali, il modello di dummynet `e stato arricchito, supportando la definizione di ritardi variabili, definiti dall’utente tramite una funzione di distribuzione, come sar `a meglio specificato nel Paragrafo 1.3.
Nell’introduzione di questa nuova feature in dummynet si `e cercato di non aumentare la com-plessit `a dell’emulatore, mantenendola entro limiti accettabili. Questo `e uno dei motivi per cui si `e scelto di riprodurre gli effetti MAC in modo probabilistico e definire un parametro addizionale per emulare interferenze date dalle altre stazioni.
Figura 1.5: Andamento qualitativo del tempo addizionale utilizzato per la trasmissione del pacchetto.
Nel nostro modello, la trasmissione di un pacchetto, terr `a il canale occupato per il tempo di trasmissione l/B, pi `u un tempo addizionale, chiamato “extra airtime”, dato dalla somma degli intervalli in cui il canale `e occupato, dai tempi per la contesa del mezzo, dai backoffs. . .2 Per
poter implementare l’emulazione in questo modo occorre quindi permettere all’utente di specificare una serie di ritardi, definiti mediante la distribuzione cumulativa (CDF) del tempo di attesa, “extra airtime”, che verr `a poi utilizzata nel calcolo del tempo di occupazione del canale.
L’emulazione riprodotta da dummynet sar `a tanto pi `u accurata quanto pi `u realistica sar `a la funzione di distribuzione definita dalla curva.
Nella definizione della curva, in prima approssimazione si pu `o a modellare un canale senza contesa, con ritardi di tipo deterministico. In questo caso, la CDF sar `a del tipo rappresentato in Figura 1.5 sulla sinistra: ad una probabilit `a di trasmissione con successo al al primo tentativo, si avr `a un overhead di ritardo fisso. Le ritrasmissioni a livello di link, se presenti, causeranno un ritardo aggiuntivo, dovuto ai timeout degli ACK a livello di link. L’effetto sulla curva di questi ritardi sar `a un andamento a gradino. La ritrasmissione a livello di link avviene per un numero limitato di volte, definito dallo standard, dopo cui il pacchetto non viene pi˘‘ ritrasmesso e viene dichiarato perso. La probabilit `a associata a questo fenomeno `e configurabile dall’utente mediante un parametro di loss.
Nel caso di mezzo non conteso, la curva pu `o anche essere ricavata, almeno in prima approssi-mazione, da uno studio analitico delle specifiche del protocollo MAC. Ma anche in questo caso, per poter riprodurre fedelmente il comportamento del canale, non si pu `o seguire fedelmente lo standard, basta infatti pensare a tutti i casi in cui l’implementazione nel firmware dei dispositivi non segue lo standard, o il caso in cui alcuni parametri sono configurati in modo da avere un comportamento pi `u aggressivo rispetto ad altri.
In caso di mezzo conteso, il ritardo introdotto diviene variabile, dovuto al fatto che a volte il canale non `e utilizzabile perch ´e in stato di “busy”3o alla presenza di collisioni. I ritardi dovuti al
mezzo occupato, e le ritrasmissioni con un back-off piccolo, probabilmente avranno delle regioni
2nel modello andranno considerati anche i preamboli, il framing, gli acknoledge e le ritrasmissioni a livello di link. 3Un canale pu `o essere in stato busy quando altre stazioni sono in trasmissione
sovrapposte nel grafico dei ritardi, quindi la curva, (determinata sperimentalmente o in base a considerazioni empiriche) dovrebbe assomigliare a quella rappresentata in Figura 1.5 sulla destra. Ulteriori studi sul come determinare questa curva, e un esempio del suo andamento con dispositivi e in situazioni reali `e riportato in Figura 1.6.
I parametri associati a questa curva di distribuzione empirica sono memorizzati in un file, e passati a dummynet con l’opzioneprofile. La pipe sar `a quindi configurata con:
ipfw pipe 3 config profile profile foo
Il file include in nome del profilo, il rate, un livello di perdita, e il numero e la posizione degli angoli che definiscono la curva, ad esempio:
name profile foo bandwidth 2Mbit/s loss-level 0.99 samples 5
prob delay # delay in us 0.2 100
0.4 130 0.5 130 0.8 1500 0.98 2000
1.3
Emulazione di canali tempo varianti
Noti i parametri caratteristici di un link di comunicazione, tipo la larghezza di banda, il ritardo introdotto dal canale, etc. . . `e facile riprodurne il suo comportamento in un emulatore. Le carat-teristiche del link sopra descritto non sono per `o rappresentative di tutti i link di comunicazione, in particolare i link di tipo wireless che si sono diffusi maggiormente negli ultimi dieci anni.
La differenza fondamentale tra l’emulazione di un link cablato e uno wireless `e la variabilit `a e la non controllabilit `a della condizione del canale. Un link cablato ha un comportamento facilmente riproducibile e soprattutto invariante nel tempo. In un canale wireless la trasmissione `e influenzata da numerosi fattori, come ad esempio il numero e il tipo di dispositivi connessi, le condizioni dell’ambiente esterno, o la presenza di interferenze di varia natura.
L’emulatore dummynet, tramite la possibilit `a di modificare il verdetto di una regola in base dato da una regola in modo probabilistico, ha la possibilit `a di poter introdurre una certa variabilit `a agli esperimenti, ma questo meccanismo non `e sufficiente per modellare un canale wireless.
L’emulazione dettagliata di un modello di canale wireless, `e sicuramente complessa da realiz-zare. Piuttosto che riprodurre tutta la complessit `a del modello e tutti i dettagli del protocollo MAC, in dummynet sono state introdotte due nuove funzionalit `a, i profili di ritardo e i link tempo varianti. Nel capitolo che segue verr `a presentata una estensione di dummynet all’emulazione di canali tempo varianti. In particolare verr `a descritta l’architettura dell’estensione realizzata e come sono stati affrontati i vari componenti di un sistema di trasmissione tempo variante.
1.3.1
Realizzazione dell’estensione in dummynet
Il funzionamento dell’emulazione su dummynet si basa sulle pipe, (Figure 1.3) dove un canale di comunicazione cablato, di tipo point-to-point, viene modellato configurando opportunamente le pipe come descritto nel Paragrafo 1.2.1. Emulare un canale wireless richiede la possibilit `a di poter definire l’effetto di altri fenomeni, come ad esempio quello del protocollo MAC, gli errori introdotti dal rumore, la condivisione del link con le altre stazioni, l’interferenza esterna, e le variazioni a cui
`e soggetto il canale nel tempo.
Ci sono emulatori che implementano tali fenomeni, come ad esempio [21] e [9], dove le carat-teristiche del canale vengono definite in dettaglio. In questo caso l’emulazione di un canale con delle caratteristiche particolari richieder `a la definizione di un modello molto preciso, richiedendo notevoli risorse nella fase di modellazione del canale. Una emulazione cos´ı dettagliata comporta inoltre un costo computazionale elevato che, se introdotto in PlanetLab, dove le applicazioni in esecuzione contendono risorse macchina e di rete, renderebbe ben presto il nodo inutilizzabile. Per questi motivi la realizzazione dell’estensione wireless `e stata implementata con un approccio diverso da quello di una emulazione completa e dettagliata. La strategia di emulazione adottata ha invece introdotto dei meccanismi atti ad emulare gli effetti introdotti dal mezzo fisico, cio `e:
• tempi di trasmissione addizionali, introdotti dal protocollo MAC. Per ogni pacchetto trasmes-so, il canale viene considerato occupato per un tempo addizionale, in modo da tenere in con-to dei tempi di backoff, dei preamboli, del framing a livello MAC, e degli acknowledgement a livello di link;
• errori introdotti dal rumore. Come descritto nel Paragrafo 1.3.3, il rumore sul canale introduce una certa probabilit `a di errore. Questa probabilit `a dipende dal livello di rumore, dal tipo di modulazione utilizzata, dal data rate e dalla dimensione del pacchetto;
• interferenze dovute alla presenza di altre stazioni. La presenza di fonti trasmissive addizion-ali `e causa di due fenomeni: errori di trasmissione dovuti alle collisioni e una riduzione nella disponibilit `a del canale, dovuta al fatto che una parte del tempo sar `a dedicata alle trasmissioni delle altre stazioni presenti.
I profili di ritardo supportano la definizione dell’overhead introdotto dal livello MAC, (ritardi dovuti alla contesa del mezzo, framing e ritrasmissioni) attraverso dei profili empirici. Il tempo di trasmissione totale sar `a quindi comprensivo anche del tempo introdotto dai profili di ritardo, in base alla distribuzione specificata dall’utente, come ad esempio la CDF definita in Figura 1.6. Questa soluzione permette di emulare sia i tempi di trasmissione di un canale, sia quelli speri-mentati nella realt `a. Il modo in cui i profili vengono utilizzati per emulare il canale `e discusso nel Paragrafo 1.3.1.
1.3.2
MAC overheads
L’overhead introdotto dal livello MAC viene modellato utilizzando i profili di ritardo: per ogni pac-chetto trasmesso, il tempo di trasmissione viene incrementato di una quantit `a di tempo scelta ca-sualmente in base ad una funzione di distribuzione (CDF). La CDF viene definita per mezzo di una funzione empirica, come ad esempio quelle rappresentate in Figura 1.6. Questo tempo aggiuntivo comprende l’overhead a cui un pacchetto `e sottoposto a causa della trasmissione wireless, ed `e formato da vari componenti: backoff, preamboli, framing a livello MAC, e acknowledgement a
0
0.5
1
200
400
600
800
1000
CDF
Delay (us)
54Mbit/s
11Mbit/s
5.5Mbit/s
2Mbit/s
1Mbit/s
Figura 1.6: La curva di ritardo (delay profile) descrive la distribuzione degli overhead a libello MAC. L’andamento a gradini `e dato dall’effetto dei backoff random (i tempi differiscono tra 802.11g e 802.11b), mentre la parte restante deriva dal framing e ack a livello MAC.
livello di link. Questi valori possono essere, in linea di principio, calcolati in base a quanto definito dallo standard di comunicazione. Per avere un modello pi `u fedele alla realt `a baster `a estrarre i valori della curva dei ritardi da un sistema reale, procedura necessaria quando si ha a che fare con dispositivi hardware che implementano gli standard in maniera diversa [17] e [31].
A titolo di esempio, una trasmissione tipica su 802.11b/g coinvolge un ritardo addizionale al pacchetto dato da una quantit `a fissa di tempo (framing a livello MAC e acknowledgement), e un backoff variabile, come rappresentato in Figura 1.6.
1.3.3
Rumore
La presenza di rumore sul canale pu `o causare un errore nella ricezione dei simboli4che il ricevitore
deve decodificare. La presenza di eccessivo rumore sul canale porter `a ad un errori da parte del ricevitore nella traduzione del simbolo, che si tradurr `a in un errore nella ricezione di un pacchetto e, infine in una perdita e una ritrasmissione a livello di link. La relazione tra il rumore5e il Packet Error Rate (PER) dipende da vari fattori, tra cui la modulazione, la larghezza in banda del canale e il data rate.
Il modello d’errore utilizzato nell’implementazione del componente di emulazione wireless si basa sulle stesse formule utilizzate dal simulatore Ns-3, per i modelli DSSS [53] e NIST [52]. Per le modulazioni 802.11g il modello NIST `e in grado di approssimare meglio il canale reale, rispetto al modello YANS [44] utilizzato in precedenza.
Il modello di canale per la modulazione 802.11b `e basato sulle formule della teoria delle co-municazioni, descritte in [55] e validate tramite confronto con un canale privo di errori da [53, Sec. 1.2.3].
4In base alla modulazione utilizzata, un simbolo pu `o codificare uno o pi `u bit. 5pi `u correttamente tra il rumore e il rapporto segnale/rumore, (SNR)
Ad esempio, l’equazione per la modulazione DBPSK a 1 Mbps, e l’approssimazione dello stu-dio [36] per la modulazione a 2 Mbps DQPSK sono date dalle seguenti formule (al rate 1 symbol = 1 bit): BER1M= 1 2e −N0Eb BER2M = √ 2 + 1 p 8π√2 1 qE b N0 e−(2−√2)Eb N0
dove Eb rappresenta l’energia per bit e N0 `e il livello di rumore al ricevitore. Conoscendo il
rappor-to segnale/rumore, la larghezza di banda del canale B e il data rate R, possiamo facilmente calcolare Eb/N0=SNRBR. Le risultati curve per il BER ai vari rate sono rappresentate in Figure 1.7.
1e-12
1e-10
1e-08
1e-06
0.0001
0.01
1
-5
0
5
10
BER
sinr (dB)
11Mbit/s
5.5Mbit/s
2Mbit/s
1Mbit/s
Figura 1.7: La relazione tra SNR e BER per diversi rate.
Per le modulazioni che utilizzano un simbolo per bit, la relazione tra il BER, la dimensione del pacchetto in bit (L), e il Packet Error rate (PER), `e:
P ER = 1 − (1 − BER)L
Per le altre modulazione occorre sostituire il BER con il Symbol error rate, ed L con la dimensione in simboli. Ad esempio, in Figura 1.8 `e rappresentato il Packet Error Rate per diversi valori di BER e L.
Data la complessit `a delle formule, `e evidente che la loro applicazione a tempo di esecuzione sarebbe impraticabile, e comporterebbe un eccessivo spreco di tempo di calcolo. Per evitare ci `o i valori del Packet Error Rate sono stati calcolati off-line e inseriti in una tabella per alcuni valori pi `u significativi delle dimensioni del pacchetto e del rapporto segnale rumore. In questo modo durante l’esecuzione del programma sar `a sufficiente effettuare un semplice lookup nella tabella per ricavare, dato il SNR e la dimensione del pacchetto la rispettiva probabilit `a di errore in trasmissione. In caso di errore sulla trasmissione, un pacchetto pu `o risultare perso, pertanto il canale non deve essere disponibile per la trasmissione successiva. Questo viene realizzato emulando il tempo necessario per la ritrasmissione a livello di link.
0
0.2
0.4
0.6
0.8
1
0
2000
4000
6000
8000
10000
12000
(1-Perr)
packet size (bits)
BER 4e-5
BER 2e-4
BER 5e-4
BER 2e-3
BER 2e-6
Figura 1.8: Probabilit `a di trasmissione per diversi valori di Bit Error Rate.
1.3.4
Competizione per l’accesso al mezzo
La presenza di stazioni in competizione per l’accesso al mezzo, viene modellata con due parametri. Il primo, netload, rappresenta la frazione di tempo in cui il mezzo non `e disponibile a causa del traffico generato da altre stazioni, ad esclusione delle collisioni che verranno gestite separatamente. Un esempio di questo tipo di interferenza sono i messaggi di “Beacon” inviati dagli Access Point per segnalare la loro presenza, che occupano il canale consumando circa l’ 1% del tempo di trasmissione. In prima approssimazione, tutti i tempi di trasmissione dei pacchetti vengono moltiplicati per 1
1−netload in modo tale da ridurre il tempo disponibile
per la trasmissione. Il secondo parametro, collisions, indica la probabilit `a di collisione di un pacchetto. I due parametri sono in relazione tra loro, e tale relazione varia in base al pattern di traffico presente sul canale ( [16, 46]) quindi per una corretta emulazione occorre distinguere i parametri usati per modellare i due effetti.
Il parametro collision viene utilizzato per forzare casualmente un errore in trasmissione, effetto che si va a sommare a quello causato dal rumore. Gli errori introdotti dalle collisioni sono gestiti allo stesso modo degli errori introdotti dal rumore, ossia tenendo in conto il tempo di trasmissione del pacchetto pi `u il tempo per una ritrasmissione a livello di link.
1.3.5
Link tempo varianti
I link di tipo tempo variante modellano la variabilit `a del canale di trasmissione nel tempo, effetto dovuto ad esempio dalla mobilit `a del dispositivo connesso.
Quando vengono utilizzati i link tempo varianti, il sistema cambia dinamicamente la configurazione delle pipe (larghezza di banda, profilo dei ritardi e loss rate) in base ad un grafo di transizione specificato dall’utente. Ad ogni nodo presente nel grafo, `e associata una configurazione specifica dell’emulatore, come rappre-sentato in Figura 1.9. Il sistema parte da una configurazione iniziale definita dall’utente, e la mantiene per un tempo casuale, in base ad una curva di tempo empirica associata al nodo. Le transizioni da un nodo al
Figura 1.9: Un esempio delle informazioni utilizzate per implementare i link tempo varianti (Para-grafo 1.3). Il link presenta lo stesso stato per intervalli di tempo in base alla distribuzione data. Trascorso questo tempo il sistema evolve in uno stato successivo con la probabilit `a specificata sugli archi.
successivo avvengono in base alla probabilit `a definita sugli archi che connettono i vari nodi. Dal momen-to che una transizione richiede comunque un tempo di configurazione lungo, se confrontamomen-to con il tempo di trasmissione dei pacchetti, le riconfigurazioni dell’emulatore sono controllate da un processo user-space, senza nessuna modifica al kernel.
Un’applicazione per questo tipo di emulazione `e data da un dispositivo mobile connesso in rete. Durante il suo percorso, in particolare se su una lunga distanza, sar `a sicuramente soggetto a diverse tecnologie di connessione alla rete, come ad esempio HSUPA, 3G or GPRS, alternate a periodi di assenza di connettivit `a. Per riprodurne il comportamento su un emulatore occorrer `a costruire un profilo per ogni situazione e una policy che gestisca le transizioni da un profilo all’altro, utilizzando un modello di Markov.
1.4
Il port su sistemi Linux
La piattaforma di PlanetLab `e formata da nodi basati su Linux, quindi come parte del lavoro svolto per PlanetLab `e stato necessario effettuare il port di dummynet sul sistema operativo Linux. Il port dell’interfaccia utente,/sbin/ipfw, `e stato molto semplice e immediato, in quando essendo un programma user space ha richiesto un semplice adattamento delle funzioni di libreria tra Linux e FreeBSD. Il port relativo alla parte
kernel space ha invece richiesto pi `di un adattamento, a causa della mancanza di standard tra interfacce (API), header, supporto offerto dal kernel, e strutture dati tra piattaforme diverse.
L’approccio seguito nel portare il codice sul nuovo sistema ha avuto tra gli obiettivi principali quello di mantenere il codice originario, per quanto possibile, non modificato. Questo modo di operare ha due notevoli vantaggi: fa emergere le assunzioni specifiche legate alla piattaforma (dando la possibilit `a di correggerle) e rende semplici i successivi aggiornamenti del programma. Inoltre avere lo stesso identico codice come rifer-imento riduce notevolmente la possibilit `a di introdurre nuovi bug. Il risultato di questo lavoro `e una serie di header e funzioni che mappano le strutture dati e le API del kernel di FreeBSD nell’equivalente Linux. In par-ticolare per quanto riguarda i pacchetti dati, glimbufs6sono stati mappati inskbufs7mentre l’intercettazione dei pacchetti `e stata mappata dal meccanismo (pfilin FreeBSD) a chiamatenetfilterin Linux.
Il lavoro svolto su Linux ha inoltre fornito un’ottima base di partenza per il porting del sistema di emu-lazione su Windows. Inoltre la suddivisione delle funzioni relative all’implementazione dell’emulatore dalle le funzioni di interfaccia con il kernel e il sistema di rete ha agevolato notevolmente il lavoro, permettendo di individuare con rapidit `a i punti del codice sui quali intervenire. L’emulatore `e al momento disponibile sui sistemi operativi pi `u diffusi, incluso Windows e il sistema per dispositivi embedded OpenWRT [11].
1.4.1
Uno sguardo generale alle modifiche effettuate
Il processo di adattamento di un software da un sistema ad un altro `e formato da passi semplici e meccanici, e da altri altri architetturali, di una certa complessit `a. I passi effettuati durante il port di dummynet a Linux sono stati:
• Adattamento degli header. Questo lavoro ha coinvolto la creazione di alcuni header “di sistema”, con l’obiettivo di fornire gli header di FreeBSD mancanti su Linux. In questa fase sono anche stati risolti i problemi derivanti da conflitti sugli header e su macro di sistema.
• Ridefinizione di macro. Per alcune funzioni particolari su FreeBSD sono state utilizzate delle macro. Questo approccio ci ha permesso di adattare il codice semplicemente ridefinendo la macro stessa, come nel caso delle macro legate ai lock o al logger.8
• Rimozione del codice contenente operazioni esplicite dipendenti dalla piattaforma. Un esempio classi-co di questo tipo di assunzione sono le funzioni relative alla rete, in particlassi-colare i campi indirizzo/porta dei pacchetti di rete. Infatti un approccio che voglia garantire la portabilit `a del codice dovrebbe pre-scindere da come sono rappresentati tali valori nel pacchetto ed utilizzare sempre le apposite funzioni di conversione tra network e host order. Anche chiamate esplicite a routine di divisione su 64 bit, non dovrebbero essere effettuate esplicitamente, ma tramite opportune funzioni, in modo da poter implementare agevolmente le stesse funzionalit `a su diverse piattaforme.
• Ricreare le API del kernel di FreeBSD utilizzando le relative funzioni corrispondenti in Linux.
La parte che ha richiesto pi `u impegno `e stata quella riguardante la progettazione dell’infrastruttura di adattamento tra i due sistemi operativi, in particolare i) capire dove aggiungere le definizioni e gli header mancanti, ii) decidere dove mantenere il codice non modificato e dove invece intervenire modificato il sor-gente originale, e iii) identificare un buon modo per agganciare il sottosistema di rete del kernel utilizzato da dummynet.
1.4.2
Agganciarsi allo stack di rete di Linux
Il primo problema da affrontare quando occorre relazionarsi con un altro sistema operativo `e cercare di capire come si pu `o accedere al traffico di rete. Infatti il classificatore e l’emulatore devono essere in grado
6la struttura dati utilizzata su FreeBSD per rappresentare un pacchetto di rete. 7la struttura dati utilizzata su Linux per rappresentare un pacchetto di rete. 8Un esempio sono le macroDEFINE SPINLOCK, LOG SECURITYeLOG NOTICE.
di intercettare, manipolare e rilasciare i pacchetti diretti allo stack di rete. Un altro requisito `e riuscire ad intercettare sia il traffico in ingresso alla macchina che quello in uscita (upstream e downstream) e riuscire a reinserire nuovamente i pacchetti nello stack dopo un certo ritardo.
Figura 1.10: L’interazione tra gli hook netfilter, il classificatore (ipfw chk() e l’emulatore (dummynet io()) code.
La maggior parte dei sistemi operativi supporta l’inserzione di funzioni generiche di filtro dei pacchetti sul percorso del pacchetto. Questo meccanismo `e chiamato pfil su FreeBSD, netfilter su Linux, e miniport drivers su Windows. Tutti questi sistemi permettono di manipolare i pacchetti senza nessuna altra modifica al resto del kernel del sistema operativo.
Per il port su Linux `e stato utilizzato il sistema netfilter, in grado di intercettare i pacchetti dal loro percorso nello stack di rete e inserirli in una coda. Da qui i pacchetti verranno passati ad una funzione specificata dall’u-tente queue handler che potr `a effettuare qualunque operazione sui pacchetti prima di reinserirli nuovamente nello stack di rete (o buttarli via) con la chiamata anf reinject().
Nel nostro sistema, la funzione handler, non fa altro che chiamare il classificatore ipfw, che processa il pacchetto confrontandolo con il ruleset e lo rilascia al sistema o lo passa all’emulatore, che lo reinserir `a nello stack tramite nf reinject()dopo un opportuno ritardo. In Figura 1.10 `e rappresentato il funzionamento dell’intero meccanismo nel caso di un pacchetto in ingresso dalla rete.
Nella versione attuale del port su Linux sono state utilizzate due funzioni di netfilter,9 e una funzione per la gestione della coda dei pacchetti. La funzione di netfilter seleziona tutti i pacchetti e li invia in una
coda apposita, sulla quale verr `a invocato il classificatore dei pacchetti e, se previsto, l’emulatore. Dopo aver applicato l’azione definita dal classificatore e un eventuale ritardo introdotto da dummynet, i pacchetti verranno reinseriti nello stack di rete.
1.4.3
Rappresentazione del pacchetto nel kernel
La rappresentazione di un pacchetto varia tra i vari sistemi operativi. Sebbene essa possa essere molto diversa, l’approccio seguito nella gestione dei pacchetti di rete risulta essere abbastanza simile. In genere la parte dati di un pacchetto `e memorizzata in uno o pi `u buffer collegati, e da un descrittore esterno, utilizzato per memorizzare tutte le informazioni accessorie ai dati (metadati) come la lunghezza del pacchetto, il puntatore ai dati, la direzione, le interfacce e i flag.
In FreeBSD e in altri sistemi da esso derivati10i metadati sono memorizzati in strutture chiamatembuf. Anche l’approccio seguito su Linux `e simile, abbiamo un descrittore che contiene le informazioni accessorie e un puntatore ai dati. Questa struttura `e chiamatask buff.
Figura 1.11: The mapping betweensk buffs andmbufs.
Su Linux il nostro handler ricever `a quindi una serie di pacchetti da processare, in strutture dati chiamate sk buff. Per permettere al core di dummynet, che utilizzambuf, di interagire con i pacchetti di Linux `e stato creato un fintombufche viene inizializzato con i campi rilevanti del pacchetto.
In Figura 1.11 sono rappresentate le strutture dati per i pacchetti su Linux e la nuova rappresentazione usata dal port mediante un finto mbuf. La ricostruzione di un finto mbufevita di dover modificare tutto il codice dell’emulatore che accede ad esso, in quanto il codice di dummynet non si accorge nemmeno della sostituzione e accede ai valori in esso contenuti nel solito modo. Prima di restituire il pacchetto allo stack di rete liberiamo il fintombufe reimmettiamo il pacchetto nello stack senza ulteriori modifiche.
1.4.4
Altri servizi di sistema
Oltre alle funzioni strettamente legate alla rete occorre riprodurre anche altri servizi di cui l’emulatore ha bisogno, come ad esempio funzioni per il timing, la gestione dei lock . . . Per riprodurre questi servizi si uti-lizzano delle funzioni “wrapper” che implementano le corrispondenti funzioni di Linux, cercando di esportare una API compatibile con FreeBSD.
