1 Wireless Mesh Networks In questo capitolo saranno presentate le caratteristiche generali di una

1 Wireless Mesh Networks

In questo capitolo saranno presentate le caratteristiche generali di una Wireless Mesh Network, ne sarà introdotta l’architettura ed i possibili scenari applicativi; discuteremo inoltre le principali differenze con le Wireless Ad Hoc Network. Particolare attenzione sarà posta sulle problematiche di progettazione derivanti dalla natura di una WMN, mentre al termine del capitolo sarà presentato lo stato dei lavori dello standard IEEE 802.11s.

1.1 Aspetti generali

1.1.1 Architettura della rete

Tipicamente i nodi che compongono una Wireless Mesh Network possono essere suddivisi in due categorie: mesh router e mesh client. I mesh router (indicati con l’acronimo MP/MAP/MPP nello standard IEEE 802.11s), oltre che rappresentare i gateway per i pacchetti dati prodotti dai client appartenenti alle proprie LAN, posseggono particolari funzionalità che gli consentono di gestire il mesh networking, in modo tale da essere in grado di inoltrare il traffico destinato a stazioni non appartenenti alla propria rete locale. Per garantire una maggiore flessibilità, un MP può essere dotato di più interfacce radio appartenenti alla stessa oppure a diverse tecnologie wireless. Un nodo della WMN (in questo caso indicato con l’acronimo MPP nello standard IEEE 802.11s) può incorporare anche funzionalità di gateway o di bridge per rendere possibile la comunicazione con reti esterne alla mesh. Nonostante queste numerose differenze, MP e AP tradizionali sono sviluppati su piattaforme hardware simili, vale a dire su sistemi embedded oppure su calcolatori general purpose.

Anche i mesh client possono essere dotati di funzionalità per la gestione del mesh networking e quindi sono in grado di operare come dei router, tuttavia non hanno la facoltà di ricoprire il ruolo di gateway o bridge. Inoltre queste stazioni sono tipicamente dotate di un solo modulo radio ed utilizzano piattaforme hardware e software più semplici rispetto ai mesh router.

Come indicato in [1] e [2], l’architettura di una WMN può essere suddivisa in tre categorie in base alla tipologia e alle funzionalità dei nodi che la compongono:

• Infrastructure/Backbone WMN • Client WMN

• Hybrid WMN Infrastructure/Backbone WMN

All’interno di questa tipologia di rete è possibile isolare due livelli gerarchici in cui suddividere i nodi che compongono la mesh. Al livello più alto si trovano i mesh router, i quali hanno una mobilità limitata e sono incaricati di formare la dorsale per interconnettere fra loro i client presenti all’interno della WMN. In questo caso i mesh router sono dedicati all’inoltro del traffico e non è prevista la possibilità che un mesh router rivesta il ruolo di sorgente o destinazione di dati utente. I MP sono incaricati di gestire i

meccanismi di auto-riconfigurazione e failure-recovery in caso di non operatività di alcuni link, al fine di mantenere sempre presente una percorso verso ogni possibile destinazione. All’interno della rete di backbone è presente almeno un nodo con funzionalità di gateway per permettere alle stazioni client di accedere a reti esterne come Internet. La dorsale può essere costituita da tecnologie eterogenee, quali IEEE 802.11 e IEEE 802.16, interfacciate fra loro tramite appositi gateway posizionati nei punti di accesso alla rete fissa oppure nei mesh router stessi.

Il livello più basso della gerarchia è occupato dai client che rappresentano esclusivamente i punti terminali della comunicazione, i quali sfruttano l’infrastruttura messa a disposizione dai MP per la trasmissione dei propri flussi dati.

Dal punto di vista progettuale in questo tipo di architettura è opportuno pianificare accuratamente il layout della rete, posizionando i MP in siti che massimizzano la capacità e dotandoli di funzionalità aggiuntive come l’utilizzo di antenne direttive per comunicazioni punto-punto.

Questo tipo di architettura è la più diffusa dal momento che presenta contemporaneamente elevate prestazioni e notevole semplicità nelle stazioni client, le quali non devono presentare alcuna funzionalità mesh e possono interfacciarsi direttamente con i MP dotati della stessa tecnologia radio.

La figura 1.1 mostra una Infrastructure/Backbone WMN dove è evidenziata l’organizzazione gerarchica di questo tipo di architettura.

Figura 1.1 Infrastructure/Backbone WMN

Client WMN

Questa tipologia di mesh network è formata da nodi che svolgono contemporaneamente il ruolo di mesh router e di client, dando origine ad una architettura simile ad una rete Ad Hoc multi-hop, dove

