2 Multi-Channel in reti Mesh All’interno di questo capitolo sarà fatta una panoramica delle principali tecniche utilizzate nelle

2 Multi-Channel in reti Mesh

All’interno di questo capitolo sarà fatta una panoramica delle principali tecniche utilizzate nelle WMN per la gestione della comunicazione multi-radio/multi-channel. In particolare, nella sezione iniziale sarà presentata una possibile classificazione degli algoritmi, mentre nella restante parte del capitolo saranno messe in luce le peculiarità e le differenze fra i vari tipi di approcci che sono stati proposti dalla comunità scientifica.

2.1 Introduzione alla comunicazione multi-channel

Come indicato all’interno del capitolo precedente, una delle principali limitazioni riscontrate all’interno di una WMN è la ridotta scalabilità della capacità di rete. Infatti, il throughput di una Wireless Mesh Network in cui la trasmissione avviene su di un singolo canale si riduce non linearmente con il numero di hop che compongono il percorso. Questa degradazione delle prestazioni può essere imputata in primo luogo alla natura statistica del protocollo CSMA/CA, il quale è tipicamente utilizzato come meccanismo di accesso al mezzo in reti 802.11. Aumentando il numero di flussi che attraversano la mesh, si da origine ad un elevato livello di interferenza co-canale e quindi si aumenta significativamente la probabilità di collisione nella comunicazione fra i due estremi del link.

Dal momento che lo standard IEEE 802.11 mette a disposizione rispettivamente 3 e 12 canali non sovrapposti nelle bande non licenziate attorno ai 2.4 GHz e 5 GHz, è stato stimato che un modo naturale per superare i problemi di interferenza tipici di una comunicazione single-channel è rendere in grado i vari nodi della rete di trasmettere su più portanti contemporaneamente. In questo modo si riesce a massimizzare il numero di flussi simultaneamente attivi e quindi a sfruttare efficientemente le risorse radio messe a disposizione dallo standard. Poiché il numero di moduli radio

utilizzabili da un MP è in genere significativamente minore del numero di canali impiegabili, si ha la necessità di definire degli algoritmi che assegnino le portanti frequenziali alle interfacce di ogni mesh router massimizzando una qualche misura di efficienza.

2.2 Classificazione degli algoritmi

Come indicato in [21] è possibile operare una classificazione degli algoritmi di allocazione dei canali in base alla scala temporale su cui viene variato l’assegnamento fra le interfacce radio di un MP e le portanti frequenziali utilizzate per la comunicazione. In particolare, risulta possibile definire tre categorie principali in cui suddividere le varie strategie di “colorazione” dei link della rete:

• Assegnamento statico • Assegnamento dinamico • Assegnamento ibrido

Assegnamento statico

In questo tipo di approccio ciascuna interfaccia utilizzata dai vari mesh router viene assegnata a un dato canale di comunicazione in modo permanente oppure per un lungo intervallo di tempo. Inoltre, le

ulteriori categorie in base al modo in cui i canali vengono distribuiti all’interno della rete:

• Common Channel Approach (CCA): In base a questa metodologia le interfacce di ogni nodo della rete sono assegnate ad un set comune di canali; per esempio se ogni MP presente all’interno della mesh ha a disposizione due moduli radio, le due interfacce sono assegnate alla stessa coppia di canali per ogni nodo della rete. Il principale vantaggio di questo tipo di approccio risiede nel fatto che il grado di connettività della WMN coincide con quello che si avrebbe in una rete single-channel, tuttavia ne deriva un conseguente incremento dell’interferenza co-canale. L’algoritmo CCA sarà utilizzato come termine di paragone all’interno degli studi simulativi che sono stati svolti.

• Varying Channel Approach (VCA): in questo approccio i moduli radio utilizzati da diversi mesh router sono suddivisi in insiemi di canali frequenziali fra loro parzialmente sovrapposti. La maggiore diversità frequenziale assicura una riduzione dell’interferenza sperimentata dai vari nodi, tuttavia si crea la possibilità di un possibile partizionamento della mesh.

Una strategia di assegnamento statico risulta particolarmente vantaggiosa quando i moduli radio sono caratterizzati da un elevato ritardo di commutazione, il quale nelle interfacce di uso comune può variare da centinaia di microsecondi fino ad arrivare a qualche millisecondo; tuttavia tale approccio permette di reagire con minore velocità ad eventuali modifiche della qualità della comunicazione. Di questa categoria di algoritmi fanno parte le soluzioni proposte da Raniwala in [5] e da Marina in [20], le quali verranno esposte all’interno del capitolo.

Asseganamento dinamico

