2. Lo standard IEEE 802.11s

57

2. Lo standard IEEE 802.11s

2.1 Introduzione: stato dei lavori e obiettivi

La IEEE nel maggio 2004 ha costituito un Task Group chiamato “IEEE 802.11s ESS Mesh” sotto il Working Group 802.11, con l’obiettivo di creare un framework standard per lo sviluppo della tecnologia WMN nelle Wireless LAN 802.11. Il Task Group, spesso riferito con la sigla “TGs”, ha indetto le consultazioni per la raccolta di proposte da utilizzare come base del processo di standardizzazione; da tali consultazioni sono emerse una decina di proposte, di cui le due principali, sostenute da due gruppi di aziende leader del mondo delle telecomunicazioni, sono denominate SEE-Mesh e Wi-Mesh. Nel marzo 2006 è stato redatto il primo documento ufficiale da cui è partito l’attuale processo di standardizzazione:

58

il documento si chiama “Joint SEE-Mesh/Wi-Mesh Proposal to 802.11

TGs” [32] e nasce, appunto, dall’unione delle due principali proposte,

SEE-Mesh e Wi-SEE-Mesh. Il documento si propone come una soluzione completa che copre tutti i requisiti di funzionalità minimi per la realizzazione di una rete WLAN mesh basata su standard IEEE 802.11, flessibile ed autoconfigurante, mirata a reti non amministrate, come ad esempio reti medio-piccole che non necessitino di una configurazione completa da parte di un service provider.

L’obiettivo dichiarato è quello di definire un framework flessibile che supporti le applicazioni più comuni delle WMN ma che allo stesso tempo fornisca la possibilità di definire protocolli e meccanismi alternativi e proprietari ottimizzati allo scenario applicativo, garantendo allo stesso tempo l’interoperabilità tra le soluzioni commerciali e facilitando eventuali sviluppi futuri.