non è presente una rete di dorsale comune. In questa modalità una stazione client implementa contemporaneamente le funzionalità di configurazione, di routing e di inoltro del traffico dati, oltre che fornire i servizi applicativi agli utenti finali. All’interno di tale architettura un nodo è tipicamente dotato di un solo modulo radio, ed inoltre è richiesta una notevole crescita della complessità software ed hardware della stazioni, dal momento che ogni client dovrà gestire le funzionalità di networking implementate nei mesh router nella configurazione precedente. Il principale vantaggio di tale soluzione è l’elevata flessibilità richiesta in dati scenari applicativi.

La figura 1.2 mostra l’architettura di una Client WMN.

Figura 1.2 Client WMNs

Hybrid WMN

L’architettura di tipo “ibrido” combina entrambe le caratteristiche dei due modelli esposti in precedenza, poiché i mesh client possono comunicare sfruttando i servizi messi a disposizione dai MP oppure

da altri client. L’utilizzo dell’infrstruttura di backbone permette la connettività con reti esterne di tipo Wi-Fi, WiMAX e sensor network, mentre le funzionalità di routing implementate nei client consentono di migliorare la connettività e la copertura all’interno della WMN. La figura 1.3 mostra l’architettura di una Hybrid WMN dove le linee tratteggiate di colore verde rappresentano la rete di dorsale messa a disposizione della comunicazione fra i mesh router mentre le linee tratteggiate di colore viola hanno lo scopo di rappresentare le funzionalità mesh disponibili all’interno dei client.

Figura 1.3 Hybrid WMN

Wi-Fi, Wi-MAX SensorNetworks, 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

1.1.2 Confronto fra WMN e Wireless Ad Hoc Networks

Fra le principali reti wireless che fanno uso della comunicazione multi-hop è possibile individuare le Wireless Ad Hoc Network, le WMN, le Wireless Sensor Network e le Hybrid Wireless Network. Le Ad Hoc Network sono reti principalmente prive di infrastruttura e con una topologia fortemente dinamica. Le Sensor Network possono utilizzare sia una trasmissione single-hop, sia una comunicazione multi-hop al fine di trasferire dei parametri fisici acquisiti da dei sensori ad un nodo centrale di monitoraggio. Analogamente le Hybrid Wireless Network sono in grado di impiegare tecniche di multi-hop wireless relaying all’interno di reti tradizionalmente single-hop come quelle cellulari.

Le principali differenze fra le Wireless Ad Hoc Network e le WMN si ritrovano nella mobilità dei nodi, nella topologia di rete e nei vincoli sui consumi energetici. Le Ad Hoc Network infatti sono composte da nodi con un elevato grado di mobilità e quindi presentano una topologia fortemente dinamica. Al contrario, all’interno di una WMN, i mesh router sono caratterizzati da una bassa mobilità, determinando quindi una topologia che è di natura prevalentemente statica. Queste sostanziali differenze conducono a differenti prestazioni al variare del protocollo di routing. Mentre i protocolli di routing on-demand mostrano migliori prestazioni all’interno di reti

Ad Hoc, i protocolli di routing di tipo table-driven presentano migliori performance nelle WMN.

Tabella 1 Principali differenza fra le WMN e le Ad Hoc Network [1]

Caratteristica Wireless Ad Hoc

Network

Wireless Mesh Network

Topologia della rete Fortemente dinamica Lentamente

variabile/statica

Mobilità dei nodi Media/Alta Bassa

Vincoli energetici Alto Basso

Caratteristiche

dell’applicazione Temporanea Permanente

Caratteristiche

dell’infrastruttura Senza infrastruttura

Infrastruttura parzialmente o completamente fissa

Relaying Operato dai client Operato dai mesh

router Routing performance Il routing on-demand presenta migliori prestazioni Il routing table-driven presenta migliori prestazioni

Pianificazione Non richiede studi

topologici

Richiede studi topologici

In seguito all’assenza di mobilità dei nodi che la compongono, in una Wireless Mesh Network è rimossa una delle principali limitazioni che si ritrovano nelle Wireless Ad Hoc Network, vale a dire il vincolo sul consumo energetico. I MP, infatti, possono essere connessi alla rete di alimentazione elettrica, mentre i nodi di una rete Ad Hoc devono tipicamente attingere a batterie portatili. La tabella 1 confronta le peculiarità delle Wireless Ad Hoc Network e delle WMN.

1.1.3 Scenari applicativi

La ricerca e lo sviluppo relativo alle Wireless Mesh Network è ampiamente motivato dai numerosi scenari applicativi che difficilmente possono essere gestiti con prestazioni paragonabili attraverso tecnologie diverse, come le reti cellulari, le Ad Hoc network, le wireless sensor network o lo standard IEEE 802.11. Possono essere individuati cinque principali scenari applicativi per le WMN:

• Broadband home networking

• Community and neighborhood networking • Enterprise networking

• Metropolitan area network • Transportation system

Broadband home networking

Attualmente in ambito domestico l’accesso a banda larga a servizi dati è realizzato principalmente attraverso lo standard IEEE 802.11. Un problema che deriva da questo tipo di soluzione è la scelta del posizionamento degli Access Point (AP), dal momento che, senza un’indagine dell’ambiente preso in considerazione, si possono generare delle zone non coperte dal segnale irradiato dall’AP. Inoltre se si considera un’architettura “infrastrutturata” dove gli Access Point sono collegati fra loro attraverso una rete di backhaul cablata (come ad esempio una Ethernet), otteniamo la formazione di un “collo di bottiglia” nel punto di accesso alla rete fissa.

L’utilizzo di una tecnologia basata sul wireless mesh networking risulta una delle soluzioni più valide per la risoluzione di queste problematiche. In tale approccio andremo a sostituire gli AP con dei mesh router tra i quali si stabilisce una connettività mesh, con un conseguente notevole miglioramento della flessibilità e della robustezza dei nodi all’inoperabilità di alcuni link. L’utilizzo di una WMN consente di eliminare il problema della formazione del “collo di bottiglia” nel punto di accesso alla rete di bakhaul ed inoltre riusciamo ad illuminare in modo uniforme tutto l’ambiente preso in considerazione.

La figura 1.4 mostra una soluzione basata sull’utilizzo di una WMN per lo scenario applicativo Broadband home networking.

Figura 1.4 WMN in ambito Broadband home networking [2]

Community and neighborhood networking

All’interno di zone residenziali mediamente dense, la principale architettura per l’accesso a reti esterne come Internet è basata sull’utilizzo della tecnologia DSL. Questo tipo di approccio presenta lo svantaggio di richiedere l’accesso ad Internet anche nel caso in cui si voglia condividere una certa quantità di informazioni all’interno del vicinato; inoltre ogni utente ha a disposizione un unico percorso per comunicare con i vicini oppure accedere a reti esterne.

In questo ambito l’impiego di una WMN è in grado di risolvere i problemi esposti precedentemente attraverso l’utilizzo di una

flessibile connettività mesh fra i MP appartenenti alla zona residenziale; inoltre vengono gestiti in modo più efficiente servizi distribuiti come il file storage ed il video streaming.

Enterprise networking

Attualmente in ambito aziendale la principale soluzione per rendere possibile la condivisione di informazioni all’interno degli uffici e contemporaneamente fornire un punto di accesso alla rete IP esterna è rappresentata dalla creazione di numerose “isole” 802.11, interconnesse fra loro attraverso una infrastruttura cablata. Tuttavia l’utilizzo di una rete fissa di backhaul costituisce uno dei maggiori costi per l’installazione e la manutenzione della rete; inoltre attraverso questo tipo di approccio otteniamo una architettura fortemente sensibile a problemi di congestione e di inoperabilità dei link.

Come mostrato all’interno della figura 1.5, attraverso la tecnologia mesh risulta possibile coprire interamente gli edifici aziendali oppure anche uffici dislocati in palazzi diversi semplicemente installando dei mesh router al posto dei tradizionali AP. In questo modo ogni nodo appartenete alla WMN risulta in grado di usufruire di ognuno dei punti di accesso alla rete esterna, migliorando la robustezza e l’utilizzazione delle risorse presenti all’interno della rete aziendale.

Figura 1.5 WMN per enterprise network [2]

Metropolitan area network

La possibilità di estendere l’impiego delle Wireless Mesh Network anche in ambito metropolitano permette di usufruire di numerosi vantaggi rispetto alle attuali soluzioni outdoor. Tra questi rivestono particolare importanza l’incremento della velocità di trasmissione rispetto alle tradizionali reti cellulari (per esempio lo standard IEEE 802.11a/g prevede che un nodo comunichi ad un bit-rate di 54 Mbps) e l’assenza di una infrastruttura cablata.

Inoltre, se confrontate con le attuali reti utilizzate in ambito MAN (ad esempio le reti ottiche), le WMN costituiscono una alternativa economicamente molto vantaggiosa per la gestione del broadband networking, soprattutto in regioni in via di sviluppo.

Transportation system