Attraverso una strategia di assegnamento dinamico ciascuna interfaccia risulta in grado di comunicare su ognuno dei canali disponibili al servizio, dal momento che i vari moduli radio vengono commutati frequentemente da una frequenza all’altra. In quest’ottica due nodi che vogliono scambiarsi delle informazioni dati necessitano di un meccanismo di sincronizzazione molto accurato, il quale assicuri che entrambi i mesh router si trovino sullo stesso canale radio in un preciso istante temporale. Inoltre, in tale meccanismo di coordinazione, è imposto che ogni mesh router visiti periodicamente un canale predefinito al fine di ottimizzare la sincronizzazione fra i MP.

Questo tipo di approccio, a cui può essere ricondotto l’algoritmo SSCH (Slotted Seeded Channel Hopping) sviluppato da Bahl in [10], presenta il vantaggio di essere praticamente immune dalla inoperabilità di alcuni canali di comunicazione, ma allo stesso tempo pone dei vincoli molto stringenti per quello che riguarda la sincronizzazione e il ritardo di commutazione fra le varie portanti.

Assegnamento ibrido

Una strategia di assegnamento ibrido combina le peculiarità delle due categorie esposte precedentemente, colorando date interfacce per un lungo periodo di tempo e commutando le restanti in modo dinamico. Un esempio di questo tipo di approccio è rappresentato dalla soluzione proposta da Wu in [8], la quale verrà presentato al termine del capitolo. Le strategie di assegnamento ibride offrono il vantaggio di non richiedere meccanismi di sincronizzazione molto accurati dal momento che, al fine di mantenere coordinazione fra le interfacce che sono commutate su base “pacchetto”, è possibile sfruttare i canali di comunicazione messi a disposizione dai moduli radio statici; tuttavia allo stesso tempo è mantenuta la flessibilità che caratterizza l’assegnamento dinamico.

La figura 2.1 riporta un esempio del funzionamento di una strategia di un algoritmo ibrido, dove ogni mesh router è dotato di un’interfaccia fissa e due sintonizzabili.

Figura 2.1 Esempio di funzionamento di un assegnamento ibrido

Assumiamo ad esempio che il nodo A abbia dati da scambiare con i MP B e C, ed inoltre che le interfacce statiche dei mesh router A, B e C siano assegnate rispettivamente ai canali 1, 2 e 3. Se A ha bisogno di comunicare con B, allora deve commutare la propria interfaccia sintonizzabile sul canale 2, sul quale il nodo B è costantemente in ricezione attraverso il suo modulo radio statico. Allo stesso modo se B dovesse inviare un pacchetto verso A, avrebbe la necessità di accordare uno dei propri moduli radio sintonizzabili sul canale 1, poiché su tale portante il MP A è sempre raggiungibile. In questo modo ognuno dei MP ha solamente l’esigenza di memorizzare in una

2 3 1 1 SWITCHABLE SWITCHABLE FIXED Nodo C FIXED SWITCHABLE SWITCHABLE Nodo A SWITCHABLE FIXED SWITCHABLE Nodo B

propria tabella locale le corrispondenze fra vicini e i canali statici a loro associati.

2.3 Algoritmi Multi-radio/Multi-canale

All’interno di questo paragrafo saranno presentate brevemente le peculiarità dei principali algoritmi per l’assegnamento dei canali che sono stati proposti. Per affrontare tale esemplificazione seguiremo la classificazione introdotta nel paragrafo precedente.

2.3.1 Algoritmi con assegnamento statico

Durante il corso degli anni, la comunità scientifica ha sviluppato numerose soluzioni il cui scopo è “colorare” ognuna delle interfacce disponibili su ciascuno dei mesh router in modo permanente, o su una scala temporale significativamente maggiore del ritardo di commutazione presentato da moduli radio tradizionali. Una soluzione che ha destato un significativo interesse è quella sviluppata da Raniwala in [5] e nota con il nome di Hyacinth. All’interno di tale implementazione ogni Network Interface Card (NIC) disponibile sui vari MP è accordata su un dato canale per un periodo di tempo che risulta dell’ordine dei minuti o delle ore, al fine di garantire stabilità e piena connettività nella WMN.

La figura 2.2 riporta l’archiettura sviluppata per Hyacinth, dove una dorsale formata da mesh router fornisce la connettività ad una serie di client, i quali hanno la possibilità di spostarsi in ogni posizione della rete.

Figura 2.2 Architettura di Hyacinth [5]

Considerando la classificazione introdotta nel Capitolo 1 tale architettura è riconducibile alla classe delle Infrastructure/Backbone WMN.

A titolo di esempio all’interno della figura 2.2 è stato scelto che ogni MP sia dotato di due interfacce radio ed in totale all’interno della rete siano utilizzati cinque canali frequenziali non interferenti.

