7
1. Wireless Mesh Networks
In questo primo capitolo viene fatta una panoramica sulle Wireless Mesh Network. In particolare vengono analizzate le caratteristiche principali, le architetture possibili e gli scenari applicativi. Inoltre sono stati approfonditi i problemi di progetto e le scelte tecnologiche, dal routing alle tecniche multi-channel.
1.1 Aspetti generali
Quando si parla di WMN si fa riferimento in generale ad una soluzione di connettività piuttosto che ad un particolare tipo di tecnologia. Rispetto alle reti ad-hoc multi-hop, già ampiamente diffuse, le WMN
8
differiscono da queste per la presenza di un’infrastruttura di rete più affidabile, rappresentata tipicamente da nodi fissi connessi tra loro per costituire un sistema di distribuzione wireless. Ogni nodo della rete, in questo scenario, può essere allo stesso tempo host e router, nel senso che funge da ricevitore, trasmettitore e ripetitore. Questo tipo di architettura consente di ottenere una rete molto flessibile e robusta, visto che ogni nodo è connesso a molti altri nodi.
Reti wireless mesh possono in teoria essere realizzate con ogni tecnologia wireless esistente, ed anche inglobando in un’unica architettura più tecnologie eterogenee. Diventa pertanto naturale cercare di sviluppare soluzioni mesh su tecnologie wireless già esistenti e diffuse dal punto di vista commerciale, come ad esempio 802.11 e 802.16. Tuttavia i requisiti e le caratteristiche di un’architettura mesh sono ben diversi dai presupposti su cui sono state sviluppate le tecnologie radio ed i protocolli MAC esistenti, quindi è inevitabile che cercare di adattare una tecnologia esistente in una soluzione mesh porta con se dei limiti. Pertanto tali meccanismi devono essere migliorati o riprogettati appositamente per sfruttare tutte le potenzialità della tecnologia mesh.
Ad esempio nello sviluppo delle tecnologie di reti di sensori, l’aspetto della connettività multi-hop è essenziale ed un presupposto alla base del progetto; lo sviluppo protocollare integra in se tutte le caratteristiche della connettività mesh, dall’inoltro multi-hop, all’ottimizzazione della potenza, realizzando una soluzione tecnologica dedicata per un determinato scenario applicativo. Purtroppo, proprio perché tali soluzioni sono state sviluppate come parte integrante di tale tecnologia, non è pensabile di applicare
9
semplicemente ciò che è stato implementato nelle reti di sensori alle reti di accesso broadband basate su tecnologie come WiFi e WiMax.
Le Wireless Mesh Network sono generalmente considerate come un tipo di rete ad-hoc a causa della mancanza di un’infrastruttura fissa, che esiste nelle reti cellulari o WiFi sotto forma di base station o Access Point. Sebbene le tecniche di comunicazione ad-hoc siano in generale un requisito delle reti WMN, le caratteristiche aggiuntive di questo tipo di soluzione richiedono algoritmi e accorgimenti progettuali molto più sofisticati. Piuttosto che diventare un tipo di tecnologia ad-hoc, le WMN hanno l’obiettivo di diversificare le capacità di tali reti, conseguentemente è più corretto considerare le reti ad-hoc come un sottoinsieme delle WMN.
1.1.1 Architettura di rete
Tipicamente una WMN consiste di due tipi di nodi: mesh router e mesh client. Il ruolo principale dei mesh router è di connettere un nodo al resto della rete mesh e di fornire l’accesso broadband wireless a client convenzionali. Per una maggiore flessibilità possono avere più interfacce radio, della stessa tecnologia di accesso o di tecnologie differenti. Un mesh router, inoltre, può incorporare funzionalità di gateway o bridge per comunicare con altri tipi di reti esterne alla mesh, a livello tre o a livello due.
Anche i mesh client possono operare come mesh router, tuttavia tipicamente utilizzano piattaforme hardware e software più semplici rispetto ai mesh router, da cui ne deriva un costo minore. Tipicamente
10
implementano funzionalità minime di routing, non hanno funzionalità di bridge o gateway ed hanno una singola interfaccia radio.
Le architetture per una WMN possono essere individuate in tre grandi gruppi in base alle funzionalità dei nodi.
• Hierarchical Wireless Mesh Networks: questa architettura è
costituita da entrambe le tipologie di nodi, mesh router e mesh client. I mesh router tipicamente hanno una mobilità minima e sono connessi tra di loro da link wireless formando un’infrastruttura di backbone per i client. I mesh router svolgono tutte le funzionalità di routing, auto-configurazione della rete e recupero della connettività in caso di guasti. Inoltre tipicamente c’è almeno un mesh router con funzionalità di gateway per permettere ai client l’accesso alle reti esterne, come Internet, o reti di diverse tecnologie. La dorsale può essere costruita utilizzando tecnologie eterogenee, come IEEE 802.11 e IEEE 802.16, interfacciate tra loro tramite appositi gateway concentrati nei punti di connessione alle reti cablate o nei mesh router stessi. Dal punto di vista progettuale ci sono due approcci possibili per costruire una tale architettura. Uno è di progettare accuratamente il layout della rete, come ad esempio il posizionamento esatto dei mesh router e il tipo di antenne da utilizzare. L’altro, detto “unplanned”, è più spontaneo e casuale, nel senso che non viene progettata la topologia di rete. Ovviamente nel primo caso, a fronte di un maggiore studio progettuale e una minore flessibilità, si riescono ad ottenere prestazioni ed affidabilità maggiori, in quanto si conoscono a priori i link della rete mesh ed è possibile utilizzare tecniche aggiuntive per incrementare le prestazioni, come l’utilizzo di antenne direzionali. Questo tipo di
11
infrastruttura è la più comune e diffusa per i suoi vantaggi e praticità. Infatti, in questo scenario i client non necessitano di particolari funzionalità mesh e possono interfacciarsi direttamente con i mesh router della stessa tecnologia radio.
• Flat Wireless Mesh Networks: in questo tipo di architettura il client
rappresenta l’unica entità della rete e svolge allo stesso tempo le funzionalità di mesh router. La concezione è simile a quella di una rete ad hoc multi-hop, dove non è presente una backbone di trasporto comune. I client stessi implementano le funzionalità di routing, inoltro dei dati e configurazione della rete. Tipicamente tutti i nodi utilizzano la stessa tecnologia radio. La complessità di un nodo in questo tipo di infrastruttura è molto superiore a quella di una WMN strutturata, in termini di elaborazione e funzionalità implementate a livello software e hardware. Inoltre le prestazioni sono in genere inferiori poiché tipicamente un utente finale è provvisto di un solo modulo radio e condivide le risorse fisiche sia per la propria comunicazione che quelle degli altri nodi. Il vantaggio è quello di una maggior flessibilità in scenari applicativi dove è richiesta un’elevata mobilità.
• Hybrid Wireless Mesh Networks: questo tipo di architettura
combina entrambe le precedenti architetture, gerarchica e flat. In questo caso i client possono accedere alla rete sia attraverso i mesh router sia attraverso gli altri client. Allo stesso tempo, l’infrastruttura di backbone rende possibile la connettività con altre reti esterne, come WiFi, WiMax, WPAN ed altre WMNs. Questo scenario è forse il più
12
flessibile in quanto permette di incrementare la connettività e la copertura all’interno della WMN. La Figura 1.1 illustra un esempio di architettura ibrida, che riassume in se entrambe le architetture precedenti.
Internet
Wi-Fi, Wi-MAX Sensor Networks, Rei cellulari, ecc..
Wireless Mesh Client
Client convenzionali Mesh Router con
Gateway IP
Mesh Router con Gateway / Bridge Mesh Router con
Gateway
Mesh Router
Mesh Router Mesh Router Mesh Router
Mesh Router con Gateway / Bridge
Wireless Mesh Backbone
Figura 1.1: esempio di architettura Hybrid Wireless Mesh Network
1.1.2 Caratteristiche delle WMN
In seguito vengono descritte in modo generale le principali caratteristiche delle wireless mesh network, sia dal punto di vista delle peculiarità applicative che delle problematiche di sviluppo.
13
Connettività multi-hop
Uno dei vantaggi delle WMN è di fornire connettività tra i nodi (mesh router o client) che non possono comunicare direttamente tra loro. Per realizzare questo obiettivo la caratteristica fondamentale è la connettività multi-hop: questo principio può essere sfruttato per raggiungere un throughput adeguato senza sacrificare il raggio di copertura. Se si aumenta la densità dei nodi, utilizzando link wireless di distanza minore, si può coprire la stessa regione ed aumentare la capacità totale di accesso.
Autoconfigurazione
Una delle caratteristiche fondamentali che motivano lo sviluppo di una WMN è la flessibilità e la facilità di impiego. L’automatizzazione della formazione della topologia, l’autoconfigurazione e il ripristino automatico della connettività sono i punti chiave di questa architettura. Ogni nodo deve essere in grado di rilevare ed instaurare la connessione con gli altri nodi e adattarsi dinamicamente ai cambiamenti topologici necessari a garantire la connettività e massimizzare le prestazioni.
Interoperabilità
L’interoperabilità con altre tecnologie wireless e wired è uno dei requisiti fondamentali nello sviluppo di soluzioni wireless mesh. Ad esempio reti WMN basate sulla tecnologia 802.11 devono essere compatibili con lo standard 802.11 nel senso che devono supportare sia la comunicazione con i comuni client WiFi sia con gli apparati che implementano funzionalità mesh. Inoltre devono essere interoperabili con
14
altre tecnologie wireless, come WiMax, ZigBee e reti cellulari, in un’ottica di convergenza delle reti. Questo obiettivo è raggiunto attraverso l’utilizzo di Gateway che possono essere collocati nei nodi stessi o in un dispositivo centralizzato.
Scalabilità
Come è ben noto i protocolli di comunicazione multi-hop soffrono di problemi di scalabilità, ovvero quando la dimensione della rete cresce le prestazioni degradano significativamente. Il problema della scalabilità si presenta su vari livelli dello stack ISO/OSI. I protocolli di routing hanno difficoltà sempre maggiori, al crescere della rete, a trovare un nodo destinatario o il percorso migliore tra due nodi della rete. I protocolli a livello di trasporto soffrono della perdita frequente della connettività, e i protocolli di livello MAC sperimentano una significativa riduzione del throughput. Se questi problemi sono ben conosciuti nelle reti cablate, nelle reti wireless le difficoltà sono ancora maggiori. Il tipico esempio è lo standard IEEE 802.11 e i suoi derivati: come ben noto, a causa della condivisione del mezzo fisico, il throughput si riduce notevolmente all’aumentare del numero di hop.
Nelle WMN gli schemi di accesso al mezzo centralizzati, come il TDMA e CDMA, sono in generale difficili da implementare, a causa della loro complessità e requisiti di sincronizzazione temporale. Quindi le tecniche di accesso al mezzo distribuite, come il CSMA/CA, nonostante soffrano di una bassa scalabilità dovuta al meccanismo di contesa del mezzo, sono ancora le più diffuse. Per migliorare la scalabilità delle WMN
15
la ricerca si occupa sempre con maggiore interesse allo sviluppo di schemi di accesso al mezzo ibridi, basati su CSMA/CA e TDMA o CDMA.
Tecniche radio
Attualmente vari approcci sono stati proposti per aumentare la capacità e la flessibilità dei sistemi wireless. Gli esempi tipici sono le antenne direzionali e le smart antennas, i sistemi MIMO e i sistemi multi-radio / multi-channel. Per incrementare ulteriormente le prestazioni dei sistemi radio la ricerca si spinge anche sul controllo del livello fisico dai livelli superiori, attraverso sistemi radio riconfigurabili dai livelli applicativi. Queste tecnologie sono ancora in fase di ricerca e affinché se ne sfruttino tutte le potenzialità anche i livelli superiori devono essere progettati in modo adeguato per supportarli, in particolare il livello MAC e i protocolli di routing. Ad esempio quando le antenne direzionali sono utilizzate nelle reti mesh, il protocollo di routing deve tenere in conto il settore selezionato dall’antenna direzionale. Lo stesso vale per i sistemi MIMO e i sistemi radio riprogrammabili.
Connettività mesh
Molti dei vantaggi della tecnologia WMN nascono dall’elevata connettività della topologia magliata, che può essere sfruttata per fornire un’alta affidabilità in forma di percorsi alternativi in caso di fallimento di link. Per ottenere questo obiettivo è necessario quindi prevedere dei meccanismi appositi per il ripristino della connettività e che al tempo stesso ottimizzino le risorse disponibili.
16
Prestazioni
Negli ultimi anni sono stati svolti numerosi studi in ambito accademico sulle reti ad-hoc multi-hop ed è da queste esperienze, viste le similarità tra reti ad hoc multi-hop e reti wireless mesh, che partono gli studi di capacità delle WMN. Spesso i risultati teorici sono molto semplicistici e lontani dalla realtà e costituiscono solamente delle linee guida in termini di limini massimi e minimi raggiungibili [3] e [4]. Del resto le prove sperimentali sono più realistiche ma strettamente legate al tipo soluzione implementata, che come visto può essere una combinazione di numerosi fattori e scelte tecnologiche, pertanto tale argomento non può essere affrontato in via generale.
La capacità di una WMN è influenzata da molti fattori quali l’architettura di rete, la densità dei nodi, il numero di canali utilizzati da ogni nodo, le potenze di trasmissione, la mobilità dei nodi. Stabilire una relazione tra questi fattori e la capacità di rete è un problema molto complesso. Il livello MAC e le strategie di routing sono le principali scelte protocollari che influenzano la capacità ottenibile in un determinato scenario, ed è su questi aspetti che si tende maggiormente a fare ricerca per sviluppare soluzioni dedicate ottimali.
Per reti basate sul meccanismo di accesso al mezzo CSMA/CA, tipicamente IEEE 802.11, in linea generale, è stato dimostrato [3] che il throughput di ogni nodo in una WMN decresce come o(1 n), dove n è il numero totale di nodi nella rete. Utilizzare tecniche channel / multi-radio permette di incrementare notevolmente la capacità di una rete, poiché il traffico viene distribuito su più canali fisici coesistenti.
17
Gestione delle risorse energetiche
Un ulteriore aspetto di rilievo tecnologico di una WMN è legato alle risorse energetiche. I mesh router tipicamente non hanno limiti restrittivi riguardo alle potenze consumate. I client invece, a seconda dello scenario applicativo, possono avere dei limiti restrittivi sulle potenze consumate, ad esempio nel caso di reti di sensori o nel caso di laptop in mobilità. Ciò deve essere tenuto in considerazione alla base del progetto della rete mesh, non solo a livello hardware ma anche nella scelta della tecnologia radio utilizzata. Molti protocolli di livello MAC prevedono meccanismi di power management dedicati al controllo dell’efficienza energetica. Tuttavia tali meccanismi risultano spesso in uno stato di compromesso tra efficienza della rete e consumo energetico e non sempre sono efficaci per le architetture WMN.
Il controllo della potenza di trasmissione non è mirato solo all’efficienza di utilizzo delle risorse energetiche dei dispositivi ma influenza direttamente anche le prestazioni di rete. Ad esempio, ridurre la potenza di trasmissione riduce il raggio di trasmissione e quindi la densità di nodi in visibilità diretta: in questo modo si riesce a ridurre il livello di interferenza globale e aumentare il throughput di ogni singolo nodo; allo stesso tempo però viene influenzata la topologia provocando una minore ridondanza della rete e quindi minore affidabilità.
Da ciò appare evidente come il progetto di una soluzione WMN debba tenere conto in modo congiunto, in un approccio cross-layer, problematiche in apparenza disomogenee che vanno dal livello di trasporto a livello fisico.
18
Mobilità
La mobilità degli utenti è un requisito generale fondamentale in una WMN. Un client deve poter muoversi all’interno di una WMN senza perdere la connettività e possibilmente sperimentando un livello adeguato di qualità del servizio. Il problema della mobilità è uno dei più difficili da affrontare e dipende fortemente dalle scelte architetturali. Innanzitutto la raggiungibilità di un client è strettamente legata al protocollo di routing utilizzato, ma ancor prima al livello protocollare su cui è sviluppata la WMN. Una rete interamente a livello data link tipicamente ha molti meno problemi rispetto ad una completamente a livello IP.
In una rete mesh a livello IP, in caso di mobilità del client è necessario gestire in modo dinamico il piano di indirizzamento, e questo richiede dei meccanismi di segnalazione aggiuntivi che possono provocare dei tempi di latenza eccessivi durante l’handover. In letteratura sono state proposte soluzioni molto diverse per risolvere questo problema molte delle quali propongono soluzioni ibride che sfruttano i principi di MPLS, introducendo tecniche d’inoltro basate su etichette, senza bisogno di gestire il piano di indirizzamento. Altre ancora sfruttano le procedure stesse del Mobile IP.
1.1.3 Scenari applicativi
La ricerca e lo sviluppo sulle WMN è motivato da alcune applicazioni che trovano in questa tecnologia impieghi applicativi che non sono ottenibili con altrettanti vantaggi con altre tecnologie esistenti come le reti cellulari,
19
reti ad-hoc, reti di sensori o reti WLAN 802.11. In questo paragrafo verrà fatta una breve panoramica sugli impieghi delle WMN.
• Accesso broadband domestico: utilizzare una soluzione mesh per
fornire la copertura wireless in ambito domestico permette di coprire interamente un edificio attraverso l’installazione di più mesh router connessi tra di loro in modalità mesh, di cui almeno uno è connesso ad Internet. La comunicazione tra i nodi diventa più flessibile e più sicura rispetto a problemi di networking e caduta di collegamenti. Le eventuali zone buie possono essere eliminate semplicemente spostando i mesh router o automaticamente agendo sui livelli di potenza dei mesh router.
• Comunità e reti di vicinato: la tecnologia mesh può essere utilizzata
come alternativa alle soluzioni cablate di tipo DSL per la fornitura di accesso broadband in zone residenziali o rurali mediamente dense. L’idea consiste nell’equipaggiare le abitazioni con dei mesh router che comunicano tra loro per portare la connettività ad ogni nodo. Ciò consente anche una copertura parziale degli ambienti esterni, e una connettività diretta tra le abitazioni senza bisogno di un’infrastruttura cablata.
• Coperture aziendali: attualmente lo standard IEEE 802.11 è molto
diffuso come tecnologia di accesso in contesti aziendali. Spesso però i punti di accesso sono isole separate e la connettività tra di esse è realizzata attraverso una connessione Ethernet cablata, che rappresenta uno dei maggiori costi di installazione. Attraverso la tecnologia mesh si può coprire interamente gli edifici aziendali od anche uffici siti in
20
edifici diversi, installando dei mesh router al posto dei normali Access Point. Ciò permette, oltre ad evitare la copertura cablata, una maggiore robustezza della rete nel caso di caduta dei link o dei nodi. Inoltre la rete è facilmente estendibile in seguito a future espansioni fisiche dell’azienda.
• Reti metropolitane: è possibile estendere la tecnologia mesh per
coprire zone metropolitane di dimensioni rilevanti, per raggiungere una copertura broadband non solo degli edifici ma anche in scenari outdor. Ciò consente di realizzare un’infrastruttura di accesso in ambito urbano sul quale poter sviluppare anche servizi aggiuntivi, quali ad esempio servizi VoIP, oppure come base per fornire la copertura radio per le future reti cellulari.
• Sistemi di trasporto: i così detti sistemi di trasporto intelligenti
possono essere creati in modo efficiente attraverso la tecnologia wireless mesh per fornire informazioni real time relative ai trasporti pubblici, come informazioni di traffico, per controlli di sicurezza pubblica o per sistemi di guida intelligenti. I veicoli pubblici possono essere equipaggiati con una scheda wireless per comunicare con dei mesh router fissi in ambito urbano, i quali dialogano tra di loro per distribuire le informazioni real time.
• Automazione negli edifici: la tecnologia mesh può essere impiegata
per i sistemi di monitoraggio e controllo dei sistemi e degli impianti negli edifici di dimensioni considerevoli, come ad esempio il controllo dell’illuminazione, ascensori e condizionatori. Le applicazioni si possono estendere anche alla domotica in ambito domestico.
21
• Sistemi di sorveglianza e sicurezza: i sistemi di sorveglianza
possono beneficiare della connettività wireless mesh evitando le installazioni di infrastrutture cablate per trasporto delle informazioni. Ad esempio si possono semplicemente installare dei sistemi di video sorveglianza in un edificio, ciascuno fornito di un mesh router, e i flussi video verranno inoltrati direttamente al punto di gestione centralizzato.
• Situazioni di emergenza e disastri naturali: esistono già in
commercio prodotti mesh autoconfiguranti per realizzare reti di accesso provvisorie in zone colpite da disastri naturali o in situazioni di emergenza.
1.2 Progettazione cross-layer
Appare evidente come le problematiche e le prestazioni di una WMN dipendano da molti fattori eterogenei dal punto di vista dello stack protocollare, che vanno dal livello fisico fino ai livelli applicativi. La metodologia classica di progettare i protocolli di rete in modo stratificato e indipendente, nel caso delle WMN, non è la soluzione ottima.
Il canale fisico, nel caso delle reti wireless, è altamente variabile, in termini di capacità, bit error rate ecc.. Sebbene si possa controllare la codifica di canale, le modulazioni, ed utilizzare schemi per il controllo degli errori per migliorare le prestazioni del canale fisico, non c’è modo di garantire una capacità costante e percentuali di perdita nulle e quindi connessioni affidabili. Inoltre in una WMN la topologia di rete cambia
22
costantemente nel tempo a causa della mobilità dei nodi e il fallimento dei link dovuto a interferenze esterne o danni ai dispositivi. La natura dinamica della topologia impatta tutti i livelli di rete. Per ottenere prestazioni soddisfacenti, è necessario che il livello MAC, il livello di trasporto e il protocollo di routing interagiscano insieme e con il livello fisico.
Il progetto cross-layer può essere concepito in due modi differenti. Il primo approccio consiste nel migliorare le prestazioni di un certo protocollo ad un certo livello tenendo in conto parametri di altri livelli. Tipicamente sono i parametri dei protocolli di basso livello ad essere riportati ai protocolli di alto livello. Ad esempio, la percentuale di perdita di trame a livello MAC può essere considerata a livello di trasporto per far si che il TCP sia in grado di distinguere le situazioni di congestione dalla perdita di pacchetti. I parametri di livello fisico, come la qualità dei link, possono essere tenuti in conto da metriche appropriate nel protocollo di routing per aumentare l’efficienza dell’instradamento dei flussi. Il secondo approccio consiste nell’unire più protocolli di vari livelli in un unico meccanismo. Per esempio, nello standard IEEE 802.11s il protocollo di routing è combinato insieme al livello MAC. Il primo approccio mantiene un certo grado di trasparenza tra i vari livelli protocollari, mentre il secondo può garantire maggiori prestazioni grazie ad un elevato livello di interazione tra i protocolli.
Un approccio di tipo cross-layer tuttavia comporta notevoli difficoltà di progetto a causa della perdita dell’astrazione del concetto di livello protocollare, incompatibilità con protocolli esistenti e minore flessibilità di controllo e management.
23
1.3 Inquadramento nella pila protocollare
Una delle scelte primarie nella realizzazione di una WMN è il livello protocollare a cui gestire l’inoltro dei flussi all’interno della rete. La scelta riguarda il paradigma di forwarding e il protocollo per la gestione dei percorsi d’inoltro, e di conseguenza influisce sull’architettura globale della rete. Una WMN può essere costruita interamente a livello data link oppure interamente a livello IP, e talvolta con soluzioni intermedie e ibride a seconda del ruolo di ogni dispositivo nella rete.
A differenza delle reti cablate, in cui tipicamente il processo d’inoltro implica la ricezione da un’interfaccia e la trasmissione su un’interfaccia separata, nelle reti wireless multi-hop l’interfaccia fisica è la stessa. Pertanto la scelta del paradigma di forwarding è un aspetto fondamentale che influenza pesantemente le prestazioni.
Nella maggior parte delle implementazioni il processo d’inoltro avviene a livello 3, come illustrato in Figura 1.2. Ogni nodo riceve dall’interfaccia radio la trama di livello MAC, estrae il pacchetto IP, ricerca nelle tabelle di routing le informazioni per l’inoltro del pacchetto e lo ritrasmette in un tentativo di accesso al mezzo distinto. Questa rappresenta la soluzione più diffusa nell’attuale panorama delle WMN, grazie all’esistenza di numerosi protocolli di routing sviluppati negli ultimi anni per le reti wireless multi-hop, come ad esempio AODV [6] e OLSR [7].
24
802.11x PHY 802.11x MAC Routing
Livelli superiori Livelli superiori
802.11x PHY 802.11x MAC 802.11x PHY 802.11x MAC 802.11x PHY 802.11x MAC
Routing Routing Routing
Route Lookup Route Lookup
NIC NIC NIC NIC
Forwarding Node Forwarding Node
Sorgente Destinatario
Figura 1.2: processo di forwarding a livello 3
In un approccio di livello 2, l’inoltro avviene completamente basandosi sugli indirizzi dei frame MAC, come nelle normali reti cablate tipo Ethernet. Un esempio pratico è il Wireless Distribution System (WDS) IEEE 802.11. Alcuni dispositivi commerciali IEEE 802.11 consentono di connettere più AP tra loro, i quali dialogano su link wireless che formano un Wireless Distribution System. Ogni nodo agisce come un bridge e i link del WDS hanno la valenza di normali segmenti di LAN. Allo stesso modo delle reti cablate, per evitare la formazione di loop, tipicamente è necessario il protocollo Spanning Tree (STP) per la creazione di una topologia priva di loop. La principale limitazione di questa soluzione è la totale mancanza dei meccanismi di autoconfigurazione e di scelta intelligente dei percorsi d‘inoltro.
In entrambi i casi il processo d’inoltro viene trattato in tentativi di accesso al mezzo separati, con conseguente spreco di risorse. Si trovano in
25
letteratura alcuni studi per aumentare l’efficienza del meccanismo di forwarding nelle reti wireless multi-hop; la tendenza è quella di delegare direttamente alla scheda di rete le operazioni d’inoltro, evitando di appesantire il processing ai livelli superiori. Alcune soluzioni propongono delle tecniche di forwarding basate su etichette, in modo simile a MPLS, con lo scopo di snellire i processi di lookup delle tabelle. (vedi [31]).
Dal punto di vista architetturale una rete interamente a livello 2 appare ai client semplicemente come un unico link, teoricamente come nelle reti cablate condivise. Il client ha un gateway di default configurato e in caso di mobilità cambia solamente il punto di accesso alla rete a livello data link, mantenendo invariate le configurazioni del client a livello IP. Viceversa in una rete WMN interamente a livello IP, il client ha configurato un gateway di default sullo stesso nodo dove ha la connettività a livello data link, e in caso di mobilità, il gateway ed eventualmente l’indirizzo IP del client, devono essere riconfigurati. I principali problemi di un’architettura a livello IP sono rappresentati dalla gestione della mobilità dei client e la necessità di configurare dinamicamente il piano di indirizzamento.
Un’altra soluzione può essere quella di avere una WMN costituita da parti interamente a livello data link e mesh router che operano anche a livello IP, ovvero una via di mezzo tra le due soluzioni estreme precedenti (Figura 1.3)
26
MAC IP MAC IP MAC MAC MAC MAC MAC MAC MAC MAC MAC IP MAC IP MAC IP MAC IP MAC MAC MAC MAC MAC MAC MAC MAC Internet Connessione Link layerConnessione IP layer
Figura 1.3: architettura protocollare di una mesh ibrida
In questo caso una WMN può essere connessa ad altre WMN, ed alcune di queste avere un punto di accesso verso reti esterne, come Internet. In questo scenario, una singola WMN è interamente a livello data link, mentre la connettività tra le diverse WMN è gestita utilizzando protocolli di routing a livello IP. Gli handover all’interno della stessa WMN sono in questo modo trasparenti al client, che viene coinvolto solo nell’handover tra WMN differenti Questo ultimo scenario è molto simile alla soluzione sviluppata in questo lavoro di tesi.
Il tipo di soluzione scelta, dal punto di vista della rete, influenza la progettazione di tutto lo stack protocollare ed il modo di gestire i servizi mesh, come, ad esempio, la mobilità dei client.
27
Esistono poi alcune soluzioni di livello intermedio, che si presentano come un livello separato nello stack protocollare, tra il livello data link e il livello di rete. L’idea consiste nell’aggiungere un nuovo livello, che si presenta nella pratica come header aggiuntivo tra quelli IP e MAC, che si occupa completamente e in modo trasparente di tutte le problematiche della rete mesh, dalle scelte d’inoltro dei flussi alla configurazione della rete.
MAC IP livello fisico Mesh layer Formazione topologia Decisioni di routing Gestione della mobilità
Figura 1.4: soluzione intermedia tra il livello MAC e IP (layer 2.5)
Un esempio di questa architettura è la soluzione mesh realizzata da Microsoft denominata Mesh Connectivity Layer (MCL) [8], che si presenta sotto forma di modulo software ed agisce come livello indipendente e trasparente tra il livello IP e il livello MAC. In ambito open source uno degli esempi più rilevati è FLAME (Forwarding Layer for Mesh) [9] che funziona secondo uno schema di principio molto simile.
28
1.4 WMN basate su standard IEEE 802.11
Lo standard IEEE 802.11 è divenuto lo standard di fatto nelle reti wireless, sia in ambito residenziale che business, per la realizzazione di local area networks (LANs). La maggior parte di questi scenari opera in modalità infrastruttura, dove una serie di Access Point servono da punto di connessione per le stazioni mobili e forniscono l’accesso ad Internet. Il ruolo attuale di IEEE 802.11 è limitato alla connettività tra client mobili ed Access Point. La capillare diffusione commerciale di questa tecnologia rende desiderabile estendere le soluzioni mesh alle comuni WLAN.
Da punto di vista della fattibilità, lo standard 802.11 non pone alcun limite logico per cui non sia possibile realizzare una WMN basata su questa tecnologia. In linea di principio ciò è possibile delegando agli strati superiori del modello OSI tutte le problematiche che lo standard non copre, come ad esempio il routing e l’inoltro multi-hop. Ciò di per se non rappresenta un violazione di alcun principio, se vediamo lo standard 802.11 semplicemente come un protocollo di livello data link; tuttavia è ben noto che, a differenza delle reti cablate, le reti wireless presentano problematiche ben più onerose, che possono essere affrontate in modo efficiente solo tenendone in considerazione ai livelli più bassi del modello ISO/OSI. Ad esempio IEEE 802.11 prevede la possibilità di instaurare una connettività ad-hoc tra vari nodi, ma non affronta in nessun modo il problema della comunicazione multi-hop, che viene invece risolto attraverso l’impiego di protocolli di routing a livello 3.
29
Lo standard IEEE 802.11 offre varie modalità di funzionamento su cui basare lo sviluppo di una rete mesh, in particolare le modalità AP, ad-hoc e WDS. La modalità ad-ad-hoc consente di formare una rete punto-punto con un altro nodo senza l’uso di un Access Point. La modalità WDS (Wireless Distribution System) sfrutta tutti e quattro gli indirizzi dell’header MAC, e permette la formazione di link punto-punto tra AP, ciascuno dei quali opera non solo come base station (modalità AP), ma anche come nodo ripetitore (relay). Tuttavia, prima che IEEE 802.11 possa essere usato per costruire una WMN efficiente, devono essere introdotte tutte le caratteristiche peculiari delle reti mesh, descritte nel paragrafo 1.1.2. Uno dei problemi di maggior rilievo nelle applicazioni mesh è quello delle prestazioni, in particolare la bassa capacità end-to-end e la mancanza di fairness nella distribuzione tra i flussi dati.
Il problema della capacità nelle tecnologie IEEE 802.11 è uno dei più critici ed in particolare nelle applicazioni multi-hop è ancora più severo. In una WMN, nella configurazione più semplice, tutti i nodi operano sullo stesso canale radio. Questo comporta un’interferenza sostanziale sia tra le trasmissioni adiacenti sullo stesso percorso (interferenza intra-flow) sia tra flussi di path diversi su nodi vicini (interferenza inter-flow). Come ben noto il meccanismo di accesso al mezzo utilizzato da IEEE 802.11 è il CSMA/CA, basato sull’accesso al mezzo su base statistica da parte dei nodi. Poiché il mezzo è condiviso solo un nodo può trasmettere una volta acquisito l’accesso al mezzo. Quindi tutti gli altri nodi in visibilità radio, interferenti, devo attendere che il mezzo si liberi prima di trasmettere.
30
B B D D E E FF C C P P Interferenza intra-flow Interferenza inter-flow Flusso 1 Flusso 2 Single Channel WMNFigura 1.5: interferenze intra-flow e inter-flow in reti mesh single-channel
Un limite ben noto nella tecnologia IEEE 802.11 è il problema dei nodi nascosti. Sebbene il meccanismo RTS/CTS risolva tale problema, non può evitare che i nodi nascosti inizino contemporaneamente la sequenza RTS/CTS e inevitabilmente ciò comporta dei pesanti ritardi dovuti al meccanismo di backoff. Inoltre il TCP esaspera ancora di più il problema effettuando un ulteriore processo di backoff. Come risultato un flusso TCP che attraversa un link inibito dal problema del nodo nascosto, tende nel tempo ad essere soppresso definitivamente.
Un altro problema ben noto nella tecnologia IEE 802.11 è la cosiddetta “anomalia”. Quando due link interferenti non sono nascosti l’un l’altro e gestiscono lo stesso numero di flussi, il MAC IEEE 802.11 alloca
31
mediamente lo stesso numero di tentativi di trasmissione ad entrambi i flussi. Tuttavia, i due link possono operare a bit rate molto differenti, ad esempio 1 e 11 Mbps. In questo caso, il throughput effettivo del link operante a 11 Mbps è limitato dal link operante ad 1 Mbps.
Il problema della fairness a livello MAC 802.11 è dovuto al fatto che il meccanismo di accesso al mezzo DCF è stato progettato per fornire un accesso equo al mezzo solo in un contesto locale, all’interno dell’area di copertura di un singolo nodo. In uno scenario multi-hop tale meccanismo fallisce nel garantire l’equità dell’allocazione delle risorse a flussi diversi.
Internet
MAP 1 MAP 2 MAP 3 GW
Path 1
Path 2
Path 3
Figura 1.6: problema della fairness tra i flussi in una topologia mesh lineare
Un flusso che attraversa più hop deve necessariamente competere per accedere al mezzo in ogni nodo del percorso, poiché il traffico inoltrato è trattato esattamente come il traffico originato localmente. Un caso estremo si verifica nel caso di una WMN di accesso dove il traffico è diretto dai nodi di accesso verso un gateway verso la rete Internet, creando una topologia
32
logica ad albero con radice il gateway. In questo scenario è ovvio che il traffico originato dai nodi più vicini al gateway ottiene una frazione maggiore del throughput rispetto ai flussi originati dai nodi più lontani dal gateway. Nell’esempio di Figura 1.6, i flussi che seguono il path 1 sono penalizzati rispetto agli altri path ed ottengono un throughput minore.
Per risolvere questo tipo di problema è necessario operare direttamente sul meccanismo di accesso al mezzo inglobando nel MAC algoritmi di scheduling che gestiscano in modo distribuito l’allocazione delle risorse in modo equo e, possibilmente, tendendo conto della qualità del servizio richiesta dai vari flussi. Queste problematiche tra l’altro sono state affrontate dallo standard IEEE 802.11e, dove è stato introdotto il meccanismo di accesso al mezzo EDCA [42]. L’alternativa consiste nel gestire l’allocazione delle risorse ai livelli più alti dello stack protocollare, ad esempio a livello di trasporto.
1.5 Routing nelle reti mesh
Trattandosi di una rete multi-hop, il protocollo di routing è necessario per governare l’instradamento dei flussi all’interno della rete. Il progetto di un protocollo di routing efficiente dipende sia dall’architettura sia dallo scenario applicativo della rete mesh. Negli ultimi anni la ricerca ha prodotto numerosi protocolli di routing per le reti ad-hoc multi-hop, ne è un esempio il noto protocollo AODV (Ad Hoc Distance Vector) ratificato nella rfc 3561 [6] dal gruppo di lavoro MANET (Mobile Ad-Hoc Networks) di IETF. La
33
maggior parte dei protocolli proposti in letteratura scientifica per le WMN, riprende tali protocolli apportando le opportune modifiche. La caratteristica principale che distingue le WMN dalle MANET, dal punto di vista del routing, è il fatto che i mesh router tipicamente sono stazionari, quindi il routing non è limitato dai problemi di scalabilità dovuti alla elevata mobilità dei nodi nelle MANET.
Uno degli aspetti decisivi per l’efficienza di un algoritmo di routing è la metrica utilizzata, ovvero il parametro in base al quale scegliere il percorso di instradamento tra due nodi. La metrica hop count, tipicamente utilizzata nei protocolli di routing per reti cablate, non garantisce prestazioni adeguate poiché non tiene in conto in nessun modo delle caratteristiche peculiari del mezzo wireless.
Nel resto del paragrafo non verrà fatta una panoramica sugli algoritmi di routing esistenti poiché lo scenario delle proposte è molto ampio; si cercherà piuttosto di definire una classificazione generale di tali protocolli e descrivere le caratteristiche principali, ponendo particolare attenzione alle metriche.
1.5.1 Classificazione dei protocolli
Sebbene anche nell’ambito delle WMN si possa fare la classica distinzione tra le due grandi categorie di algoritmi di routing, ovvero link state e distance vector, conviene seguire un'altra metodologia, che consenta di mettere maggiormente in risalto le differenti caratteristiche dei numerosi
34
protocolli di routing proposti negli ultimi anni nel campo delle reti wireless multi-hop.
In base alla stratificazione funzionale dei percorsi di instradamento creati dal protocollo di routing, si possono distinguere protocolli di tipo gerarchico o flat.
• Nei protocolli gerarchici si può individuare una gerarchia funzionale tra i nodi, in cui ogni livello gerarchico ha un diverso compito nella gestione dei percorsi di instradamento. Nel caso in cui i nodi di un certo livello gerarchico falliscono nella ricerca di un percorso, tale responsabilità è delegata ai nodi di livello gerarchico maggiore; questa tecnica è utilizzata, ad esempio, dal protocollo HSR (Hirarchical State Routing [10]).
• I protocolli di tipo “flat”, invece, non hanno nessuna gerarchia e tutti i nodi operano ad un pari livello di responsabilità nella ricerca dei percorsi di instradamento.
La seconda classificazione distingue invece i protocolli in base al tipo di topologia che formano i percorsi di instradamento.
• Il primo approccio è il caso in cui il protocollo opera su una rete la cui topologia è già predefinita. A differenza delle reti ad hoc, in una WMN la mobilità dei nodi è limitata e per aumentare l’efficienza si può sfruttare tale vantaggio per costruire una backbone. Un esempio è il caso in cui il protocollo di routing a livello IP opera sopra una backbone ad albero costruita a livello 2 dal protocollo Spanning Tree (STP).
35
• L’altro approccio è quello di utilizzare protocolli di routing che non si appoggiano a nessuna backbone sottostante, creando percorsi peer-to-peer in modo libero tra ogni nodo della rete.
• Il terzo possibile approccio è un approccio ibrido: l’idea è di creare una certa topologia di backbone, di tipo mesh od ad albero a seconda dello scenario, che può essere usata per accelerare o supportare i meccanismi di routing che non si appoggiano ad una backbone. Infine, i protocolli di routing possono essere distinti in base al modo in cui mantengono le informazioni di routing. Si può distinguere tra schemi di routing preventivi, detti anche table-driven, protocolli reattivi, detti anche on-demand, e approcci ibridi.
• Nel caso di protocolli preventivi, ogni nodo scambia periodicamente le sue informazioni di routing con gli altri nodi e mantiene localmente le informazioni per raggiungere ogni nodo della rete. Esempi di questo approccio sono DSDV [11], OLSR [7], WRP [12] e STAR [13]. • Nei protocolli reattivi, un nodo richiede e mantiene le informazioni dei
percorsi solo quando necessita di comunicare con un altro nodo. Tipici esempi di questo approccio sono AODV [6], DSR [14], MRLQSR [15].
• Infine gli approcci ibridi traggono benefici da entrambi i precedenti metodi, ad esempio il protocollo di routing designato come mandatario nello standard IEEE 802.11s, detto HWMP, Hybrid Wireless Mesh Protocol, che viene descritto dettagliatamente nel capitolo 2.
36
1.5.2 Caratteristiche
Da un punto di vista qualitativo, i requisiti ottimi per un algoritmo di routing per una WMN sono strettamente legati all’architettura di rete ed al suo utilizzo. In via generale, tuttavia, è possibile identificare alcuni requisiti fondamentali:
• scalabilità: deve essere in grado di mantenere prestazioni, se non costanti, almeno adeguate al crescere delle dimensioni della rete • robustezza e affidabilità: deve essere in grado di reagire alle situazioni
di guasto o peggioramento delle prestazioni, ripristinando in tempi brevi la comunicazione, sfruttando l’alta connettività e ridondanza topologica di una rete mesh
• supporto alla mobilità: il protocollo deve essere in grado di reagire prontamente alla mobilità dei client senza interrompere la comunicazione e senza degrado della QoS. Tipicamente protocolli di tipo preventivo sono più adatti in scenari con bassa mobilità mentre i protocolli di tipo reattivo sono più adatti in situazioni di elevata mobilità.
• basso overhead: naturalmente ogni protocollo di routing introduce un overhead aggiuntivo e un carico di traffico nella rete che deve essere il più basso possibile in quanto occupa risorse utili. Oltre all’entità delle risorse impiegate anche la loro distribuzione nel tempo è un fattore importante. Ad esempio i protocolli di tipo preventivo, come OLSR [7] introducono un carico costante nella rete mentre quelli di tipo reattivo, come AODV, occupano risorse in istanti temporali
37
concentrati nei momenti di ricerca dei percorsi. Vantaggi e svantaggi ancora una volta dipendono fortemente dagli obiettivi e dallo scenario applicativo.
• velocità nello stabilire un percorso d’inoltro: la velocità con cui il protocollo è in grado di stabilire un percorso d’inoltro per un flusso dipende fortemente dal meccanismo utilizzato; i protocolli di tipo preventivo sono tipicamente più veloci in quanto mantengono localmente informazioni aggiornate sui percorsi d’inoltro mentre i protocolli di tipo on-demand devono eseguire una procedura di ricerca che talvolta può richiedere un tempo eccessivo
La difficoltà di progettare una soluzione efficiente in un determinato scenario sta nel trovare il giusto compromesso tra i molti fattori che influenzano le prestazioni. Aumentare la complessità tecnologica di una soluzione spesso comporta la necessità di utilizzare un approccio cross-layer nella progettazione dell’intero stack protocollare. Il protocollo di routing in particolare deve tener conto di tutte caratteristiche del livello fisico e MAC. Ad esempio l’utilizzo di tecniche radio avanzate o di antenne direttive influenza pesantemente le scelte del protocollo di routing il quale deve tenerne conto internamente per sfruttare tutti i vantaggi delle scelte tecnologiche dei livelli inferiori. Ad esempio, in una WMN che utilizza le tecniche multi-channel, il protocollo di routing deve essere disegnato appositamente altrimenti può vanificare gli importanti vantaggi che si ottengono dall’utilizzo delle tecniche multi canale.
38
1.5.3 Tecniche di routing
Nel seguito vengono descritte sommariamente due tecniche di routing, le quali, piuttosto che illustrare il funzionamento di una determinata classe tra quelle descritte nel paragrafo 1.5.1, mettono in luce ulteriori accorgimenti e scelte algoritmiche valide per più tipi di protocolli.
Multipath routing
La maggior parte dei protocolli di routing utilizzano un unico percorso per instradare flussi tra una coppia di nodi. Una possibilità è quella di trovare ed utilizzare più percorsi tra il nodo sorgente e quello destinatario. La presenza di più percorsi garantisce un alto grado di affidabilità in caso di fallimento del percorso primario velocizzando inoltre i tempi di ripristino della connessione. Inoltre il traffico può essere distribuito sui vari percorsi non interferenti per ottenere un maggior throughput ed applicare tecniche di load balancing. Come in ogni protocollo, esiste sempre un trade-off tra prestazioni e complessità, ed ogni soluzione deve essere valutata in base a vantaggi e svantaggi in un determinato scenario applicativo.
Tra le varie proposte nella letteratura scientifica vale la pena citare AOMDV [16], una variante multipath di AODV e i lavori di Lee e Gerla [13] e Roy [18].
Routing “opportunistico”
I protocolli di routing tradizionali tipicamente decidono una sequenza di nodi che formano il percorso tra una sorgente e un destinatario ed inoltrano i pacchetti attraverso questi nodi. Questa tecnica tuttavia non tiene
39
in considerazione la caratteristica broadcast delle trasmissioni wireless. In particolare quando un nodo intermedio fallisce nel ricevere un pacchetto, il pacchetto deve essere ritrasmesso dal nodo intermedio anche se altri nodi vicini lo hanno ricevuto in modo corretto e possono inoltrarlo verso la destinazione.
ExOR [17] è un meccanismo di routing che tiene conto di questa caratteristica cercando di minimizzare il numero totale di trasmissioni. Per far questo ExOR prende le decisioni di forwarding in modo ritardato: i pacchetti vengono trasmessi broadcast ad ogni hop, viene determinato quali nodi hanno ricevuto correttamente il pacchetto, poi l’algoritmo sceglie tra questi il nodo migliore che si occuperà di inoltrare il pacchetto. Ancora una volta tale soluzione ha vantaggi e svantaggi, ed esistono meccanismi simili, come ROMER [20] che migliorano molte sue caratteristiche.
1.5.4 Metriche
Il principale fattore che influenza le prestazioni del protocollo di routing è la metrica utilizzata. La maggiore differenza di una WMN rispetto alle reti cablate è l’inaffidabilità del mezzo wireless combinata con i ben noti limiti dei protocolli di accesso al mezzo. La qualità che sperimenta un link in un mezzo wireless dipende da molti fattori ed è variabile nel tempo, e questo è il motivo per cui i protocolli di routing basati sull’hop count sono poco efficienti negli scenari wireless.
La progettazione di una metrica non può scindersi dalla progettazione del protocollo di routing, come il protocollo di routing non può prescindere dal tipo di soluzioni tecnologiche impiegate a livello fisico e MAC. E’ per
40
questo che l’approccio cross-layer ricorre pesantemente, più che in altri aspetti, nella progettazione delle metriche.
1.5.4.1 Requisiti
Per assicurare buone prestazioni, le metriche devono soddisfare quattro requisiti.
1. La metrica non deve causare frequenti cambiamenti dei percorsi al fine di assicurare la stabilità della rete;
2. deve tenere in conto le caratteristiche della rete mesh assicurando che il percorso a costo minimo sia quello con prestazioni migliori; 3. deve assicurare che il percorso a peso minimo possa essere trovato
da algoritmi efficienti con complessità sostenibile;
4. deve assicurare che il protocollo di routing non possa formare dei loop nella rete;
Stabilità dei percorsi
La qualità dei link wireless in una WMN varia molto velocemente nel tempo, sia per le caratteristiche intrinseche del mezzo radio sia a causa dell’alto grado di interferenza tra i nodi. Sebbene la metrica debba tener conto della qualità dei link, il calcolo del costo deve essere tale da non provocare frequenti fluttuazioni dei percorsi con conseguente spreco di risorse di elaborazione e abbattimento delle prestazioni.
La stabilità del costo di un certo percorso dipende da quali caratteristiche del percorso la metrica tiene conto. Ad esempio metriche che calcolano il costo basandosi su proprietà topologiche, quali l’hop count o la
41
capacità del path, sono tipicamente più stabili rispetto alle metriche sensibili al carico della rete [21]. Inoltre studi teorici dimostrano che metriche sensibili al carico della rete sono più adatte a protocolli di routing di tipo reattivo mentre hanno prestazioni scadenti se applicate a protocolli di routing di tipo preventivo [21].
Buone prestazioni per il percorso a peso minimo.
Per assicurare un utilizzo efficiente delle risorse di rete, il percorso a costo minimo deve garantire buone prestazioni in termini di throughput e ritardi. Per ottenere ciò le metriche devono essere in grado di catturare le caratteristiche della WMN che impattano sulle prestazioni dei percorsi. Le principali caratteristiche sono le seguenti:
• Lunghezza del percorso. Ogni salto aggiuntivo introduce un ritardo e aumenta la probabilità di perdita di un pacchetto, facendo mediamente aumentare il ritardo end-to-end e riducendo il throughput.
• Capacità dei link. La capacità di un link wireless varia con la distanza poiché le attuali tecnologie radio permettono di adeguare il rate di trasmissione in base alla qualità sperimentata dal canale. Ne risulta che i link più brevi mediamente hanno una capacità maggiore, poiché sperimentano una qualità di canale migliore. Quindi se si scelgono i link di un percorso in base alla capacità, tipicamente il percorso end-to-end risulta formato da un numero maggiore di salti rispetto al percorso di minima lunghezza.
• Percentuale di perdita dei pacchetti. Un nodo può dover trasmettere un pacchetto più volte sui link con alta percentuale di perdita con conseguente aumento dei ritardi e diminuzione del throughput. A
42
causa del problema dell’anomalia delle reti IEEE 802.11, in questo tipo di tecnologia, tale evento comporta conseguenze anche più gravi. • Interferenze. Il flusso attraverso un link wireless non consuma solo la
banda dei nodi lungo il percorso, ma contende la banda anche coni nodi vicini interferenti lungo il percorso. Questo è il problema dell’interferenza inter-flow. La metrica deve aiutare il protocollo di routing a scegliere il percorso che non solo bilancia il carico di traffico, ma che riduce anche questo tipo di interferenze. L’altro tipo di interferenza è quella intra-flow: i nodi lungo il percorso dello stesso flusso competono l’un l’altro per l’accesso al mezzo e ciò comporta oltre uno spreco di risorse, una diminuzione del throughput e aumento del ritardo end-to-end. Una metrica ottimale deve poter tener conto di entrambi i tipi di interferenza. Tuttavia è molto difficile ottenere questo risultato poiché sia il canale utilizzato da un link che la sua capacità sono entrambi correlati al livello di interferenza che si impone ai nodi vicini. Infatti, in termini di capacità, un pacchetto trasmesso su un link a 1 Mbps impiega per più tempo il mezzo rispetto allo stesso pacchetto trasmesso su un link a 10 Mbps, aumentando sia l’interferenza intra-flow sia quella inter-flow.
1.5.4.2 Panoramica delle principali metriche
Lo studio delle metriche, soprattutto in ambito accademico, è uno degli ambiti di ricerca più attivi, infatti, nella letteratura scientifica si
43
possono trovare un numero molto elevato di soluzioni. Vediamo in seguito alcuni esempi.
Expected Transmission Count
Una delle più semplici è la metrica ETX (Expected Transmission Count) [22] e [23], definita come il numero medio di tentativi di trasmissione a livello MAC necessari per una corretta consegna di una trama su un link. Il costo di un percorso è la somma dei costi dei singoli link.
Questa metrica tiene conto sia della percentuale di perdita su un link sia della lunghezza del percorso, tuttavia non considera in nessun modo il problema dell’interferenza o il fatto che link differenti possono avere rate trasmessivi diversi. Una metrica molto simile è la Airtime metric, utilizzata come metrica di default nello standard IEEE 802.11s, e che viene descritta con maggior dettaglio nel capitolo 2.
Expected Transmission Time
La ETT (Expected Transmission Time) [24] si propone come miglioramento alla ETX considerando anche la differenza del rate trasmissivo sui link. Il costo di un link è definito come il tempo medio previsto per trasmettere con successo una trama a livello MAC sul link. Il costo di un percorso è la somma dei costi dei singoli link. Come la ETX anche la ETT non tiene conto delle interferenze inter-flow e intra-flow.
44
Weighted Cumulative ETT (WCETT)La WCETT (Weighted Cumulative ETT) [24], si propone come miglioramento della ETT cercando di ridurre il numero di nodi lungo un percorso che trasmettono sullo stesso canale, tenendo quindi in considerazione il problema dell’interferenza intra-flow.
Trascurando i dettagli algoritmici, vale la pena riportare un problema che mette in luce un altro tipo di difficoltà nel progetto delle metriche: non esiste un algoritmo efficiente del calcolo della WCETT poiché la metrica non è isotonica. Una metrica è isotonica se assicura che l’ordine di grandezza del peso di due path viene preservato se ad essi viene preposto o posposto un terzo path comune. Inoltre se viene utilizzata in un protocollo di routing di tipo link-state tale metrica può causare dei loop nella rete.
Esistono in letteratura metriche ancora più complesse che tentano di tenere in considerazione tutti i fattori precedentemente elencati, compresa l’interferenza inter-flow, ad esempio la metrica MIC (Metric of Interference and Channel-switching) [25].
E’ evidente come all’aumentare della complessità di tali soluzioni emergono problemi di rilevanza sempre maggiore, non solo dal punto di vista analitico ma anche pratico, nel senso di applicabilità in un contesto reale. Inoltre per aumentare l’efficienza tali metriche tengono in considerazione numerosi parametri che non sempre è facile ricavare dal punto di vista implementativo. Alcune di queste metriche inoltre, per stimare i parametri necessari alla computazione del costo, iniettano traffico di probing aggiuntivo nella rete, comportando un ulteriore spreco di risorse.
45
1.6 Multi-radio / multi-channel
L’utilizzo di tecniche multi-channel consente di ottenere numerosi vantaggi e risolvere alcuni dei problemi affrontati in questo capitolo. Come detto in precedenza i mesh router in un’architettura strutturata, spesso supportano l’utilizzo di più moduli radio, e ciò permette, a fronte di una maggiore complessità, un notevole incremento delle prestazioni.
Nelle architetture più semplici di WMN, ogni nodo è equipaggiato con una singola interfaccia, che tipicamente è configurata per lavorare sullo stesso canale degli altri nodi per consentire la connettività. Per utilizzare più canali distinti nella solita rete è necessario che i dispositivi abbiano più interfacce radio o abbiano la possibilità di cambiare il canale nel tempo. I dispositivi con più interfacce radio possono impostare ogni interfaccia su un canale diverso; se, inoltre, supportano il channel-switching possono cambiare dinamicamente il canale e trasmettere su ognuno di essi per un certo periodo di tempo.
Il channel-switching richiede un elevato livello di sincronizzazione tra i nodi, affinché possano trasmettere e ricevere sullo stesso canale. Un possibile schema è quello in cui tutti i nodi cambiano il canale operativo secondo un qualche ordine prefissato. Ogni interfaccia commuta su tutti i possibili canali in differenti slot temporali, secondo un ordine pseudocasuale basato su un seme comune, e due nodi possono comunicare tra loro solo negli slot in cui utilizzano lo stesso canale. Il vantaggio di questo schema è che il traffico è bilanciato tra tutti i possibili canali con conseguente riduzione del livello di interferenza globale. Tuttavia, un tale
46
meccanismo richiede un livello di sincronizzazione a grana fine dal punto di vista temporale, che è difficile da ottenere senza opportune modifiche al livello MAC di IEEE 802.11.
Pertanto l’approccio più promettente nel costruire una WMN multi canale basata su IEEE 802.11 è quello di utilizzare mesh router equipaggiati con più schede radio, ciascuna delle quali configurata su un determinato canale. Gli standard IEEE 802.11b/g e IEEE 802.11a hanno la possibilità di operare rispettivamente su 3 e 12 canali ortogonali, che possono essere sfruttati per comunicare simultaneamente con i nodi vicini, eliminando del tutto, o in parte, l’interferenza. Un nodo con due interfacce radio, settate su canali ortogonali, può comunicare contemporaneamente con due nodi vicini, senza il bisogno di contendersi il mezzo. In questo modo viene ridotta l’interferenza intra-flow (vedi Figura 1.5). Scegliendo in modo intelligente il canale di ogni link, si riesce a ridurre anche l’interferenza inter-flow. In questo modo la concorrenza globale per l’accesso al mezzo viene ridotta notevolmente e la capacità della rete aumenta.
Le tecniche di assegnazione del canale radio alle varie interfacce rappresentano il punto chiave per ottimizzare l’utilizzo delle risorse in un’architettura di questo tipo. Intuitivamente, l’obiettivo della metodologia di assegnamento dei canali è di ridurre il livello di interferenza globale utilizzando più canali possibili mantenendo però un adeguato livello di connettività tra i nodi.
In letteratura scientifica i metodi proposti per l’assegnazione dei canali sono molto numerosi, e tale area rappresenta una delle tematiche di ricerca più seguite in ambito accademico. Piuttosto che fare una panoramica
47
delle soluzioni proposte, nel seguito viene fatta una classificazione in base alle caratteristiche su cui si basano tali metodi.
1.6.1 Assegnazione dei canali basata sulla topologia
L’assegnamento dei canali può essere fatto semplicemente basandosi sulla topologia di rete, con l’obiettivo di minimizzare il livello di interferenza per ogni link. Il problema, in questo caso, si riduce al problema di colorare un grafo seguendo certi limiti, dove il numero di rami uscenti da un nodo rappresenta il numero di canali disponibili e il colore rappresenta il canale radio. Il problema è notoriamente complesso dal punto di vista computazionale e le soluzioni pratiche in genere sono solo delle approssimazioni.
Ad esempio Marina e Das [26] propongono una soluzione basata su questo approccio che ha come obiettivo quello di minimizzare la massima interferenza sperimentata da ogni link.
Subramanian [27], propone invece una soluzione basata su una ricerca esaustiva della soluzione ottima eseguita ciclicamente per un determinato numero di iterazioni. L’approccio è quello di minimizzare l’interferenza inter-flow per ogni possibile canale.
Un altro tipo di approccio, proposto da Das [28], ha come obiettivo quello di cercare di massimizzare il numero di link che possono essere attivi simultaneamente.
48
1.6.2 Assegnazione dei canali basata sul livello di traffico
I meccanismi di assegnamento dei canali in base alla topologia, si basano sulla premessa che tutti i link della rete siano equamente caricati. Tuttavia è ovvio come tale requisito non sia soddisfatto in un’architettura di rete così dinamica. Questo secondo metodo ha l’obiettivo di assegnare i canali ad ogni interfaccia in modo che la banda disponibile su ogni link sia proporzionale al traffico che deve trasportare. Poiché il carico dei link viene determinato tipicamente dagli algoritmi di routing, la soluzione ideale sarebbe operare la scelta dell’assegnazione dei canali in modo congiunto alle funzionalità del routing. Dal punto di vista algoritmico il problema è identico alle tecniche di traffic engineering tipicamente utilizzate nelle reti cablate, come ad esempio nel caso di MPLS. Tuttavia, per rendere efficiente una simile tecnica è necessario l’utilizzo di meccanismi di scheduling potenti che controllino in modo adeguato la distribuzione dei flussi a livello MAC.1.6.3 Assegnazione dinamica dei canali
La tecnica più evoluta in questo contesto è quella di avere un meccanismo che assegni i canali ai link in modo dinamico, ovvero facendo in modo che ogni interfaccia cambi il canale operativo nel tempo per soddisfare qualche requisito. Se l’assegnazione statica dei canali è un problema già di per se oneroso dal punto di vista computazionale,
49
l’assegnazione dinamica rappresenta un problema ancora più complesso, poiché si deve tener conto del fattore temporale.
Il problema principale riguarda la dipendenza diretta tra i canali utilizzati da nodi diversi. La connettività rimane sempre l’obiettivo principale per consentire la comunicazione, e due nodi vicini devono operare sullo stesso canale per poter comunicare. E’ intuitivo come cambiare il canale di un singolo nodo influenzi le decisioni di assegnazione di intere porzioni della rete, tanto più ampie tanto più è limitato il numero di interfacce per ogni nodo e il numero di canali disponibili.
Per esplicare con maggiore chiarezza il problema, esaminiamo la situazione nella Figura 1.7:
dipendenza dal canale tra i nodi
Figura 1.7: illustrazione del concetto di dipendenza del canale utilizzato tra i nodi
della rete
Questo esempio mostra come cambiare un canale di un certo link renda necessario una riassegnazione dei canali in altre porzioni di rete a
50
causa della dipendenza tra i canali. Quando il link D-E cambia il canale da 3 a 7, i link D-F, E-H e H-I necessitano anch’essi di cambiare canale radio al fine di mantenere lo stesso livello di connettività.
Poiché i parametri in base ai quali cambiare il canale tipicamente sono strettamente dipendenti dalle metriche, anche questo tipo di approccio deve poter essere integrato, o collaborare, con il protocollo di routing ed avere un supporto adeguato a livello MAC.
1.6.4 Scelte architetturali
Nella realizzazione di una WMN basata sulle tecniche multi-channel, oltre alle tecniche di assegnazione dei canali esaminate in precedenza, anche le scelte architetturali hanno un impatto sulle prestazioni della rete. Nelle WMN basate su IEEE 802.11, ad esempio, si può scegliere di utilizzare sia gli standard IEEE 802.11b/g sia IEEE 802.11a oppure entrambi.
Un esempio di scelta architetturale in una mesh infrastrutturata è quella di utilizzare 802.11a nella parte di backbone e 802.11b/g nella parte di accesso, come illustrato nella Figura 1.8. La scelta di una determinata configurazione pone quindi dei vincoli, che devono essere tenuti in considerazione nella progettazione del meccanismo di assegnazione dei canali.
51
Figura 1.8: esempio di architettura mesh multi-channel basata su standard IEEE802.11. In questa soluzione i link tra i nodi sono realizzati sul livello fisico di 802.11a mentre la copertura è realizzato con 802.11b/g
In questo scenario ogni mesh router è provvisto di almeno due moduli radio: uno opera sullo standard IEEE 802.11b/g e fornisce la connettività ai mesh client, come dei normali AP; per ridurre l’interferenza, ogni interfaccia di accesso è impostata su un canale diverso. Le altre interfacce, talvolta più di una, operano di modalità IEEE 802.11a, e sono utilizzate per connettersi agli altri mesh router formando una backbone per la comunicazione tra i mesh router. Ciascun link opera su un canale diverso, minimizzando l’interferenza con gli altri link, e il numero di canali utilizzati dipende ovviamente dal numero di interfacce distinte dedicate alla connettività della backbone. Questa soluzione, sebbene sia solo una delle tante possibili configurazioni, è una delle più utilizzate dalle proposte
52
commerciali. Una possibile estensione di questo scenario, tra l’altro riscontrato in alcuni prodotti commerciali, prevede l’utilizzo di tre moduli radio, dove il terzo modulo radio viene utilizzato per distinguere la trasmissione e la ricezione su due canali distinti non interferenti [46]. Una possibile alternativa è ad esempio l’utilizzo, per i link della backbone, di link punto-punto realizzati con tecnologie alternative proprietarie con elevate prestazioni, eventualmente utilizzando antenne altamente direzionali per minimizzare l’interferenza, con notevole incremento delle prestazioni in termini di capacità, a fronte di un calo di flessibilità.
Ogni soluzione offre prestazioni e vantaggi di utilizzo diversi e deve essere scelta in base allo scenario applicativo della WMN.
1.6.5 Prestazioni
Esistono in letteratura scientifica molti studi che analizzano le prestazioni di soluzioni multi-channel / multi-radio. Da un punto di vista generale è dimostrato un aumento delle prestazioni in termini di throughput, ma è difficile quantificare esattamente i vantaggi rispetto alle soluzioni a singolo modulo radio e singolo canale. In particolare l’efficienza nello sfruttare una tale tecnologia dipende, oltre che dai meccanismi di assegnazione dei canali, dalla bontà degli algoritmi di routing nello scegliere i percorsi in modo da sfruttare il vantaggio di avere link non interferenti.
In termini di throughput il guadagno è direttamente proporzionale al numero di moduli radio disponibili per ogni nodo, ma i risultati sperimentali dimostrato che tale relazione è altamente non lineare [5].
53
1.7 Problematiche del livello di trasporto
Il protocollo di trasporto TCP è nato e si è sviluppato per essere utilizzato nelle reti cablate e si è dimostrato non particolarmente adatto all’utilizzo nelle reti wireless.
Innanzitutto il TCP fallisce nelle WMN nell’utilizzare in modo efficiente la banda disponibile. Quando un pacchetto viene perso in un hop intermedio di un path multi-hop, è richiesto che il pacchetto venga ritrasmesso e ripercorra l’intero path anche se è arrivato correttamente fino al nodo precedente, sprecando le risorse del path fino a tale nodo.
Inoltre anche il meccanismo di controllo della congestione non è adatto nelle WMN in quanto il TCP non è in grado di distinguere tra le perdite dovute ad errori sul link e le vere congestioni, quindi riduce erroneamente il rate di trasmissione anche in caso di errori sul link. Nelle reti basate su IEEE 802.11 la percentuale di errori sul link talvolta è notevole e ciò comporta una notevole sottoutilizzazione delle risorse a causa del meccanismo del TCP.
La fairness nel TCP dipende fortemente dal Round Trip Time (RTT) dei flussi. Quando più flussi condividono lo stesso link wireless, il flusso che attraversa un numero inferiore di nodi tende ad acquisire nel tempo una maggiore percentuale di banda, sbilanciando l’equità dei flussi. Pertanto è necessario un modello indipendente dal RTT per raggiungere una vera fairness. I protocolli di livello di trasporto esistenti, inoltre, tendono ad allocare in modo equo la banda disponibile tra i flussi uscenti da un singolo nodo piuttosto che tra tutti i nodi che condividono lo stesso canale radio. Di
54
conseguenza un flusso uscente da un nodo con meno flussi attivi tende ad acquisire più banda di quella prevista nel caso in cui si voglia garantire prestazioni simili a tutti i flussi della rete, ad esempio appartenenti alla stessa categoria di traffico.
Sono state proposte varie alternative all’utilizzo del TCP nelle reti wireless, ad esempio ATP (Ad Hoc Transport Protocol) [29]. Tipicamente queste sono varianti del TCP, nate negli ultimi anni in particolare per le reti ad-hoc e presentano ancora delle inefficienze nelle applicazioni WMN.
1.8 Attività di standardizzazione
Visto il crescente interesse nello sviluppo delle WMN e la nascita nel mondo accademico ed industriale di numerose soluzioni eterogenee e incompatibili, la IEEE ha iniziato un’attività di standardizzazione della tecnologia mesh su vari fronti tecnologici.
La maggior parte dei testbed accademici e prodotti commerciali è basata sullo standard 802.11, e poiché, come visto in precedenza, l’utilizzo di IEEE 802.11 nelle applicazioni WMN presenta numerose problematiche, ogni proposta introduce una serie di meccanismi aggiuntivi per superare tali problemi che comportano un’inevitabile mancanza di interoperabilità tra le varie soluzioni. Uno standard comune in ambito 802.11 è pertanto necessario per assicurare lo sviluppo futuro della tecnologia WMN. Per questo motivo è nato un Task Group in ambito IEEE denominano 802.11s,