Attraverso il mesh networking risulta possibile fornire informazioni real-time all’interno di metropolitane o treni, fornendo ai passeggeri dati sui servizi, informazioni di controllo sulla sicurezza oppure comunicazioni di emergenza, invece di limitare la disponibilità di accesso a servizi dati attraverso le tecnologie IEEE 802.11 ed IEEE 802.16 solamente alle fermate dei trasporti pubblici. Come indicato nella figura 1.6, per rendere possibile tale connettività all’interno di un servizio di trasporto si rende necessaria la disponibilità di una rete di backhaul per l’accesso alla rete IP esterna in grado di gestire una elevata mobilità, ed inoltre una WMN all’interno del veicolo per trasportare le informazioni prodotte dai client.

1.1.4 Caratteristiche di una WMN

Le caratteristiche principali di una WMN che ne influenzano fortemente le prestazioni riguardano aspetti di:

• Tecniche di trasmissione radio • Scalabilità

• Connettività

• Qualità del servizio (QoS) • Compatibilità ed interoperabilità • Sicurezza

• Mobilità

Tecniche di trasmissione radio

Le tecniche di trasmissione radio, grazie ai rapidi progressi ottenuti nel campo dei semiconduttori, delle tecnologie a RF e nella teoria dell’informazione, hanno subito una significativa rivoluzione. Attualmente numerosi approcci sono stati proposti per incrementare la capacità e la flessibilità delle reti wireless. Esempi tipici sono l’utilizzo della tecnologia MIMO, di smart antenna e di sistemi multi-radio/multi-channel.

Inoltre, per incrementare ulteriormente le prestazioni ottenibili in una comunicazione wireless sono state proposte numerose tecniche che

rendono possibile la configurazione del livello fisico dagli strati protocollari superiori. Queste tecnologie radio permetteranno un notevole miglioramento delle prestazioni, ma, allo stesso tempo, richiedono una modifica sostanziale degli altri livelli dello stack ISO/ OSI, specialmente per quello che riguarda i protocolli MAC e di routing. Ad esempio, quando sono utilizzate delle antenne direttive all’interno di reti 802.11, le funzionalità di routing devono necessariamente considerare il settore illuminato dall’antenna. Problematiche analoghe sorgono dall’utilizzo della tecnologia MIMO oppure di sistemi radio riprogrammabili.

Scalabilità

La comunicazione multi-hop è la base del funzionamento delle WMN. Tuttavia uno dei principali problemi del multi-hop networking è dovuto alla scarsa scalabilità presentata da questa soluzione, dal momento che, quando le dimensioni della rete crescono in modo significativo, si ottiene una brusca degradazione delle prestazioni. Infatti i protocolli di routing hanno difficoltà sempre maggiori, al crescere della rete, a trovare il percorso migliore tra due nodi della WMN, le funzionalità del livello di trasporto soffrono della perdita frequente della connettività, e i protocolli MAC sperimentano una significativa riduzione del throughput.

All’interno di una WMN, a causa della sua natura Ad Hoc, risultano di difficile implementazione tecnologie di accesso al mezzo di tipo centralizzato, quali ad esempio le tecniche TDMA o CDMA, dal momento che queste ultime richiedono una precisa sincronizzazione temporale e presentano un elevata complessità. Quindi i protocolli MAC di tipo distribuito, come il CSMA/CA, sono ancora i più diffusi, nonostante soffrano di problemi di scalabilità in seguito al meccanismo di accesso a contesa. Al fine di migliorare tali caratteristiche, la ricerca si sta occupando sempre con maggiore attenzione dello sviluppo di schemi di accesso al mezzo di tipo ibrido, basati su CSMA/CA e TDMA o CDMA.

Connettività

Molti dei vantaggi resi disponibili della tecnologia WMN si possono ritrovare nell’elevato grado di connettività presentato dalla rete, il quale può essere sfruttato per garantire un’elevata flessibilità e robustezza in caso di malfunzionamento di nodi o link della mesh. Per sfruttare le potenzialità messe a disposizione dalla tecnologia di rete ed incrementare significativamente le prestazioni è opportuno utilizzare algoritmi di auto-configurazione e controllo della topologia, tuttavia tali funzionalità richiedono una progettazione accurata di tutto lo stack protocollare.

Qualità del Servizio

A differenza dei tradizionali servizi offerti all’interno delle reti Ad Hoc, la maggioranza delle applicazioni disponibili in una WMN necessitano di un elevato bit-rate e differenti livelli di QoS. Si crea quindi la necessità di utilizzare metriche più evolute rispetto a quelle tradizionalmente utilizzate all’interno di reti wireless, come ad esempio il numero di hop da sorgente a destinazione. Come sarà più chiaro in seguito, la ricerca si sta attualmente concentrando sulle performance ottenibili attraverso l’impiego di nuove metriche, le quali, tenendo in considerazione grandezze come il delay jitter o il packet-loss-ratio, risultano in grado di migliorare significativamente le prestazioni percepite dall’utente finale.