La principale innovazione introdotta da questa soluzione è la suddivisione delle funzionalità di assegnamento dei canali in due fasi distinte, vale a dire nello stadio di neighbor-to-interface binding e di interface-to-channel binding. Le procedure di neighbor-to-interface binding hanno il compito di individuare quale modulo radio ogni MP deve utilizzare per stabilire il link con il proprio vicino.

Un problema significativo che deve essere affrontato nella definizione delle procedure di assegnamento fra vicini e interfacce è il vincolo della channel-dependency fra i vari nodi che compongono la rete. A causa del numero limitato di moduli radio che si hanno a disposizione, se un mesh router decide di commutare una delle proprie interfacce su di un diverso canale, si da origine ad un meccanismo a catena che porta ad una radicale ridistribuzione dei canali all’interno della WMN. Consideriamo l’esempio di figura 2.3; nel caso in cui D decida di accordare il proprio link D-E su di una diversa portante a causa dell’eccessivo carico sulla frequenza attualmente utilizzata, si crea la necessità di commutare anche il collegamento D-F dal momento che D ha a disposizione solo due NIC per comunicare con i propri vicini. In questo modo si genera un

effetto di ripple che costringe anche E-H e H-I a spostarsi sulla frequenza scelta da D.

Figura 2.3 Problema della channel-dependency in una WMN [5]

Per limitare l’impatto di questo problema è stato deciso di suddividere i moduli radio di ogni mesh router in UP-NIC e DOWN-NIC. Mentre la UP-NIC è utilizzata per connettersi ad un nodo genitore, vale a dire ad un MP che è più vicino al portal di quello attualmente sotto esame, la DOWN-NIC viene impiegata per comunicare con nodi che presentano una distanza maggiore dalla rete esterna. Ciascun MP della WMN è responsabile di colorare le proprie DOWN-NIC, mentre deve accordare le interfacce di tipo up

Il problema della channel-dependency è fortemente limitato dall’imposizione che ogni MP ha la facoltà di commutare solo le proprie interfacce down, mentre non possiede nessun grado di libertà sulle UP-NIC; questa limitazione tende ad eliminare l’effetto di ripple all’interno della rete.

Le tecniche di interface to channel binding hanno il compito di decidere quale canale frequenziale assegnare ad ognuno dei moduli radio di tipo down posseduti dal nodo. Per operare questo tipo di selezione ciascun mesh router ha la necessità di stimare il livello di utilizzazione delle varie portanti nel proprio interference-range mediante tecniche di misure passive oppure inviando attivamente del traffico di probing all’interno della rete.

Uno degli aspetti caratteristici dei meccanismi di distribuzione dei canali all’interno di una WMN è la necessità di mediare fra la volontà di raggiungere una buona diversità frequenziale e la necessità di mantenere una rete non partizionata. Alla luce di questo vincolo il problema del channel assignement può essere inteso come un meccanismo di controllo della topologia della mesh. In letteratura numerose soluzioni, fra le quali anche l’algoritmo CLICA (Connected Low Interference Channel Assignement) proposto da Marina in [20], hanno adottato questo tipo di approccio. L’idea che sta alla base di CLICA è di definire un assegnamento statico fra interfacce e moduli radio di ogni MP della WMN attraverso una

visita ricorsiva dei nodi della rete. In questo lavoro si procede a “colorare” i moduli radio di ogni MP cercando di minimizzare una stima dell’interferenza che si basa sul modello a protocollo [20]. La strategia di assegnamento sviluppata da Marina è di tipo traffic-independent, vale a dire che non è affrontato il problema del diverso grado di carico che i MP devono gestire in base alla loro posizione nella rete. Tipicamente all’interno di una Wireless Mesh Network il traffico genenerato dai client è destinato ad usufruire di risorse che si trovano all’esterno della mesh. Come vedremo, questa semplificazione comporterà una significativa degradazione delle prestazioni rispetto alla nostra implementazione dove è stata presa in considerazione la tipologia del traffico di rete.

La strategia di assegnamento dei canali sviluppato da Marina in [20] è stata utilizzata come base per la definizione del nostro algoritmo ed inoltre sarà impiegata durante le prove simulative come termine di paragone per valutare la bontà della nostra soluzione.

2.3.2 Algoritmi con assegnamento dinamico

All’interno della comunità scientifica sono state proposte numerose soluzioni che tentano di gestire le comunicazioni multi-channel attraverso lo sviluppo di algoritmi dinamici, i quali generalmente

categoria di soluzioni sono i lavori proposti da Jain in [9] e da Bahl in [10]. Questa classe di implementazioni prevede di commutare il canale di comunicazione su base “pacchetto”, necessitando quindi di una sincronizzazione molto accurata fra i mesh router che compongono la rete. In particolare, nella soluzione sviluppata da Bahl e nota con il nome di SSCH, ogni MP è dotato di un solo modulo radio che accorda sui diversi canali resi disponibili al servizio seguendo un ordine ottenuto in base alla relazione (2.1). All’interno della (2.1) xi e ai sono due numeri naturali i quali