Vengono introdotti una serie di nuovi meccanismi per l’installazione, la configurazione e l’operatività di una WLAN mesh. Tali meccanismi si collocano a livello MAC dello standard IEEE 802.11 e possono essere implementati sul livello fisico di tutta la famiglia degli standard, IEEE 802.11a/b/g/n. La proposta introduce un’estensione per quanto riguarda la formazione della topologia, per rendere la WLAN mesh autoconfigurabile, dinamica e di facile impiego. La principale caratteristica che contraddistingue l’approccio proposto dal TGs dai comuni sistemi WMN è l’introduzione di un meccanismo di forwarding e instradamento completamente a livello MAC, piuttosto che a livello di rete, realizzando, di fatto, un routing a livello 2; tale meccanismo è denominato HWMP (Hybrid

59

una soluzione mandataria mirata a garantire l’interoperabilità, e che altri tipi di soluzioni possono essere impiegate. Lo standard prevede il supporto delle comunicazioni di tipo broadcast e multicast oltre a quelle unicast. Inoltre definisce dei meccanismi di base per sfruttare le tecniche multi-channel, sia nel caso di dispositivi con singolo modulo radio che con più moduli radio. Gli obiettivi delle specifiche presentate nel documento sono:

• Incrementare il raggio di copertura e la flessibilità d’uso (rispetto alle normali soluzioni WLAN)

• Prestazioni affidabili • Sicurezza

• Supporto alle comunicazioni multimediali tra i dispositivi • Efficienza energetica per dispositivi con limiti di consumo • Compatibilità con gli standard precedenti

• Assicurare l’interoperabilità per il networking • Possibilità di incrementare il throughput

Nella Figura 2.1 viene illustrato in uno schema stratificato l’insieme delle funzionalità logiche del livello MAC introdotte dallo standard.

60

LAN metaphor, 802.1 bridging support

Legacy 802.11 a/b/g/n 802.11i link security based Mesh Measurement Mesh Topology

Learnigng Routing & Forwarding

Mesh Internetworking with other 802 networks

Medium Access Coordination Mesh Security

802.11 service

integration Mesh Configuration & Management PHYs Single-hop/multi-hop neighbor discovery Extensible path selection & forwarding MAC enhancements Unmanaged automatic management Discovery & Association

Figura 2.1: struttura logica delle funzionalità definite dallo standard IEEE 802.11s

Nell’ultimo anno il TGs ha redatto nuovi documenti, di difficile reperibilità, che modificano sostanzialmente molti dei meccanismi della proposta iniziale. Pur mantenendo inalterati gli obiettivi, il formato dei frame, il protocollo di routing HWMP e i meccanismi di controllo e gestione sono cambiati notevolmente. Non disponendo di nessun Draft completo ufficiale, a parte il documento della proposta iniziale, sono state

61

reperite in rete alcune “redline” [33], ovvero documenti ufficiali che riportano solo le differenze rispetto alle versioni precedenti delle decisioni prese nei vari incontri del TGs. Da tali documenti sono stati estratti gran parte degli argomenti di interesse di questa tesi. Alcune “redline” sono molto esaustive in quanto apportano modifiche di parti complete riguardo ai meccanismi di interesse, come ad esempio il protocollo HWMP.

Tuttavia il processo di standardizzazione è ancora nelle fasi iniziali, e attualmente non è ancora stato approvato il Draft 1.0. Ciò rende difficoltoso avere una visione esaustiva e certa di ciò che sarà lo standard effettivo, la cui ratifica è prevista, nel migliore dei casi, per fine 2008.

2.1.1 Outline dello standard

Lo standard descrive un framework completo per la realizzazione di una rete mesh con tecnologia IEEE 802.11 affrontando una vasta serie di problematiche. Innanzitutto definisce l’architettura e gli elementi base della rete. Specifica come realizzare il supporto alle tecniche multi-channel e come gestire l’interconnessione alle altre reti. Una sezione sostanziosa è dedicata alla descrizione dettagliata del formato dei frame, sia quelli nuovi introdotti per la gestione dei servizi mesh, sia le modifiche apportate ai tipi di frame già esistenti, come ad esempio i beacon.

Vengono poi descritti i servizi mesh. I principali sono:

• La scoperta dei nodi, la formazione e il mantenimento della topologia: comprende la descrizione di come viene automatizzata la creazione

62

della rete, la gestione dei link, la gestione dei canali negli scenari multi-channel, le procedure di attivazione di un nodo

• Il meccanismo di selezione dei path d’inoltro e il forwarding: descrive il protocollo di routing HWMP, le metriche utilizzate ed il modo in cui vengono inoltrati i dati

• La gestione della sicurezza

• L’ottimizzazione dei parametri del meccanismo di accesso al mezzo, EDCA, introdotto nello standard IEEE 802.11e

• Il meccanismo di Congestion Control all’interno della rete mesh

• Common Channel Framework (CCF), un meccanismo opzionale per

la gestione del multi-channel integrato nel livello MAC

• Mesh Deterministic Access (MDA), uno schema opzionale di

miglioramento al meccanismo di accesso al mezzo

• La descrizione del supporto all’internetworking, che descrive i modi per interfacciarsi con le reti esterne e l’utilizzo delle VLAN all’interno della mesh.

• Mesh Beaconing e Syncronization, descrive le procedure di

sincronizzazione tra i nodi della rete mesh

• Power Management, ovvero gestione del controllo delle risorse energetiche, ottimizzata per lo senario mesh

Il resto del capitolo si concentra in particolare sugli aspetti topologici e di routing; verranno fatti cenni ai meccanismi di miglioramento del livello MAC ed altri aspetti, come la sicurezza, verranno totalmente tralasciati.

63

2.2 Overview delle WLAN Mesh

In questo paragrafo verranno analizzate le principali caratteristiche della rete Mesh concepita dallo standard.

2.2.1 Componenti dell’architettura

Nella maggior parte delle applicazioni WLAN 802.11, c’è una chiara distinzione tra i dispositivi che costituiscono l’infrastruttura di rete e i dispositivi che semplicemente utilizzano l’infrastruttura per ottenere l’accesso alle risorse di rete. Le più comuni infrastrutture WLAN al momento sono costituite da Access Point (AP) 802.11 che forniscono un certo numero di servizi, come l’accesso alla rete e servizi di autenticazione e management. Gli AP tipicamente sono direttamente connessi a una rete cablata, ad esempio di tipo Ethernet, e semplicemente forniscono connettività ai dispositivi client piuttosto che utilizzare la connettività wireless per comunicare tra loro. I client del resto, sono tipicamente semplici stazioni (STA) 802.11 che devono associarsi con un AP per ottenere l’accesso alla rete. Tali stazioni dipendono in tutto e per tutto dagli AP a cui sono associate. Il modello di sviluppo tipico di queste WLAN è illustrato nella Figura 2.2

64

Figura 2.2: architettura classica di una WLAN

In una rete mesh, il DS (Distribution System), tipicamente cablato, viene realizzato facendo in modo che gli AP comunichino direttamente tra loro su link wireless, fornendo una rete magliata (mesh) per il trasporto delle informazioni tra i nodi in modalità multi-hop (WDS, Wireless

Distribution System). I dispositivi tradizionalmente classificati come client,

a loro volta possono beneficiare della possibilità di stabilire una connessione peer-to-peer wireless con gli altri client vicini o gli altri AP diversi da quello a cui sono associati. A loro volta, tali client evoluti, possono fornire gli stessi servizi degli AP, aiutando le stazioni tradizionali (individuate con l’acronimo STA nello standard IEEE 802.11) ad accedere alla rete. In questo scenario si perde la tradizionale distinzione tra i ruoli nettamente separati tra dispositivi client e quelli dell’infrastruttura.

65

Lo standard distingue i dispositivi wireless in due categorie: nodi mesh, che sono dispositivi capaci di supportare servizi di tipo mesh, e nodi che non supportano i servizi mesh, come le tradizionali stazioni 802.11. I nodi mesh inoltre possono in modo opzionale supportare i servizi di accesso degli AP.

I servizi mesh sono implementati come un’interfaccia logica MAC, che è indipendente dal tradizionale MAC 802.11. Quindi, in sostanza, un singolo dispositivo può avere sia il ruolo di AP sia il ruolo di nodo mesh, oppure di nodo mesh e di stazione standard.

Un esempio di rete Mesh è illustrata nella Figura 2.3.

MP AP MP AP MP MP Portal MP Portal MP MP AP MP AP STA _STA STA _STA Rete cablata

Mesh Point

Mesh AP

Stazioni

Mesh Portal

Figura 2.3: architettura e componenti di una wireless mesh network secondo lo standard IEEE 802.11s

I Mesh Point (MP) sono entità che supportano i servizi mesh, che partecipano nella formazione e all’operatività della rete mesh. Un MP può

66

essere sia un dispositivo dedicato di una certa infrastruttura, o un dispositivo end-user capace di partecipare completamente alla formazione e alle operazioni della rete mesh. I nodi che forniscono i servizi di AP in modo aggiuntivo a quelli di un MP sono chiamati Mesh Access Point (MAP). Le stazioni standard si connetto ai MAP per ottenere l’accesso alla rete e non partecipano alla fornitura dei servizi mesh, come ad esempio il meccanismo routing. La Figura 2.4 illustra graficamente la suddivisione funzionale delle tre tipologie di dispositivi.

Inoltre nella rete mesh spesso è presente un nodo che fornisce la connettività verso reti esterne, chiamato Mesh Point Portal (MPP). Questo nodo integra sia le funzionalità di un MP sia quelle di un Portal. Le funzionalità di Portal sono mirate alla possibilità di interoperare a livello data link con un segmento di LAN 802, realizzando tutte le funzionalità di un bridge, compresa l’implementazione dello STP (Spanning Tree Protocol) sulla LAN. Su tale LAN, a sua volta, può essere presente un Router (livello tre) per la connessione con reti esterne, o eventualmente un altro MPP che connette alla LAN un'altra rete Wireless mesh.

67

802.11

Mesh Point Mesh Access Point Access Point normali stazioni 802.11

Mesh Point Mesh Access

Point

Access Point

Figura 2.4: suddivisione funzionale dei componenti di un’architettura mesh basata su standard IEEE 802.11s

I mesh point possono operare a diversi livelli di funzionalità. Non tutti i MP devono utilizzare tutti i servizi di tipo mesh. Servizi come il routing possono essere utilizzati in modo parziale o addirittura non impiegati. Lo standard, infatti, prevede l’esistenza di particolari tipi di MP che implementano funzionalità mesh minime. In particolare possono non far parte del Distribution System (DS) e non implementare le funzionalità di routing. In questo modo sono capaci solo di comunicare con i nodi vicini.

2.2.2 Modello protocollare

La rete mesh è in sostanza una rete LAN IEEE 802 composta di link IEEE 802.11. In effetti, questo significa che la rete mesh è funzionalmente equivalente ad una rete Ethernet vista dalla prospettiva delle altre reti e dei livelli protocollari superiori, pertanto appare come se tutti i MP della mesh fossero direttamente connessi al livello data link. I protocolli mesh

68

introdotti dallo standard nascondono i dettagli delle funzionalità mesh ai livelli superiori, fornendo semplicemente la consegna dei dati a livello 2 all’interno della mesh; il piano di forwarding supporta sia un indirizzamento “individuale” che di “gruppo” (lo standard adotta la nomenclatura “individually address” per riferirsi alla consegna unicast, e “group address” per riferirsi a consegne broadcast o multicast).

La Figura 2.5 illustra questo concetto: la rete mesh appare ai bridge 802.1 e ai livelli superiori come un unico dominio broadcast di livello 2, privo di loop. 802.11s Mesh Point 802.11s Mesh Point 802.11s Mesh Point 802.11s Mesh Point 802.11s Mesh Point 802.11s Mesh Point 802.11s Mesh Point 802.11s Mesh Point 802.11s 802.11s MAC MAC 802 802 MAC MAC Bridge Bridge 802.11s 802.11s MAC MAC 802 802 MAC MAC Bridge Bridge 802.11s 802.11s MAC MAC 802 802 MAC MAC Bridge Bridge 802.11s 802.11s MAC MAC 802 802 MAC MAC Bridge Bridge Mesh Portal Mesh Portal

L3 Router L3 Router 802.11s Mesh Point 802.11s Mesh Point 802.11s Mesh Point 802.11s Mesh Point 802.11s Mesh Point 802.11s Mesh Point 802.11s Mesh Point 802.11s Mesh Point 802.11s 802.11s MAC MAC 802 802 MAC MAC Bridge Bridge 802.11s 802.11s MAC MAC 802 802 MAC MAC Bridge Bridge 802.11s 802.11s MAC MAC 802 802 MAC MAC Bridge Bridge 802.11s 802.11s MAC MAC 802 802 MAC MAC Bridge Bridge Mesh Portal Mesh Portal

L3 Router L3 Router

Figura 2.5: modello di connettività nella rete mesh

2.2.3 Internetworking

Il Mesh Portal (MPP) permette alla rete mesh di comunicare con una rete esterna di livello 2 di tipo 802, come un segmento di LAN Ethernet. Il MPP in pratica agisce da bridge in modo compatibile allo standard 802.1D.

69

Figura 2.6: internetworking tra la rete mesh e reti 802

Nell’esempio di Figura 2.6 i dispositivi 14, 12 e 13 interagiscono in modo trasparente come se fossero connessi ad un normale switch layer 2.

Il una rete mesh possono esistere più MPP, come in Figura 2.6, e ciascuno di essi implementa un meccanismo per annunciarsi all’interno della rete mesh. Questo meccanismo utilizza dei messaggi chiamati Portal

Announcement (PANN), che vengono inoltrati periodicamente nella rete in

modo broadcast. Nella rete mesh possono esistere più MPP ma ciascun MP è tenuto ad identificare come Portal uno solo di essi. Il protocollo definisce, in modo basilare, un meccanismo per la selezione del MPP che può essere esteso per garantire un bilanciamento del traffico tra i MPP presenti ed un incremento della QoS.

70

2.3 Formato dei frame

Nello standard vengono introdotti nuovi tipi di frame ed altri già esistenti sono stati modificati. La maggior parte delle aggiunte riguardano i frame di management per la gestione dei servizi mesh introdotti dallo standard. Molte delle modifiche a frame esistenti si presentano sotto forma di aggiunta di Information Element (IE), che hanno un formato standardizzato. Ad altri frame, come quelli Data sono stati aggiunti dei campi.

Nel resto del paragrafo verranno descritti i formati dei frame di maggiore interesse.

2.3.1 Formato generale dei frame

Il formato generale dei frame comprende una serie di campi che compaiono in un ordine prefissato in tutti i tipi di frame. La Figura 2.7 illustra il formato generale di una trama di livello MAC. Il primi tre campi (Frame Control, Duration/ID e Address 1) e l’ultimo campo (FCS) costituiscono il formato base e sono presenti in tutti i tipi di frame. I campi

Address 2, Address 3, Sequence Control, Address 4, QoS Control, Mesh Header e Frame Body sono presenti solo in determinati tipi e sottotipi di

frame. Il campo Address 1 (RA) contiene l’indirizzo del MP che deve riceve il frame, mentre il campo Address 2 (TA) è l’indirizzo del MP che ha trasmesso il frame. Il campo Address 3 (SA) contiene l’indirizzo del MP che ha originato il frame, mentre Address 4 (DA) tipicamente rappresenta il

71

MP a cui è destinato il frame. Il contenuto effettivo degli indirizzi dipende dai flag “to-ds” e “from-ds” nel campo Frame Control. I campi,

Duration/ID e Sequence Control hanno lo stesso formato ed utilità dei

frame classici dello standard IEEE 802.11.

Quando presente, il campo Mesh Header precede direttamente il campo Frame Body e rappresenta la principale introduzione dello standard IEEE 802.11s al formato classico delle trame IEEE 802.11.

Lo standard descrive accuratamente il formato di ogni tipo e sottotipo di frame. Descrive tutti i componenti contenuti nel corpo dei frame di management ed il loro formato, ed in particolare il formato Mesh Action, che è la struttura base per il trasporto degli IE utilizzati per la gestione della maggior parte dei servizi Mesh.

Header MAC FCS 4 Body 4 o 16 2 6 2 6 6 6 2 Octets: 2 Mesh Header QoS Control Address 4 Sequence Control Address 3 Address 2 Address 1 Duration/ ID Frame Control FCS 4 Body 4 o 16 2 6 2 6 6 6 2 Octets: 2 Mesh Header QoS Control Address 4 Sequence Control Address 3 Address 2 Address 1 Duration/ ID Frame Control

Figura 2.7: formato generale della trama IEEE 802.11

La Tabella 2.1 riporta i tipi e sottotipi di frame aggiunti dallo standard IEEE 802.11s, specificati nei campi Type e Subtype del campo Frame

72

11 Extended 0000 Mesh Data

11 Extended 0001 Mesh Management

11 Extended 0010-1111 Reserved

Tabella 2.1: tipi di frame introdotti dallo standard IEEE 802.11s

La Figura 2.8 illustra il formato del campo Mesh Header.

12 2 1 Ottetti: 1 Mesh Address Extension Mesh Sequence Number Mesh Time To Live (TTL) Mesh Flags 12 2 1 Ottetti: 1 Mesh Address Extension Mesh Sequence Number Mesh Time To Live (TTL) Mesh Flags

Figura 2.8: formato del campo Mesh Header

Il Mesh Header è presente i tutti i frame di tipo Extended, di sottotipo Mesh

Data e Mesh Management, e può avere una dimensione variabile da 4 o 16

byte. Il principali campi sono i seguenti:

• Mesh Flags: che specifica il tipo di processing dell’header mesh, in

particolare specifica se è presente o meno il campo Mesh Address

Extension

• TTL: è utilizzato per mitigare l’effetto di eventuali loop nella rete,

facendo si che un frame venga scartato dopo che è stato inoltrato un numero massimo di volte

• Mesh Sequence Number: è utilizzato per rilevare la ricezione di frame

73

• Mesh Address Extension: fornisce due indirizzi MAC addizionali, Address 5 e Address 6. Questi vengono utilizzati principalmente per

la comunicazione tra entità che non supportano le funzionalità mesh. Nel paragrafo 2.6.2 verrà descritto dettagliatamente il loro utilizzo.

2.3.2 Formato individuale dei frame

Per fornire i servizi mesh vengono utilizzati sia i frame di tipo

Extended, introdotti dallo standard, sia i frame Management classici dello

standard IEEE 802.11, opportunamente modificati con l’aggiunta di alcuni campi (vedi Figura 2.9).

modificati MAC Frame Format nuovi Type: Extended Type: Management Subtype: Mesh Data Subtype: Mesh Management Beacon

Association Request / Response Reassociation Request / Response Probe Request

Probe Response

Local Link State Announcement Route Request

Route Reply Route Error Route Reply Ack ecc… (vedi tabella 2.2 )

74

2.3.2.1 Frame di Management

I principali frame di management che hanno subito delle modifiche nel loro contenuto sono: Beacon, Association Requet, Association Respone,

Reassociation Request, Reassociation Response, Probe Request e Probe Response. Qui descriviamo solo il frame di beacon, che è il frame di

maggiore interesse per comprendere le funzionalità e i servizi di tipo mesh. Nella Figura 2.10 viene illustrato il contenuto del campo Body in un frame Beacon.

SSID Mesh _ID Mesh Capability Mesh Neighbor List Mesh DTIM Mesh Portal Reachability BeaconTiming

MDAOP

AdvertisementsMKDDIE

Figura 2.10: campi contenuti in un frame di tipo Beacon

Oltre ai campi standard previsti da IEEE 802.11, ne sono stati aggiunti altri sotto forma di IE. Tra questi, quello di maggior interesse è il WLAN Mesh

Capability, utilizzato per annunciare i servizi disponibili nella rete mesh, ed

è presente in tutti i frame di management sopra elencati.

L’IE WLAN Mesh Capability ha il formato illustrato nella Figura 2.11.

Channel Precedence Indicator 4 1 1 1 2 4 4 1 1 1 MDA Capabilit y Syncroniz ation Capability Power Save capability Peer Capacity Active Metric ID Active Protocol ID Version Length ID PrecedenceChannel Indicator 4 1 1 1 2 4 4 1 1 1 MDA Capabilit y Syncroniz ation Capability Power Save capability Peer Capacity Active Metric ID Active Protocol ID Version Length ID

Figura 2.11: formato dell’Information Element WLAN Mesh Capability

75

• Active Protocol ID: identifica il protocollo di routing utilizzato nella

rete mesh (vale 0 per HWMP)

• Active Metric ID: identifica il tipo di metrica utilizzato nella rete mesh

(vale 0 per la metrica Airtime)

• Peer Capacity: indica la capacità di un MP di stabilire link aggiuntivi

• Power Save Capability: indica il supporto alla modalità “power safe”

• Synchronization Capability: indica il supporto ai servizi di

sincronizzazione

• MDA Capability: indica il supporto del nodo alla modalità MDA

• Channel Precedence: è il valore di precedenza del canale dell’UCG

(Unified Channel Graph) a cui il MP appartiene

Tra gli altri IE aggiunti nel formato del Beacon, vale la pena citare il Mesh

ID. Tipicamente l’SSID è utilizzato dalle STA per trovare gli AP, mentre il

Mesh ID è utilizzato dai MP per trovare gli altri MP appartenenti alla stessa rete. In questo modo non vengono confuse le due funzionalità. Per evitare che le stazioni trasmettano richieste di associazione ai MP non MAP, i MP possono inserire nel campo SSID un valore pari a tutti 1, mentre Mesh ID viene comunque rilevato dagli altri MP per le procedure di Discovery.

2.3.2.2 Frame Extended

I frame di tipo Extended possono essere di due sottotipi: Mesh Data e

76

I frame Mesh Data hanno il formato completo descritto nel paragrafo 2.3.1, in particolare tutti e 4 gli indirizzi dell’header vengono utilizzati, e i flag

To-DS e From-To-DS del campo Frame Control valgono entrambi 1.

I frame Mesh Management hanno il formato riportato nella Figura 2.12, che si differenzia da quello Mesh Data per la mancanza del QoS Header, oltre che per il contenuto specifico del campo Body.

Header MAC FCS 4 Body 4 o 16 6 2 6 6 6 2 2 Mesh Header Address 4 Sequence Control Address 3 Address 2 Address 1 Duration/ ID Frame Control FCS 4 Body 4 o 16 6 2 6 6 6 2 2 Mesh Header Address 4 Sequence Control Address 3 Address 2 Address 1 Duration/ ID Frame Control

Figura 2.12: formato di un frame di tipo Mesh Management

Il corpo del frame Mesh Management consiste principalmente in un Mesh

Action Data Unit, che è un tipo di MMPDU (MAC Management Protocol Data Unit) trasmessa tra due entità MAC, ed eventualmente un header per

la gestione della sicurezza.

Il Mesh Action Data Unit contiene il campo Mesh Action, illustrato in Figura 2.13. Questo è costituito da un campo Category e un campo Mesh

Action Details, costituito da un valore Action seguito da uno o più IE diversi

a seconda del tipo di Mesh Action.

varibile Ottetti: 1

Mesh Action Details Category

varibile Ottetti: 1

Mesh Action Details Category

77

2.3.3 Information Element

Lo standard definisce una serie di IE che possono essere utilizzati in varie combinazioni nei frame di tipo Management, Mesh Management e

Mesh Data.

Un esempio di IE è già stato visto nel 2.3.2.1 nella descrizione del formato del frame Beacon, ovvero il WLAN Mesh Capability.

Piuttosto che descrivere dettagliatamente ogni tipo di IE definito nello standard, nel resto della tesi verrà illustrato il formato dei vari IE contestualmente alle procedure che li utilizzano.

Tutti gli IE hanno una parte in comune costituita dai primi due campi: ID, che permette di distinguere il tipo di IE, e Length che rappresenta la lunghezza dell’IE.

2.3.4 Formato dei Mesh Management Action Frame

Il formato degli Action Frame tipicamente è quello base del campo Mesh Action visto in Figura 2.13. E’ composto da un campo Category, un campo Action e da uno o più IE. Nella Figura 2.14 è illustrato, come esempio, il formato di un Action Frame di tipo Route Request.

Route Request IE

variabile 1

Ottetti: 1

Action

Category Route Request IE

variabile 1

Ottetti: 1

Action Category

78

Il valore del campo Category è posto a 5 per tutti i tipi di frame mesh. Il campo Action individua il tipo di messaggio specifico. La Tabella 2.2 illustra i valori del campo Action per i principali tipi di frame.

Valore del campo Action

Descrizione Applicazione

0 Local Link state announcement Neighbor discovery

1 Peer Link Disconnect Neighbor discovery

2 Route Request HWMP routing

3 Route Reply HWMP routing

4 Route Error HWMP routing

5 Route Reply Ack HWMP routing

6 Congestion Control Request Congestion Control

7 Congestion Control Response Congestion Control

8 Neighborhood Congestion

Announcement

Congestion Control

9 Mesh Deterministic Access (MDA) MDA

10 Beacon Timing Request Beaconing and

Synchronization

11 Beacon Timing Response Beaconing and

Synchronization

12 Non-mesh Action Encapsulation Action

13 Connectivity Report Connectivity reporting

14 Radio Aware Optimized Link State

Routing (RA-OLSR)

79

15-254 Reserved Reserved

255 Vender Specific Mesh Management Vender Specific

Tabella 2.2: principali tipi di Action Frame introdotti dallo standard IEEE 802.11s

2.4 Sequenza di avvio di un MP

Nei prossimi paragrafi vengono descritti i principali protocolli e servizi previsti dallo standard IEEE 802.11s. Per mantenere una logica descrittiva verrà seguito l’ordine delle operazioni che esegue un MP quando viene acceso, ovvero la sequenza di avvio.

Tale processo può essere schematizzato nei seguenti punti: 1. Scanning attivo o passivo per scoprire altri MP. 2. Selezione del canale.

3. Creazione dei link con i vicini • Autenticazione • Associazione

• Autenticazione 802.11i e scambio di password 4. Misura della qualità dei link

5. Avvio dei servizi di routing e forwarding 6. Inizializzazione degli AP, se il nodo è un MAP

80

Figura 2.15: sequenza di avvio di un MP

2.5 Mesh Discovery e creazione dei link

Le procedure di Mesh Discovery e Peer Link Establishment descrivono il modo in cui i MP, in modo automatizzato, rilevano la presenza di una rete mesh, scoprono quali sono i loro vicini e configurano i link

81

wireless che andranno a formare la topologia. Ogni MP è configurato con un unico Mesh ID (vedi paragrafo 2.3.2.1) e con almeno un profilo o più profili di diversa priorità. Un profilo consiste di tre elementi:

• Il Mesh ID

• L’identificativo del protocollo di routing • L’identificativo di una metrica da utilizzare

2.5.1 Procedura di Discovery

L’obiettivo di questa procedura è quello di scoprire quali sono i MP vicini e le loro proprietà. Un MP che non è parte di una rete mesh, esegue uno scanning passivo (esaminando i Beacon ricevuti) o attivo (attraverso i messaggi di tipo Probe) per scoprire i MP vicini.

Quando viene rilevato un dispositivo, vengono esaminate le informazioni da esso annunciate, in particolare il Mesh ID e le informazioni di profilo contenute nell’IE Mesh Capability (entrambi contenuti sia nei Beacon sia nei messaggi di Probe, vedi paragrafo 2.3.2.1). Il nodo può essere classificato in una delle seguenti categorie:

• Neighbor: un nodo viene considerato neighbor quando le informazioni

annunciate dal vicino coincidono con almeno uno dei profili configurati sul nodo locale

• Candidate peer: se oltre ad avere un profilo compatibile, il campo Peer Capability contenuto nell’IE Mesh Capability è diverso da zero,

il vicino viene considerato come un possibile nodo verso cui stabilire un link

82

• Ignore node: se nessuno dei profili configurati coincide con le

caratteristiche annunciate da un dispositivo rilevato, questo viene classificato come nodo da ignorare

Se il MP non rileva nessun nodo vicino, adotta il Mesh ID del profilo configurato con più alta priorità e rimane attivo (ad esempio nel caso del primo MP che viene acceso).

Le informazioni sullo stato dei nodi vicini e le loro caratteristiche, principalmente quelle annunciate nell’IE Mesh Capability, vengono mantenute localmente nella Neighbor Table.

2.5.2 Selezione del canale

Nella rete mesh ci possono essere MP che hanno una o più interface radio e che possono utilizzare uno o più canali per la comunicazione tra MP. Se i dispositivi non supportano il channel-switching, ogni interfaccia radio deve essere configurata per lavorare su un singolo canale per volta, ma il canale può variare nel tempo. Lo schema di assegnamento dei canali usato nella WLAN Mesh può essere diverso a seconda della topologia e dei requisiti delle applicazioni della rete (vedi paragrafo 1.6 ).

83

La Figura 2.16 illustra tre esempi di allocazione dei canali. La Figura 2.16.a illustra il caso più semplice in cui tutti i MP utilizzano lo stesso canale, ad esempio nel caso in cui i MP siano forniti di una singola interfaccia radio. Questa modalità è chiamata Simple Unification Mode. Lo standard specifica un protocollo che permette ad una serie di MP di sincronizzarsi su un canale comune per comunicare, realizzando uno schema di questo tipo. I casi (b) e (c) di Figura 2.16 illustrano due metodi di allocazione dei canali più avanzati, in cui i MP possono avere più interfacce radio e nella rete vengono utilizzati più canali contemporaneamente. Questo schema è chiamato Advanced Mode. Lo standard è flessibile e permette di implementare un qualsiasi meccanismo di selezione dei canali, per ottimizzare le prestazioni nei vari scenari applicativi.

Una serie di interfacce radio di MP che sono interconnessi l’un l’altro attraverso un canale comune è definito nello standard come Unified

Channel Graph (UCG). Lo stesso dispositivo può appartenere a differenti

UCG. La Figura 2.17 esplica il concetto di UCG.

Esempi di Unified Channel

Graphs

84

Lo standard definisce un meccanismo per la coordinazione del cambio del canale usato all’interno di un UCG, nel caso sia necessario cambiare il canale per problemi di interferenza. Ogni UCG nella WLAN Mesh possiede un valore comune di precedenza utilizzato per unire più UCG o cambiare canale utilizzato in un UCG.

Per ogni interfaccia un MP può decidere di utilizzare una delle due modalità sopra descritte. La modalità utilizzata viene annunciata attraverso il flag apposito nell’IE Mesh Capability, contenuto sia nei Beacon che nei messaggi di Probe Request/Response.

I due protocolli che lo standard propone per la gestione degli UCG sono: • Simple channel unification protocol: meccanismo che consente di

sincronizzare tutti i MP sullo stesso canale nel caso in cui i MP siano configurati nella modalità Simple Unification Mode. Questo protocollo consente ai nuovi MP che vengono accesi di sincronizzarsi sul canale comune utilizzato in una mesh. Inoltre consente unificazione nel caso vengano rilevati più UCG disgiunti.

• Channel graph switch protocol: meccanismo che consente di cambiare

il canale di un UCG sincronizzando tutti i MP che ne fanno parte. Questo protocollo utilizza un nuovo tipo di frame chiamato Switch

Announcement.

Esaminiamo il caso più semplice in cui un MP sia configurato nella modalità Simple Unification Mode. Quando un MP non rileva nessun vicino durante la procedura di Discovery, adotta il Mesh ID di uno dei profili configurati, seleziona un canale operativo e il valore iniziale random del

85

mesh disgiunta, ovvero più MP operanti su canali diversi, viene selezionato il canale utilizzato dal nodo candidate peer che annuncia il CPI più elevato, e tale canale diventerà quello comune dell’UCG; inoltre il MP inoltre imposta il proprio CPI al valore di quello più elevato appena scoperto. Se un nodo già operativo rileva un MP con CPI più elevato che sta utilizzando un canale diverso da quello con cui è configurato lui stesso, può opzionalmente iniziare la procedura di Channel Graph Switching.

Per chiarire il concetto, conviene fare un esempio basandosi sulla situazione in Figura 2.18.

C

A

D

B

Figura 2.18: esempio di rete mesh in topologia lineare. In questo esempio si suppone che l’ordine di accensione dei nodi sia: A, B, C, D

Partiamo dallo stato in cui tutti i nodi sono spenti.

1. Il nodo A si accende. Non trova nessun vicino, quindi passa al canale 1 (definito nel suo primo profilo) e seleziona un valore del CPI in modo random pari a 5

2. Il nodo B si accende. Non trova nessun vicino, quindi passa al canale 2 (definito nel suo primo profilo) e seleziona un valore del CPI in modo random pari a 8

86

3. Il nodo C si accende. Rileva il vicino A, configura il canale 1, pari a quello di A, e setta il valore CPI come quello di A ovvero 5. In pratica si è creato un UCG sul canale 1 con CPI pari a 5.

4. Il nodo D si accende. Rileva il nodo A e il nodo B. Poiché B ha un CPI più grande, seleziona il canale 2, come B. In questo modo si è formato un UCG sul canale 2 con CPI pari a 8.

5. A rileva un MP con CPI maggiore sul canale 2 ed inizia la procedura di Channel Graph Switching, mandando in broadcast un messaggio di Switch Announcement per passare al canale 2. Setta un timer al cui scadere passerà al canale 2.

6. C riceve il messaggio di Switch Announcement e lo inoltra a sua volta. Anche il nodo C, allo scadere di un timer passerà al canale 2. In questo modo dopo un certo intervallo di tempo tutti i nodi comunicano su un canale comune, costituendo un unico UCG.

2.5.3 Creazione dei link

Il passo successivo è quello di creare i link tra i MP per formare la topologia Mesh. Nessun frame dati o di management viene trasmesso o accettato finché la procedura di link establishment non si è conclusa. Un MP inizia la procedura di link establishment, o partecipa alla procedura iniziata da un nodo vicino, solo nel caso in cui non abbia raggiunto il numero massimo di connessioni con i vicini.

Nel caso in cui siano stati rilevati più candidate peer, un MP decide quali link stabilire in base alle misure di qualità effettuate sui link.

87

I MP utilizzano tre tipi di messaggi di management per la gestione del protocollo:

• Association Request, con incluso l’IE Peer Link Open, utilizzato per

richiedere la creazione di un link

• Association Response, con incluso l’IE Peer Link Confirm, utilizzato

per accettare la creazione di un link

• Disassociation, con incluso l’IE Peer Link Close, utilizzato per

chiudere la connessione tra due MP

Un link si considera stabilito solo quando entrambi i nodi agli estremi del link hanno trasmesso e ricevuto i messaggi Peer Link Open e Peer Link

Confirm.

Il protocollo gestisce un meccanismo di ritrasmissioni, gestito attraverso timer, che garantisce la robustezza del meccanismo. Inoltre i messaggi trasportano un campo, detto directionality, che trasporta un numero pseudocasuale utilizzato per evitare problemi di sessioni concorrenziali del protocollo.

88

A B

Stato di B: associatrion_pending

Stato di B:subordinatenode, link down

Stato di A: association pending

Stato di A: superordinate node link down

Assoc req (dir=5) Assoc req (dir=3)

Assoc req (deny) Assoc req (accept)

se dirrecv<= dirsendallora scarta

Figura 2.19: scambio di messaggi per la fase di link establishment

Una volta stabilito il link, il nodo con indirizzo MAC più alto viene chiamato “superordinate node” e l’altro “subordinate node”. Dopodiché è necessario effettuare le misure sulla qualità del link richieste dal protocollo di routing. Prima che le misure siano state effettuate il link è considerato in stato inattivo. I link in questo stato sono ancora inibiti alla gestione dei servizi mesh. Il nodo denominato superordinate node è responsabile di effettuare le misure di qualità sul link. I parametri da valutare dipendono dal tipo di metrica che utilizza il protocollo di routing; nel caso di HWMP, il protocollo mandatario, i parametri sono due, ovvero la packet error rate, e il rate trasmissivo.

Una volta eseguite le misure, queste vengono trasmesse al nodo “subordinate node” attraverso i messaggi Local Link State Announcement. Tale meccanismo garantisce la simmetria delle informazioni sul link.

Nella Figura 2.20 è illustrato il formato dell’IE Local Link State

Announcement (LLSA), dove r è il bit rate espresso in Mbps e ef è la

89

Figura 2.20: formato dell’Information Element Local Link State Announcement, utilizzato per lo scambio delle misure di canale tra due MP vicini

Una volta che entrambi i MP posseggono le informazioni sulla qualità del link, quest’ultimo viene considerato attivo (vedi Figura 2.21 ).

misure

subordinate superordinate

Stato di A: link down

Stato di A: link up Stato di B: link down

Stato di B: link up

Local link state ann.

(r, ept)

A B

Figura 2.21: scambio delle misure di canale e modifica dello stato di un link

La Tabella 2.3 riassume i possibili stati di associazione in cui può trovarsi un nodo. La Neighbor Table deve memorizzare tale informazione e tutte le altre informazioni necessarie alla gestione del link, quali: l’indirizzo MAC primario del MP vicino, eventuali indirizzi MAC secondari nel caso in cui il MP sia fornito di più interfacce radio, le misure di qualità del link e il canale utilizzato.

90

Stato Descrizione

Neighbor Rilevato, ma senza possibilità di creare un link (peer

capability = 0)

Candidate peer Nodo candidate, link non ancora stabilito Association pending Procedura di creazione del link in corso

Subordinate, link down Associazione completa, link down in attesa delle misure. Nodo “superordinate”

Subordinate, link up Link attivo. Nodo “superordinate”

Superordinate, link down Associazione completa, link down in attesa delle misure. Nodo “subordinate”

Superordinate, link up Link attivo. Nodo “subordinate”

Tabella 2.3: descrizione dei possibili stati di un link secondo lo standard IEEE 802.11s

2.6 Path Selection Protocol e inoltro dei frame

Lo standard si riferisce ai termini “mesh path selection” e “mesh

forwarding” per descrivere la selezione dei path, single-hop o multi-hop e

l’inoltro dei frame lungo questi path a livello data link. Nel resto della tesi ci si riferirà con il termine “routing” per indicare il meccanismo di “mesh

path selection”, poiché in pratica si tratta di un vero e proprio protocollo di

91

I frame di tipo Data utilizzano il formato a quattro indirizzi con l’aggiunta di alcune informazioni specifiche (vedi paragrafo 2.3.1). Le stazioni si connettono ai Mesh AP (MAP) con le stesse procedure dello standard IEEE 802.11, poiché da un punto di vista logico la mesh è un insieme di AP che fanno parte dello stesso ESS (Extended Service Set).

I messaggi di routing, così verrà chiamato per semplicità il meccanismo, sono a loro volta trasportati a livello 2, utilizzando i frame di management (MMPDUs). I messaggi che utilizza il protocollo di routing si presentano sotto forma di IE, con i formati descritti nel paragrafo 2.3.2.2.

Sebbene lo standard garantisce flessibilità nella scelta del protocollo di routing, definisce un protocollo di routing mandatario, chiamato HWMP (Hybrid Wireless Mesh Protocol) per permettere l’interoperabilità tra le soluzioni di diversi venditori. Ogni MP può supportare più meccanismi di routing, ma solo uno deve essere utilizzato nella rete mesh. Allo stesso modo permette di implementare liberamente le metriche utilizzate dal protocollo di routing, ma, per gli stessi motivi, ne definisce una mandataria, che tutti i MP devono supportare, chiamata Airtime.

Come descritto nel paragrafo 2.3.2.1, il tipo di protocollo di routing utilizzato e la metrica scelta sono annunciati all’interno del campo Mesh

Capability Information.

Oltre al protocollo HWMP, che deve essere implementato in ogni nodo, lo standard propone anche un protocollo alternativo, chiamato RA-OLSR, basato sui principi del protocollo OLSR [7], ma adattato per lavorare a livello 2 sulla base del framework disegnato dallo standard.

92

2.6.1 Airtime metric

La metrica definita nello standard, chiamata “Airtime” per riflettere la sua caratteristica radio-aware, è concettualmente molto simile alla metrica ETX citata nel paragrafo 1.5.4.

Il costo di un link riflette l’ammontare delle risorse consumate su un canale per la trasmissione di un frame. Questa metrica rappresenta una stima approssimata e semplice di facile implementazione.

L’espressione analitica è la seguente:

e

r

B

O

O

c

−

⎥⎦

⎤

⎢⎣

⎡

₊

₊

=

1

1

dove Oca e Op sono delle costanti che rappresentano l’overhead del

protocollo, Bt è la dimensione, in numero di bit, del frame di test, mentre r e ept sono il rate di trasmissione espresso in Mbps e la percentuale di perdita

di frame sul link. La percentuale di perdita di frame ept è la probabilità che,

quando un frame di dimensione standard Bt viene trasmesso al rate corrente r, il frame venga corrotto dalla trasmissione. Lo standard lascia libera

93

Parametro _(802.11a) Valore _(802.11b) Valore Descrizione

Oca 75 us 335 us Channel access overhead

Op 110 us 364 us Protocol overhead

Bt 8224 8224

Number of bits in test frame

Tabella 2.4: valori delle costanti per il calcolo della metrica Airtime

2.6.2 Inoltro dei frame

Poiché la rete opera completamente a livello 2, l’inoltro dei frame avviene in base agli indirizzi MAC trasportati. In alcune situazioni i 4 indirizzi dell’header MAC non sono sufficienti: il caso principale è la comunicazione tra entità, come le STA tradizionali, che non implementano i servizi MAC. In questa situazione i MAP agiscono da proxy per le STA e non ci sono abbastanza indirizzi nell’header MAC per trasportare gli indirizzi MAC della STA sorgente e destinataria. Per questo nel Mesh

Header inserito nel frame IEEE 802.11 sono stati aggiunti due indirizzi

MAC opzionali. La presenza dei due indirizzi aggiuntivi è stabilita dal valore del flag AE del Mesh Header (vedi paragrafo 2.3.1).

La rete mesh è altamente dinamica, la topologia può cambiare velocemente nel tempo, inoltre i protocolli di routing sono dinamici quindi i percorsi possono cambiare nel tempo. Per questo motivo i frame originati da un MP possono arrivare fuori ordine al MP destinatario, oppure possono arrivare più copie dello stesso frame. Il campo Sequence Control presente

94

nell’header IEEE 802.11 è pensato per essere utilizzato hop-by-hop per controllare il problema dell’ordinamento dei frame e alla loro duplicazione su un singolo link, quindi non può essere utilizzato per risolvere il problema nella rete mesh. Pertanto nel Mesh Header è stato introdotto un nuovo campo, il Mesh Sequence Number, grazie al quale è possibile rilevare i frame duplicati e controllare l’ordinamento.

Lo standard distingue due tipi di indirizzi: “individually address” che rappresentano gli indirizzi unicast, e “group address” intendendo gli indirizzi che individuano contemporaneamente un gruppo di MP, quindi quelli che tipicamente sono gli indirizzi multicast e broadcast.

2.6.2.1 Inoltro dei frame unicast

La casistica delle possibili trasmissioni unicast comprende i seguenti casi: MP-MP, STA-STA. I casi ibridi come la comunicazione tra una STA e un MP si possono facilmente dedurre.

In linea di principio i sei indirizzi vengono utilizzati in questo modo: • Address 1 (RA) e Address 2 (TA) tra i nodi terminali di un link, tra il

trasmettitore (TX) e ricevitore (RX)

• Address 3 e Address 4 (SA) tra i nodi terminali di un percorso, tra un

MP sorgente e un MP destinatario (inclusi MPP e MAP)

• Address 5 e Address 6 per la comunicazione end-to-end tra due

terminali di tecnologia 802. Ad esempio tra due STA o tra una STA e un MP e viceversa.

95

MAP MP MPP STA 802

802.11 STA

link link link link

mesh path

comunicazione 802 end-to-end

Figura 2.22: illustrazione dei tre tipi di path tra dispositivi

La Tabella 2.5 riassume l’utilizzo dei sei indirizzi e il valore dei flag To-DS e From-DS del campo Frame Control e del flag AE nei vari casi.

Tabella 2.5: significato ed utilizzo dei 6 indirizzi di un frame IEEE 802.11s

I casi principali in cui è necessario l’utilizzo di sei indirizzi sono la comunicazione tra due STA, sia interne che esterne alla rete mesh, e la comunicazione tra due MP passando dal MPP.

96

Vediamo per esplicito questi due scenari.

In Figura 2.23 è illustrato il caso di comunicazione tra una STA 802.11 interna alla mesh e una stazione esterna su una rete cablata 802 connessa al MPP, come nel caso illustrato nella Figura 2.22.

Figura 2.23: caso di comunicazione tra una stazione IEEE 802.11 ed una stazione su una LAN esterna, in cui sono necessari tutti e 6 gli indirizzi della trama MAC IEEE 802.11s

I campi Address 5 e Address 6 in questo caso trasportano gli indirizzi MAC delle stazioni. La comunicazione tra una STA 802.11 (STA1) e l’Access Point (MAP1) avviene nel modo standard utilizzando solo tre indirizzi. La Figura 2.24 invece illustra il caso della comunicazione tra due MP interni alla rete attraverso un percorso che passa per il MPP. Questo caso è molto frequente e si presenta quando un MP vuole comunicare con un altro

97

MP interno alla mesh, ma il protocollo di routing non fornisce un percorso diretto tra i due MP.

Figura 2.24: esempio di impiego dei 6 indirizzi del frame IEEE 802.11s; comunicazione tra due MP interni alla rete mesh transitando per il MPP

2.6.2.2 Inoltro dei frame broadcast

I frame broadcast sono individuati dal campo Address 2 pari a tutti 1. Un MP accetta frame broadcast solo dai vicini. L’indirizzo MAC sorgente (SA) e il valore del Mesh Sequence Number identificano univocamente un frame broadcast. In questo modo un MP è in grado di sapere se un determinato frame è già stato ricevuto e, in tal caso, lo scarta. Prima di

98

inoltrare un frame broadcast, un MP decrementa il valore del TTL nel Mesh

Header.

2.7 Il protocollo HWMP

L’obbiettivo del routing è determinare i percorso d’inoltro verso le destinazioni e popolare la tabella di routing. Il protocollo HWMP è un protocollo di routing ibrido che combina la flessibilità del routing on-demand con un’estensione preventiva basata sulla costruzione di una topologia ad albero. La combinazione di queste due caratteristiche rende l’HWMP un protocollo flessibile adatto a una vasta tipologia di reti mesh, sia per le architetture di tipo “infrastruttura”, o gerarchiche, sia quelle flat, o ad-hoc.

L’HWMP utilizza una serie di regole derivate dal protocollo di routing AODV [6], adattato per un funzionamento totalmente a livello data link e col supporto di una metrica radio-aware adatta al mezzo wireless.

Il protocollo distingue due modalità operative non esclusive: • Modalità on-demand:

• Modalità preventva tree-based:

Nel caso in cui nella rete non ci sia un MPP, la procedura on-demand si occupa di instaurare i percorsi di instradamento peer-to-peer tra i MP. Nel caso invece in cui è presente un MPP come punto di uscita verso l’esterno, si possono combinare i due meccanismi: il meccanismo preventivo si occupa di costruire e mantenere una topologia ad albero che ha come radice il MPP e instaura una connessione tra tutti i MP e il MPP, fornendo

99

l’accesso alla rete esterna; il meccanismo on-demand consente di instaurare le comunicazioni intra-mesh tra i MP senza transitare dalla radice dell’albero. Tale scelta si basa sulla constatazione che la maggior parte delle applicazioni delle reti mesh mirano a fornire una connettività verso le reti esterne, come Internet, pertanto una grande porzione del traffico della rete è diretta da e verso il MPP.

L’approccio utilizzato dall’HWMP porta innumerevoli benefici :

• Flessibilità di adattamento ai requisiti che deve avere ogni rete mesh in ogni tipo di scenario.

• La scelta dei percorsi ottimi è affrontata in modo semplice ed efficiente.

• Inoltre la costruzione di una topologia ad albero ha i seguenti vantaggi:

o Il flooding è ridotto alla ricerca delle destinazioni all’esterno della mesh.

o Il traffico broadcast di management è ridotto.

o I path on-demand possono utilizzare la topologia dell’albero come appoggio per istituire percorsi di backup.

Entrambe le modalità utilizzano messaggi e regole di processing comuni. I messaggi utilizzati dal protocollo sono: Route Request (RREQ), Route

Reply (RREP), Route Error (RERR) e Route Announcement (RANN).

Questi messaggi sono strutturati in modo flessibile in modo da permettere di adattarsi ad entrambe le modalità di routing.

Inoltre l’HWMP utilizza un meccanismo basato sui sequence number per stabilire la validità dei messaggi e garantire l’assenza di loop nella rete in ogni momento.

100

Il fatto di disporre di due meccanismi che possono essere utilizzati anche insieme, consente di combinarli per elaborare diverse strategie di comunicazione, ed alcuni esempi verranno illustrati nel paragrafo 2.7.5.

Gestione delle informazioni locali

Per il corretto funzionamento del protocollo ogni MP mantiene localmente una serie di tabelle, le principali sono: Neighbor Table, Proxy Table, Forwarding Table.

Come accennato in precedenza, un MP è come se agisse da Proxy per i terminali normali, STA, a lui connessi, implementando i servizi mesh per fornire la connettività a tali nodi. Un MP pertanto deve conoscere quali sono i nodi per cui agisce da Proxy e mantiene tale informazione in una tabella apposita.

La Forwarding Table, elemento chiave del protocollo di routing, mantiene le informazioni sulla raggiungibilità degli altri MP. In essa sono registrate le informazioni sui MP, come indirizzo MAC e sequence number, e quelle relative al percorso per raggiungerli, ovvero next hop, metrica del path, lunghezza del path in termini di hop ed altre informazioni.

Per garantire l’affidabilità di tali informazioni, le entry delle tabelle sono gestite attraverso un meccanismo di timer e sequence number.

2.7.1 Routing on-demand

Se un MP sorgente S vuole comunicare con un MP destinatario D e non ha alcuna informazione per poter raggiungere tale nodo, deve

101

innanzitutto far si che nella rete si instauri un percorso d’inoltro tra i due nodi. Questa tecnica segue i principi base delle tecniche di routing on-demand come ad esempio AODV da cui l’HWMP riprende la maggior parte delle primitive.

Il routing on-demand nell’HWMP utilizza un meccanismo basato sui messaggi Route Request ( RREQ ) e Route Reply ( RREP ) per stabilire i percorsi tra i MP presenti nella rete.

Il formato di questi due messaggi è illustrato in Figura 2.25 e Figura 2.26.

Metric Element ID Length Flags Time to Live Ottetti: 1 1 4 1 RREQ ID 4 Originator Address 6 Originator Sequence Number 4 4 Destination Flags #1 1 Hop-count 1 Destination Address #1 6 …… 4 1 6 Destination Seq. Num. #N …… 1 DO RF Reserved Destination Flags #N DO RFReserved Destination Address #N Destination Seq. Num. #1 Lifetime Proxied Address 0 o 6 4

Figura 2.25: formato dell’Information Element Route Request (RREQ)

ID Length Mode_Flags Time to _Live

Ottetti: 1 1 4 1 Destination MP Address 6 Destination Sequence Number 4 Lifetime 4 4 Hop-count 1 Originator Address #1 6 6 4 Dependent MP DSN #1 …… 1 Dependent MP MAC Address #1 Originator Seq. Num. #1 Metric Dependent MP Count N 4 6 Dependent MP DSN #1 Dependent MP MAC Address #1 1 Destination Proxied Address 0 o 6

102

Quando un MP S vuole trovare un percorso per raggiungere un MP destinatario D, invia un messaggio RREQ in broadcast annunciando la destinazione D nel campo Destination Address. Inoltre è possibile, nello stesso RREQ, annunciare la ricerca di più destinazioni contemporaneamente. Per ogni destinazione viene specificato il MAC address, il numero di sequenza necessario per processare pacchetti non obsoleti e due flag DO (“Destination Only”) e RF (“Reply and Forward”) che gestiscono le politiche d’inoltro dei RREP da parte dei nodi intermedi. A causa della trasmissione broadcast, ogni nodo può ricevere copie multiple dello stesso RREQ che è stato originato da S, ognuno dei quali ha seguito un percorso diverso per arrivare alla destinazione D. Quando un nodo che non è il destinatario riceve un RREQ, crea una route verso S, oppure, se l’informazione sulla route è già nota e se il pacchetto ricevuto non è obsoleto e la metrica che annuncia per raggiungere S è migliore di quella già presente, aggiorna le informazioni sulla route. Dopo di ché il pacchetto RREQ viene re-inoltrato in broadcast. Prima di inoltrare il RREQ, il nodo deve aggiornare il campo Metric con la metrica cumulativa del path fino a quel punto del percorso, in questo modo il nodo destinatario è in grado di conoscere la metrica di ogni possibile path verso la sorgente.

I nodi intermedi non sono tenuti a generare RREP se non esplicitato nel messaggio RREQ attraverso i flag DO e RF.

Se DO =1, solo la destinazione può rispondere con un RREP. Se RF=1 invece, i nodi intermedi, se hanno già informazioni sul percorso verso la destinazione, possono rispondere con un RREP e allo stesso tempo re-inoltrare in broadcast il RREQ. La possibilità di risposta dei nodi intermedi permette di ridurre il tempo di instaurazione del percorso d’inoltro.

103

Una volta raggiunta la destinazione D, il MP crea, od aggiorna, la route verso il MP sorgente ed invia un messaggio RREP di risposta, in modalità unicast verso la sorgente.

Il MP può ricevere più RREQ che hanno seguito percorsi diversi. In teoria il MP potrebbe aspettare di ricevere tutti i possibili RREQ e scegliere il path con metrica migliore, ma poiché il tempo di instaurazione del path è molto critico nelle procedure on-demand, la soluzione scelta è quella di scegliere il path relativo al primo RREQ che giunge a destinazione.

Il RREP seguirà il percorso a ritroso verso la sorgente seguendo il percorso migliore; ogni nodo, infatti, ha precedentemente creato la route per raggiungere il MP S. Allo stesso tempo i nodi intermedi che processano il RREP, creano la route per raggiungere il MP destinatario. Una volta che il RREP è giunto a S, il path si è stabilito e la comunicazione può iniziare.

2.7.2 Routing preventivo tree-based

Quando nella rete è presente un MPP che fornisce la connettività verso la rete esterna, ogni nodo può mantenere, in modo preventivo, le informazioni sulla raggiungibilità del Portal. In questo modo si ottimizzano le comunicazioni verso la rete esterna, poiché le informazioni sulla route per raggiungere il MPP sono sempre disponibili ed aggiornate, senza la necessità di invocare la procedura on-demand. Oltre ai vantaggi in termini di velocità, tale soluzione consente di ottimizzare l’utilizzo delle risorse della rete. Infatti, in uno scenario in cui la maggior parte delle

104

comunicazioni sono dirette verso l’esterno, sarebbe inefficiente ogni volta inondare la rete di messaggi broadcast per instaurare il path verso il MPP. Il meccanismo di routing tree-based consente la creazione di una topologia ad albero nella rete mesh che ha come radice il MPP.

L’HWMP prevede due metodi per la disseminazione delle informazioni di routing necessarie per instaurare i path verso la radice. Il primo metodo si basa sull’invio periodico da parte del MPP di messaggi di RREQ, in tal caso ci si riferisce a tali messaggi come Proactive RREQ. Il secondo metodo utilizza i messaggi Root Announcement (RANN), intesi alla distribuzione delle informazioni di raggiungibilità della radice.

La differenza è che il primo metodo è mirato all’instaurazione vera e propria dei path d’inoltro tra i MP e la radice. Nel secondo caso, invece, la radice distribuisce le informazioni sulla sua raggiungibilità, ma i percorsi d’inoltro possono essere instaurati on-demand.

Entrambi i meccanismi sono regolati da una serie di timer per il controllo del flooding e l’ottimizzazione delle scelte dei percorsi d’inoltro, tuttavia per snellire la trattazione non verranno descritti.

2.7.2.1 Meccanismo basato sui Proactive RREQ

In questa modalità il MPP invia periodicamente in broadcast i messaggi PRREQ. In questi messaggi i flag DO e RF valgono 1, la metrica è pari a zero e il sequence number è un numero progressivo incrementato dal MPP ad ogni invio.

105

I MP che ricevono tale messaggio inizializzano o aggiornano le informazioni di raggiungibilità del MPP, registrando il next hop, la metrica del path e il numero di hop necessari per raggiungere la radice. Dopo di ché aggiornano i campi hop count e TTL del PRREQ e aggiornano la metrica aggiungendovi quella dell’ultimo link su cui è stato ricevuto il messaggio. Poi inoltrano il messaggio.

In questo modo le informazioni circa la presenza e la raggiungibilità della radice sono disseminate in tutta la rete.

Ogni MP può ricevere copie multiple del PRREQ ognuna proveniente da un percorso diverso dalla radice al MP. Il MP può aggiornare o cambiare la route verso la radice solo se il PRREQ contiene un sequence number maggiore oppure se ha lo stesso sequence number, ma una metrica di percorso migliore rispetto a quella memorizzata nella tabella di forwarding. In questo modo si sono creati i percorsi d’inoltro in uplink, ovvero ogni MP sa come raggiungere il MPP, ma ancora l’instaurazione del path non è completa poiché i MP non hanno ancora informazioni sulla presenza e raggiungibilità dei loro figli nell’albero.

L’instaurazione del percorso inverso avviene attraverso l’invio di messaggi RREP, detti “gratuitous” (GRREP). A seconda del flag “Proactive RREP” contenuto nel PRREQ, un MP può o deve rispondere al PRREQ con un GRREP.

Il GRREP è trasmesso in modo unicast verso la radice. In questo modo, sia i MP intermedi che il MPP registrano la raggiungibilità del MP che ha originato il messaggio. A questo punto i percorsi d’inoltro si sono formati, costruendo una topologia ad albero e permettendo una connettività bidirezionale.

106

Come illustrato in Figura 2.26, nel messaggio RREP compaiono una serie di campi, chiamati “Dependent MP”. Questi sono utilizzati nei Gratuitous RREP, per annunciare i MP discendenti dell’albero, ovvero quei MP che passano attraverso il MP in esame per raggiungere la radice.

Lo standard non specifica l’utilità di questi campi, ma intuitivamente essi servono per una serie di procedure di mantenimento dell’albero in seguito alla caduta di link o quando un MP cambia il nodo genitore. Nel caso in cui un MP scelga di cambiare genitore, lo standard specifica solo che il MP deve mandare un GRREP verso la Root, attraverso il nuovo percorso, ed annunciare l’elenco dei suoi dependent node, senza poi specificare dei meccanismi per la gestione di tali informazioni.

2.7.2.2 Meccanismo basato sui RANN

In questa modalità la root trasmette periodicamente i messaggi di Root Announcement (RANN) in modo broadcast. Il flooding di questi messaggi segue le stesse regole dei PRREQ. La differenza è che i MP che ricevono il RANN non sono obbligati a instaurare un path verso la radice.

Una volta memorizzate le informazioni sulla raggiungibilità della root, se un MP vuole instaurare una connessione con essa, per raggiungere le reti esterne, deve iniziare una procedura on-demand. Tale procedura segue in linea di principio le regole descritte nel paragrafo 2.7.1, ma in questo caso i RREQ sono mandati in modo unicast verso la root, in quanto si hanno già le informazioni sulla raggiungibilità. Lo scambio di messaggi RREQ e RREP serve solo alla creazione delle route nei nodi intermedi.

107

Analogamente al meccanismo basato sul PRREQ, quando un MP decide di cambiare il genitore per raggiungere la root, deve mandare un GRREP contenente la lista dei suoi dependent node.

Nella Figura 2.27 è illustrato il formato del messaggio Root Announcement (RANN).

ID Length Flags Time to _Live

Ottetti: 1 1 1 Originator Address 6 Destination Sequence Number 4 Lifetime 4 4 Hop-count 1 1 Metric

Figura 2.27: formato dell’Information Element Root Announcement (RANN)

2.7.3 Mantenimento e ottimizzazione

La prima proposal dello standard prevedeva solo l’utilizzo del meccanismo basato sui RANN e le sue procedure erano molto più complesse. In particolare descriveva una lunga serie di meccanismi per il mantenimento e l’ottimizzazione dei percorsi dell’albero, attraverso l’invio periodico di messaggi di verifica, e con utilizzo intenso dei messaggi Route Error nel caso di cambiamenti topologici dell’albero. Negli ultimi draft tali procedure sono state snellite pesantemente, fino a ridursi alle semplici procedure descritte nei paragrafi precedenti. Tuttavia, da un’analisi dettagliata dei protocolli, ci si rende conto che ci sono ancora molte lacune su questi aspetti.

108

Nel caso in cui il link verso un nodo vicino non sia più disponibile, ad esempio per la rottura del dispositivo, un MP trasmette in broadcast un messaggio di Route Error (RERR), che annuncia che lui non è più in grado di comunicare con il MP caduto. L’informazione, propagandosi nella rete, fa si che anche gli altri MP possano eventualmente aggiornare le informazioni di routing.

In Figura 2.28 è illustrato il formato di un messaggio RERR.

ID Length Mode Flags Ottetti: 1 1 Destination Address 6 Destination MP Sequence Number 4 Num. of Destination 1 1

Figura 2.28: formato dell’Information Element Route Error (RERR)

2.7.4 Gestione delle stazioni 802.11

Come visto nei paragrafi precedenti, i MAP agiscono da proxy per le normali stazioni che non implementano le funzionalità mesh.

Ogni MP mantiene una Proxy Table dove tiene traccia delle STA, chi è il loro MP Proxy, e se sono interne o esterne alla rete mesh (infatti potrebbero anche trovarsi in una LAN collegata al MPP).

Lo standard prevede un meccanismo per la gestione delle informazioni sulle normali stazioni [34]. Tale procedura si basa su due tipi di messaggi: Proxy

Update (PU) e Proxy Update Confirmation (PUC). Il Proxy Update viene

109

facendo da Proxy; tale messaggio può annunciare la presenza, o la cancellazione, di una o più stazioni.

Il PUC serve per dare la conferma della ricezione, poiché il protocollo prevede un meccanismo d’inoltro affidabile con tanto di ritrasmissioni multiple nel caso in cui non arrivi il PUC entro un certo tempo.

Nella Figura 2.29 sono illustrati i formati del PU e del PUC.

ID Length Flags Ottetti: 1 1 Proxy Address 6 Sequence Number Proxied MAC Address #1 6 …… 1 Number of Proxy Address N 2 1 Proxied MAC Address #1 6 ID Length Flags Ottetti: 1 1 Destination MP Address 6 Sequence Number 1 1 Proxy Update

Proxy Update Confirmation

Figura 2.29: formato degli Infromation Element Proxy Update (PU) e Proxy Update Confirmation (PUC)