Compatibilità ed interoperabilità

Una delle caratteristiche che una WMN dovrebbe presentare è il supporto contemporaneo sia di nodi convenzionali, sia di mesh client. Al fine di presentare questa funzionalità una Wireless Mesh Network deve risultare compatibile con gli standard precedentemente definiti, altrimenti le motivazioni che si trovano alla base dello sviluppo delle WMN sarebbero fortemente compromesse. L’integrazione di una Mesh Network con altre reti wireless richiede che alcuni mesh router presentino la possibilità di interfacciarsi con wireless network di natura eterogenea. Ad esempio

una WMN basata su tecnologia 802.11 deve garantire, in un’ottica di convergenza delle diverse tipologie di rete, l’interoperabilità con la tecnologia Wi-MAX, ZigBee o UMTS/HSDPA.

Sicurezza

La disponibilità di soluzioni in grado di garantire un elevato grado di sicurezza risulta essere una delle caratteristiche chiave per una larga diffusione di una tecnologia di rete, soprattutto nelle comunicazioni wireless.

Nonostante siano state proposte numerose architetture per il sopporto della sicurezza all’interno della tecnologia WLAN, nessuna risulta adatta all’impiego all’interno di una mesh network dal momento che l’architettura distribuita di una WMN non supporta in modo naturale la definizione di un server centrale per la distribuzione delle chiavi pubbliche. In conseguenza di ciò si crea la necessità di stabilire nuovi schemi per il supporto della sicurezza adatti all’utilizzo all’interno di una WMN. In particolare dovranno essere definiti algoritmi di cifratura più efficienti, meccanismi di distribuzioni delle chiavi più affidabili, Intrusion Detection System (IDS) conformi alla natura architetturale di una Wireless Mesh Network e contemporaneamente risulterà necessaria una ridefinizione dettagliata dei protocolli di routing e di livello MAC.

Mobilità

La mobilità degli utenti è uno dei requisiti fondamentali che una rete wireless ha il vincolo di gestire pienamente. Da un punto di vista teorico un mesh client deve avere la possibilità di spostarsi in qualsiasi punto della WMN, mantenendo pienamente la connettività e un adeguato livello di qualità del servizio. Il problema della mobilità è uno dei più difficili da affrontare dal punto di vista progettuale poiché dipende fortemente sia dalla natura architteurale della rete, sia dal protocollo di routing utilizzato. Sono attualmente in fase di studio varie soluzioni a questo problema, le quali cercano di sfruttare le funzionalità di inoltro dei pacchetti in base ad un etichetta tipiche della tecnologia MPLS, e contemporaneamente le peculiarità del protocollo Mobile IP.

1.1.5 Capacità di una WMN

Una delle limitazioni più importanti che si riscontrano nelle prestazioni presentate da una WMN è dovuta alla ridotta scalabilità della capacità di rete. Contrariamente al valore assunto dal limite teorico del throughput per nodo, il quale tende asintoticamente a

( )

n

O 1 , dove n è il numero dei nodi presenti nella rete, è stato stimato in [3] che la capacità teoricamente ottenibile da ciascun nodo in una Random Static Wireless Ad Hoc Network è asintoticamente

limitata da O

(

1 nlogn

)

. Inoltre, considerando dei reali protocolli di routing, di trasporto e MAC, la reale capacità ottenibile all’interno di una WMN è significativamente minore della metà del valore ottenuto in modo analitico. E’ stato successivamente stimato attraverso studi sperimentali volti ad indagare le peculiarità del protocollo CSMA/CA [4], che solamente in una topologia lineare il throughput decresce approssimativamente come

1

n

della banda del canale, mentre in un a configurazione arbitraria la capacità ottenibile all’interno di una WMN è proporzionale a O

(

W_×n−1d

)

_{, dove W è la} banda totale e d è la dimensione della rete. Ad esempio in una configurazione planare il throughput ha un andamento del tipo

(

_{× d}−12

)

W

O .

Uno dei possibili approcci per incrementare significativamente la capacità di rete è utilizzare più moduli radio sullo stesso nodo, rendendo il mesh router capace di comunicare simultaneamente su più canali frequenziali. La recente diffusione di tecniche multi-channel è stata fortemente incoraggiata anche dalla attuale disponibilità di interfacce radio a costo limitato, rendendo così i prodotti che sfruttano tale tecnologia accessibili ad un prezzo contenuto. In tale ottica all’interno di questo lavoro di tesi ci siamo prefissi lo scopo di indagare il reale incremento della capacità di rete

ottenuto attraverso l’utilizzo di comunicazioni multi-channel/multi-radio.