indicano rispettivamente il canale di comunicazione utilizzato ed il seme impiegato nella generazione della sequenza pseudo-causale.

(

)

Inoltre, in [10] si ipotizza che dopo un periodo di tempo prefissato ogni nodo dovrà commutare la propria interfaccia all’interno di un canale predefinito al fine di evitare il partizionamento della rete. La base funzionale della soluzione sviluppata da Bahl risiede nel fatto che ogni MP è a conoscenza del piano di scheduling di ognuno dei suoi vicini in modo tale da potersi sincronizzare con un dato MP per poter iniziare una comunicazione dati. Questa necessità è gestita

attraverso l’invio periodico di messaggi di probing che tendono tuttavia ad incrementare l’overhead che transita in rete.

Il principale svantaggio della classe di algoritmi dinamici risiede nel fatto che richiede una sincronizzazione temporale molto accurata fra i mesh router, la quale risulta difficilmente ottenibile attraverso hardware di tipo convenzionale. Inoltre un problema rilevante che non è considerato in questo tipo di soluzioni è il valore assunto dallo switching delay, il quale all’interno di interfacce commerciali risulta non trascurabile rispetto alle altre fonti di ritardo. Ne consegue quindi la necessità di apportare modifiche alla pila protocollare ISO/OSI e principalmente alle funzionalità di livello MAC al fine di introdurre queste funzionalità direttamente all’interno dei driver della schede wireless ed ottenere quindi un significativo miglioramento delle prestazioni.

2.3.3 Algoritmi con assegnamento ibrido

All’interno di questa classe di algoritmi vengono conciliate entrambe le peculiarità delle due categorie esposte precedentemente. La banda disponibile è suddivisa in un canale di controllo sul quale ogni MP si trova costantemente in ascolto, ed in n canali dati D1, D2, … , Dn che

mesh router in modo tale da minimizzare la probabilità di collisione su tali frequenze.

Nella soluzione proposta Wu in [8] ciascun nodo della WMN è dotato di due interfacce radio half-duplex, una delle quali è utilizzata esclusivamente per le comunicazioni sulla frequenza di controllo, mentre la restante è accordata sulle varie portanti D1, …, Dn per la

trasmissione dei frame DATA e dei relativi ACK. Inoltre, ogni MP appartenente alla WMN mantiene due strutture dati, denominate dall’autore Free Channel List (FCL) e Channel Usage List (CUL[]), le quali sono utilizzate rispettivamente per indicare quali canali dati sono disponibili al servizio e per contenere informazioni sulle frequenze attualmente utilizzate per le comunicazioni dei client nell’interference range del nodo sotto esame. Ogni mesh router in base alla propria CUL[] calcola in modo dinamico le portanti utilizzabili per la comunicazione da inserire nella struttura FCL. La base funzionale della soluzione sviluppata in [8] è un handshake del tipo RTS/CTS sul canale di controllo, il quale è riportato graficamente nella figura 2.4. Se il MP X ha dei dati da trasmettere al nodo Y, gli invia sulla portante di controllo un messaggio RTS in cui indica al vicino la propria FCL. In seguito Y confronta la propria lista CUL[] con la FCL ricevuta da X, sceglie un canale dati per la comunicazione e invia questa informazione verso X nel messaggio

CTS, il quale ha anche la finalità di inibire la trasmissione dei vicini di Y sul canale che questo ultimo ha scelto per la comunicazione.

Figura 2.4 Handshake fra i due estremi del link

Il protocollo prevede infine che al momento in cui X riceve il messaggio proveniente da Y trasmetta un pacchetto di RES (Reservation) per indicare ai propri vicini di non iniziare una trasmissione sulla portante su cui intende comunicare con Y. Se il meccanismo di handshaking ha avuto successo, i due nodi inizieranno una comunicazione sul canale dati su cui si sono

Canale di controllo X Canale dati D B RTS S CTS S RES A-B communications NAVCTS NAVRES NAVRTS Y Others

router rilasceranno la risorsa radio occupata riportandosi in ascolto sul canale di controllo.

La soluzione proposta da Wu presenta il vantaggio di sfruttare a pieno le risorse radio messe a disposizione dallo standard e contemporaneamente non necessita di una accurata sincronizzazione fra i MP all’interno della WMN. Tuttavia, a nostro giudizio, il protocollo sviluppato in [8] presenta il problema della formazione di un canale “collo di bottiglia” sulla frequenza di controllo, poiché ogni mesh router dovrà accedere a tale frequenza per iniziare una trasmissione dati; una architettura di questo tipo tenderà inevitabilmente a limitare la scalabilità di una WMN, degradandone significativamente le prestazioni ottenibili in reti di grandi dimensioni.