1.2 Routing nelle reti mesh

La scelta e l’implementazione di una data tipologia di protocolli di routing influenza fortemente le prestazioni riscontrate all’interno della rete, specialmente in uno scenario multi-hop come quello che caratterizza una Wireless Mesh Network. Tipicamente le funzionalità di routing utilizzate all’interno delle WMN sono ottenute come rivisitazioni dei protocolli definiti per le Wireless Ad Hoc Network, ai quali vengono apportate opportune modifiche per considerare le diverse caratteristiche dei nodi presenti all’interno della rete, in particolare la natura statica dei mesh router e il mancato vincolo sul consumo energetico dei MP appartenenti alla WMN.

Uno degli aspetti centrali che caratterizzano significativamente le performance di un protocollo di routing è la metrica associata ad ogni link, vale a dire la funzione costo utilizzata per scegliere il percorso che da una sorgente conduce ad una determinata destinazione. Le metriche, come quella hop count, che tipicamente vengono utilizzate all’interno delle reti cablate presentano basse prestazioni se impiegate nelle WMN dal momento che non tengono conto della natura broadcast del mezzo di propagazione wireless.

All’interno di questo paragrafo sarà fatta una classificazione della tipologia dei principali protocolli di routing utilizzabili all’interno delle WMN e successivamente saranno introdotte le principali metriche che riescono a rappresentare meglio gli aspetti significativi di una comunicazione wireless.

1.2.1 Classificazione dei protocolli di routing

Una possibile classificazione dei protocolli di routing può essere realizzata in base alla modalità con cui sono ottenute e mantenute le informazioni di raggiungibilità delle destinazioni presenti all’interno della rete. In quest’ottica è possibile isolare tre principali categorie:

• protocolli di routing table-driven • protocolli di routing on-demand • protocolli di routing ibridi Protocolli di routing table-driven

All’interno di questa categoria ogni mesh router scambia periodicamente con gli altri nodi della rete messaggi di raggiungibilità e mantiene tali informazioni all’interno della propria tabella di routing. Questa tipologia di protocolli presenta buone prestazioni quando il traffico presente nella WMN è tipicamente

destinato o proveniente da reti esterne, vale a dire nel caso in cui la maggior parte delle connessioni dei MP vengono stabilite con i gateway della mesh. I principali protocolli che fanno parte della categoria table-driven sono DSDV e OLSR.

Protocolli di routing on-demand

All’interno della famiglia dei protocolli di tipo reactive un nodo trasmette informazioni di routing solamente al momento in cui ha la necessità di comunicare con una data destinazione. In questo modo si riduce il traffico di controllo che circola nella rete, ma allo stesso tempo si incrementa il ritardo sul primo pacchetto dati inviato dalla sorgente. Tipici esempi di questo approccio sono AODV e DSR.

Protocolli di routing ibridi

I protocolli di routing di tipo ibrido combinano le peculiarità di entrambe le categorie esposte precedentemente, dal momento che costruiscono un albero di instradamento che da ogni nodo della mesh conduce tipicamente al portal della rete, ma allo stesso tempo danno origine a route on-demand quando un MP ha la necessità di comunicare con un altro nodo appartenente alla mesh. Uno dei principali esponenti di questa famiglia è il protocollo HWMP, il quale è demandato come mandatario all’interno della

standardizzazione IEEE 802.11s ed è stato oggetto di un precedente lavoro di tesi svolto presso il nostro gruppo di ricerca.

1.2.2 Metriche di routing

Per assicurare un utilizzo efficiente delle risorse di rete, il percorso a costo minimo deve garantire buone prestazioni in termini di throughput e ritardo end-to-end. Al fine di ottenere tali caratteristiche, le metriche di routing devono essere in grado di rappresentare le caratteristiche della WMN che influenzano le prestazioni del sistema. All’interno di questo paragrafo sarà fatta una veloce panoramica delle principali metriche che sono state definite per riprodurre le peculiarità di una comunicazione wireless.

Expected Transmission Count (ETX)

La metrica ETX, proposta da De Couto in [15], è definita come il numero di trasmissioni, comprese le ritrasmissioni, necessarie a livello MAC per inoltrare con successo un pacchetto all’interno del canale wireless. La metrica ETX è espressa dal punto di vista analitico dalla relazione (1.1), dove Pf e Pr rappresentano rispettivamente la probabilità di perdita nelle due direzioni della comunicazione. Il costo associato all’intero path è ottenuto come la somma dei pesi associati ad ognuno dei link attraversato dal flusso dati.

r f

P

P

ETX

×

=

1

(1.1)

ETX risulta in grado di rappresentare contemporaneamente sia l’effetto prodotto dalla lunghezza del percorso, sia dalla probabilità di perdita nelle due direzioni della comunicazione, tuttavia trascura completamente l’effetto della intra-flow interference, della inter-flow interference e il fatto che le varie sorgenti possano comunicare ad una diversa velocità trasmissiva.

Expected Trasmission Time (ETT)

La metrica ETT, definita da Draves in [16], si propone di migliorare le prestazioni ottenute tramite ETX considerando nel costo associato al percorso anche la velocità trasmissiva delle varie sorgenti. In base a ETT il peso associato al collegamento radio è definito come la quantità di tempo necessaria per inoltrare con successo un pacchetto a livello MAC. Dal punto di vista analitico il costo ETTi del link i è espresso dalla relazione (1.2)

i i i B s ETX ETT = × (1.2)

rispecchia l’impatto della capacità del link sulle prestazioni del percorso, tuttavia trascura completamente l’effetto dell’interferenza prodotta all’interno della rete. Per esempio in base a ETT il protocollo di routing potrebbe scegliere una percorso che utilizza un solo canale invece che optare per un path caratterizzato da una maggiore diversità frequenziale e quindi da un throughput più elevato.

Weighted Cumulative ETT (WCETT)

La metrica WCETT, definita da Draves in [16], si propone l’obbiettivo di ridurre il numero di nodi lungo il percorso che trasmettono sullo stesso canale frequenziale, tenendo quindi in considerazione il problema della intra-flow interference. Da un punto di vista analitico, per il percorso p, WCETT è definita dalla relazione (1.3), dove β è un parametro variabile compreso nell’intervallo [0,1].

( ) (

)

_j k j p i link ETTi X p WCETT ≤ ≤ ∈ + − =

∑

1 max 1

β

β

(1.3)

Il termine Xj rappresenta il numero di hop di p sul canale j. Il secondo addendo della (1.3) rappresenta l’effetto della intra-flow interference dal momento che essenzialmente assegna un costo basso ai percorsi che hanno una maggiore diversità frequenziale.

I principali svantaggi dell’utilizzo della WCETT si ritrovano nella mancata considerazione della inter-flow interference e nel fatto che tale metrica di routing non presenta la proprietà di isotonicità (si consideri [14] per una dimostrazione). Una metrica è isotonica se aggiungendo lo stesso link a due diversi percorsi da un nodo sorgente verso una data destinazione si mantengono le stesse relazioni di disuguaglianza che si avevano prima di considerare questo ulteriore collegamento. L’assenza di tale proprietà determina il fatto che non esistono degli algoritmi efficienti per il calcolo del costo del percorso, in particolari gli algoritmi link-state possono produrre dei cicli di routing all’interno della rete.

Metric of Interference and Channel-switching (MIC)

La metrica MIC, proposta da Yang in [14], si propone l’obbiettivo di sviluppare ulteriormente WCETT andando a risolvere i problemi di non isotonicità e di inabilità a considerare la inter-flow interference. La metrica MIC per il percorso p è definita nella relazione (1.4), dove N è il numero totale di nodi nella rete e min(ETT) è il più piccolo valore di ETT sperimentato all’interno della mesh.

( )

₍

_)∑

∈

+

_∑

∈

×

=

_{linki p}

IRU

_{i nodej p}

CSC

_j

ETT

N

p

MIC

min

1

(1.4)

I due addendi che compongono la metrica MIC, IRU (Interference-aware Resource Usage) e CSC (Channel Switching Cost) sono definiti rispettivamente in (1.5) e (1.6), dove Ni sono i vicini del nodo i che appartengono al suo interference range, CH(i) rappresenta il canale assegnato al nodo i, mentre prev(i) indica il nodo precedente di i sul percorso p. i i i ETT N IRU = × (1.5)

(

( )

)

( )

( )

(

)

( )







=

≠

=

i

CH

i

prev

CH

se

w

i

CH

i

prev

CH

se

w

CSC

_j 2 1 (1.6) 2 1

0

≤

w

<

w

Dal punto di vista fisico IRUi rappresenta il tempo in cui il canale risulta occupato per i vicini del nodo sotto esame in seguito ad una sua trasmissione sul link i. Questo termine rappresenta la inter-flow interference dal momento che favorisce i percorsi che consumano una aliquota minore del tempo di trasmissione ai nodi vicini. CSCj considera invece la intra-flow interference dal momento che associa ai percorsi con link consecutivi accordati sullo stesso canale un costo maggiore rispetto a quello ottenuto in percorsi con una più elevata diversità frequenziale.

1.3 Progettazione Cross-layer

Tradizionalmente, protocolli appartenenti a livelli diversi dell’architettura OSI risultano trasparenti l’uno all’altro. Questo tipo di approccio rende il processo di sviluppo ed implementazione di tali funzionalità più semplice e scalabile. Tuttavia la metodologia della stratificazione non conduce necessariamente ad ottime soluzioni, soprattutto in reti wireless. Per esempio il canale di propagazione risulta variabile in termini di capacità, bit error rate, ecc. Nonostante possano essere utilizzati differenti schemi di codifica e modulazione, non è possibile garantire una banda costante oppure ritardi approssimativamente costanti. Ne consegue una inevitabile ripercussione sulle prestazioni del sistema a causa della natura non ideale del canale wireless.

Al fine di ottenere una qualità percepita soddisfacente è necessario che i protocolli dei vari strati dell’architettura OSI interagiscano. Ad esempio, all’interno delle WMN le funzionalità di livello MAC possono includere meccanismi per il controllo della topologia e di auto-configurazione. Tali informazioni devono essere rese disponibili al protocollo di routing che in questo modo sarà in grado di ottenere dei percorsi a più elevate prestazioni.

La progettazione cross-layer, rendendo disponibili parametri che tipicamente sono utilizzati dai livelli protocollari sottostanti a quello

preso in considerazione, risulta in grado di migliorare significativamente le prestazioni dei vari livelli architetturali. In quest’ottica la probabilità di perdita dei pacchetti ottenuta dal meccanismo di accesso al mezzo può essere riportato al protocollo di trasporto TCP che quindi riesce a distinguere una reale condizione di congestione da una situazione di perdita momentanea. Allo stesso modo le funzionalità di livello fisico possono fornire al protocollo di routing dei parametri riguardanti la qualità del canale di comunicazione in maniera tale che queste informazioni possano essere utilizzate nella scelta dei percorsi ottimi all’interno della mesh. Un’ulteriore modalità con cui può essere realizzata una progettazione cross-layer è la fusione in un unico blocco di più componenti protocollari. Ad esempio le funzionalità di livello MAC e di routing possono essere combinate al fine di considerare più strettamente la loro interazione. Il vantaggio di questo secondo approccio è rappresentato dalla possibilità di ottenere migliori prestazioni rispetto alla prima modalità presentata, ma tuttavia si ottiene una significativa crescita della complessità del sistema dal momento che viene persa completamente la trasparenza e la stratificazione fra i vari livelli protocollari.

In entrambi i casi la progettazione cross-layer può comportare notevoli difficoltà derivanti dalla possibile incompatibilità con

protocolli esistenti e dalla minore flessibilità di controllo e gestione del sistema.

1.4 Attività di standardizzazione

La notevole attività di ricerca sulle WMN svolta sia nel mondo accademico, sia in quello industriale, ha portato allo sviluppo di numerose soluzioni proprietarie fra loro non interoperabili; attualmente i maggiori produttori stanno già commercializzando i primi prodotti che si basano sul mesh networking. In quest’ambito i principali enti di standardizzazione come IEEE hanno sentito la necessità di formare dei gruppi di lavoro che portino alla stesura di standard comuni al fine di gettare le basi per la definizione di soluzioni con un elevato grado di compatibilità.

Attualmente la quasi totalità dei test-bed che si sono sviluppati nella comunità scientifica e industriale riguardano lo standard 802.11; visti i numerosi problemi di scalabilità presentati dall’estensione di tale tecnologia ad una comunicazione multi-hop, ogni costruttore si trova costretto a sviluppare soluzioni proprietarie che inevitabilmente sono fra loro non compatibili. Al fine di risolvere questo problema in ambito IEEE è stato formato il Task Group 802.11s, al quale è demandato il compito di potenziare il livello MAC dell’architettura protocollare. Le nuove funzionalità introdotte consentono di gestire

le procedure di routing e di inoltro del traffico all’interno della WMN completamente a livello Data link, rendendo quindi trasparante la reale topologia della mesh ai livelli protocollari superiori, i quali considerano la WMN essenzialmente come una tradizionale rete Ethernet. Inoltre al fine di ottenere un IEEE 802.11 Wireless Distribution System (WDS) capace di supportare efficientemente sia le trasmissioni broadcast/multicast sia le comunicazioni unicast è stato previsto l’utilizzo di metriche di routing radio-aware e di topologie multi-hop auto-configuranti.

Oltre che nella tecnologia 802.11, la ricerca sulle WMN si sta sviluppando anche in altre tipologie di rete, quali ad esempio la famiglia IEEE 802.15 e IEEE 802.16. Tuttavia, vista la nascita più recente di tali standardizzazioni, lo stato della ricerca sul mesh networking risulta ancora ad uno stato iniziale.