Capitolo 2
PROTOCOLLI DI ROUTING
Al crescere della dimensione delle reti wireless, i nodi che le costituiscono si trovano dislocati in aree molto piu grandi del proprio raggio di copertura radio. Sono necessari, quindi, dei protocolli di routing per creare cammini di comunicazione tra nodi distanti sfruttando nodi intermedi.
A causa della natura altamente dinamica delle reti ad hoc, caratterizzate da frequenti e non predicibili cambiamenti di topologia, lo sviluppo di algoritmi di routing risulta molto piu complesso di quanto non lo sia per le reti cablate tradizionali.
Gli algoritmi di routing in ambiente MANET devono tenere conto della disponibilita di banda limitata e della forte dinamicita che caratterizzano questo tipo di reti. La condizione ideale e rappresentata dal limitare l'overhead generato dal traco di controllo, mantenendo una notevole rapidita nel rispondere ai cambiamenti frequenti di topologia.
In una rete ad hoc multihop un pacchetto passa tipicamente attraverso
diversi nodi prima di arrivare a destinazione. Ogni nodo della rete, quindi,
deve sapere in ogni momento a quale nodo consegnare il pacchetto per
raggiungere la corretta destinazione. Dunque, tutti i nodi della rete
si occupano dell' instradamento dei pacchetti. Questa e una di erenza
fondamentale rispetto alle reti cablate tradizionali, dove l'instradamento
viene gestito dai router, che rappresentano un sottoinsieme numericamente
limitato dei nodi presenti nella rete.
Gli algoritmi di routing sono di tipo distribuito. Questo signi ca che tutti i nodi della rete devono eseguire gli algoritmi stessi, senza alcun coordinamento centrale. Inoltre devono essere scalabili, ovvero capaci di adattarsi in modo eciente all'incremento del numero di nodi presenti nella rete.
La forte dinamicita della rete e la necessita di non generare un eccessivo overhead con il traco di controllo ha reso necessario lo studio e la progettazione di nuovi protocolli di routing per reti MANET.
2.1 Classi cazione
I protocolli di routing possono essere classi cati secondo vari livelli. Il primo livello di classi cazione e basato sul tipo di comunicazione che permettono di stabilire: unicast, geocast, multicast o broadcast.
Gli algoritmi unicast sono usati per le comunicazioni uno-a-uno (un
mittente manda pacchetti ad un unico destinatario) e rappresentano la
categoria piu vasta. Gli algoritmi multicast sono utilizzati per inviare
uno stesso messaggio ad un gruppo di nodi identi cati dall'indirizzo della
sottorete. Gli algoritmi di tipo geocast rappresentano un caso particolare
degli algoritmi multicast in cui il gruppo di nodi destinatari si trova collocato
in una determinata area geogra ca. In ne, gli algoritmi broadcast sono
usati per inviare un dato pacchetto a tutti i nodi che partecipano alla
rete. Occorre osservare che una trasmissione wireless viene automaticamente
ricevuta da tutti i vicini che si trovano nel raggio di copertura del
trasmettitore. Quindi, per avere una trasmissione broadcast, ciascun nodo
potrebbe limitarsi a ritrasmettere tutti i pacchetti che riceve. Questo,
pero, sarebbe molto ineciente a causa dell'elevata quantita di ritrasmissioni
ridondanti e quindi sono state sviluppate soluzioni piu ecienti.
2.1 Classi cazione
L'inoltro dei pacchetti puo avvenire in accordo a due tecniche fondamentali:
Source Routing - Il pacchetto contiene tutte le informazioni sul percorso da compiere per arrivare a destinazione;
Hop-by-Hop Routing - Ciascun nodo e ettua l'inoltro dei pacchetti sulla base del contenuto memorizzato nelle sue tabelle di routing.
La nostra attenzione si focalizzera sugli algoritmi di tipo unicast basati su hop-by-hop routing, che possono essere suddivisi in tre categorie: reattivi, proattivi e ibridi.
Negli algoritmi di tipo reattivo le rotte vengono calcolate esclusivamente quando e necessario, inoltrando la richiesta in rete (route discovery process).
Infatti, se i nodi non generano traco applicativo, il routing rimane inattivo.
I percorsi cos individuati vengono mantenuti nche la destinazione non risulta piu raggiungibile o il percorso e obsoleto o non piu utilizzato.
Il paradigma utilizzato nei protocolli reattivi e di tipo richiesta/risposta:
ciascun nodo, dopo aver inviato in rete la richiesta di un percorso verso una data destinazione, si dispone in attesa della risposta. Naturalmente questa procedura non deve essere ripetuta per ogni singolo pacchetto in quanto ogni rotta individuata rimane valida per un certo periodo di tempo, durante il quale possono essere svolte varie trasmissioni. Per questo motivo le informazioni di routing vengono mantenute in una cache no alla scadenza di un dato intervallo di tempo o nche non vengono cancellate esplicitamente perche risultano obsolete o non piu valide.
Questo tipo di protocolli, generando traco di controllo solo quando viene ricercata una rotta, sono caratterizzati da un basso overhead ma comportano un maggior ritardo temporale nella ricerca della rotta stessa. Alcuni degli algoritmi di tipo reattivo maggiormente utilizzati sono AODV [PR99], DSR [JM96] e TORA [CP97].
Dualmente, i protocolli proattivi, attraverso lo scambio periodico di
informazioni di controllo, mantengono nel tempo informazioni aggiornate
e consistenti sulle rotte necessarie per mettere in comunicazione generiche
coppie di nodi. Essi presentano il vantaggio di o rire immediatamente le rotte
richieste a spese di un overhead piu elevato dovuto al traco di controllo.
Tra gli algoritmi di tipo proattivo ricordiamo il protocollo OLSR [JMQ98]
ed il protocollo DSDV [BP94].
Esistono, in ne, anche dei protocolli ibridi che si comportano in modo proattivo in determinate circostanze mentre in altre hanno un comportamento reattivo. Tra questi possiamo citare il protocollo ZRP (Zone routing protocol) [HH01]. Questo protocollo ssa attorno a ciascun nodo una zona circolare, il cui raggio viene misurato in termini di numero di passi. Ogni nodo utilizzera un approccio proattivo verso tutte le destinazioni all'interno della suddetta zona mentre usera un algoritmo reattivo per calcolare il percorso verso le destinazioni all'esterno. Quando un nodo deve trasmettere del traco applicativo verso una data destinazione, cerca una rotta all'interno della propria tabella di routing. Se la destinazione interessata si trova all'interno della zona circolare individuata intorno al nodo mittente, allora esiste gia una rotta per poterla raggiungere.
Altrimenti, se la destinazione non e all'interno della zona, occorre avviare un procedimento di ricerca della rotta.
Nell'ambito di questa tesi sono stati analizzati in dettaglio due protocolli di routing: AODV e OLSR. Nei paragra successivi verranno descritte in dettaglio le funzionalita e le caratteristiche di tali soluzioni.
2.2 Il protocollo AODV
Il protocollo AODV (Ad hoc On-demand Distance Vector) [BDP03] e un protocollo di tipo reattivo ed opera puramente su richiesta. Questo signi ca che tutti i nodi che non fanno parte di alcun percorso attivo non devono conservare informazioni di routing ne essere coinvolti in scambi periodici di messaggi.
AODV associa un numero di sequenza a ciascuna rotta individuata. L'uso
di tale numero di sequenza assicura l'assenza di cicli nella ricerca delle rotte
e permette ad un nodo di scegliere sempre il percorso piu aggiornato.
2.2 Il protocollo AODV
Figura 2.1: Formato messaggio Route Request
2.2.1 Ricerca delle rotte
La funzionalita di scoperta di una rotta entra in azione quando un nodo sorgente vuole stabilire una comunicazione con un nodo destinatario verso cui non ha informazioni di routing.
In questo caso il nodo sorgente avvia un procedimento di ricerca della rotta trasmettendo in broadcast un messaggio di Route Request (RREQ), descritto in gura 2.1.
Il messaggio RREQ e costituito dai sequenti campi:
Type: Identi cativo numerico del tipo del messaggio (vale 1 per RREQ);
Flags: Possibili opzioni da settare (vedere [BDP03] per maggiori dettagli);
Reserved: Campo riservato per uso futuro. Attualmente viene posto a 0 dal trasmettitore e ignorato dal ricevitore;
Hop Count: Numero di nodi attraversati dal nodo origine al nodo
che attualmente sta elaborando il pacchetto (incrementato di uno di
nodo in nodo, prima di inoltrare nuovamente il pacchetto);
RREQ ID: Identi cativo che, insieme all'indirizzo IP del nodo sorgente, permette l'identi cazione univoca dei messaggi di RREQ;
Destination IP Address: Indirizzo IP del nodo destinazione verso cui si cerca una rotta;
Destination Sequence Number: Ultimo numero di sequenza usato dal nodo origine per identi care una rotta verso il nodo destinatario;
Originator IP Address: Indirizzo IP del nodo origine che ha generato la RREQ;
Originator Sequence Number: Numero di sequenza da usare per identi care la rotta verso il nodo origine all'interno della routing table.
Ogni nodo che riceve un pacchetto RREQ valuta se esiste o meno un'entrata nella propria tabella di routing corrispondente all'Originator IP Address. Se e gia presente, considerando l'Originator sequence number decide se deve o meno aggiornare tale entrata (se il numero di sequenza associato all'entrata della tabella di routing e inferiore a quello del pacchetto
e necessario fare un aggiornameno in quanto l'entrata e obsoleta).
Se nella tabella di routing non vi e alcuna entrata corrispondente all'Originator IP address del pacchetto, ne viene creata una che andra a far parte di un percorso inverso (Reverse route) verso la sorgente della richiesta.
Tale percorso potra essere usato per inviare il messaggio di Route reply (RREP) (ovvero la risposta alla richiesta RREQ) o piu in generale come percorso valido per pacchetti dati.
Quindi l'invio in broadcast del RREQ determina la formazione di percorsi inversi da tutti i nodi verso la sorgente della richiesta. Di questi percorsi ne verra scelto uno per trasportare la RREP e quindi dovranno essere mantenuti per un tempo suciente a far giungere RREQ a destinazione.
Ogni nodo che riceve una RREQ valuta se dispone o meno di informazioni
valide per raggiungere la destinazione desiderata. Se queste informazioni sono
disponibili il nodo provvede ad inviare (in unicast attraverso il Reverse route)
il RREP al mittente della richiesta. Se non ne dispone, invece, si limita a
2.2 Il protocollo AODV
Figura 2.2: Formato messaggio Route Reply
inoltrare in broadcast la richiesta dopo aver incrementato di un'unita il campo Hop Count. La richiesta puo essere inviata in broadcast anche se esiste una rotta verso la destinazione nella tabella di routing, qualora questa risulti obsoleta (ovvero se il Destination sequence number presente nella RREQ e maggiore di quello registrato nella tabella di routing).
Il messaggio RREP, illustrato in gura 2.2, e costituito dai seguenti campi:
Type: Identi cativo numerico del tipo del messaggio (vale 2 per RREP);
R: Repair Flag, utilizzato nel multicast;
A: Acknowledgment required;
Pre x Sz: Se diverso da zero indica che il nodo indicato come prossimo passo potrebbe essere usato per raggiungere qualsiasi nodo con lo stesso pre sso di routing (come indicato dal Pre x Sz) della destinazione richiesta;
Hop Count: Numero di hop dal nodo destinatario al nodo origine;
Destination IP Address: Indirizzo IP del nodo destinazione per cui viene fornita una rotta;
Destination Sequence Number: Numero di sequenza associato
alla rotta;
Originator IP Address: Indirizzo IP del nodo che ha generato la RREQ a cui viene fornita risposta;
Lifetime: Validita in millisecondi del percorso individuato.
In gura 2.3 e illustrato un esempio di ricerca della rotta avviata dal nodo S che vuole ottenere un percorso valido verso il nodo D.
Figura 2.3: Ricerca della rotta
2.2.2 Eventi di disconnessione
Ogni nodo deve tenere sotto controllo lo stato della connettivita verso i vicini ad un hop per tutte le rotte attive. Per tenere traccia della validita di un collegamento verso un vicino ad un hop si possono usare diversi
meccanismi, tra cui:
Scambio periodico di messaggi di Hello: un nodo periodicamente emette un messaggio di controllo (Hello) con il quale annuncia la propria presenza. La ricezione di tale messaggio indica a tutti i vicini ad un hop che il collegamento verso il nodo che lo ha emesso e attivo.
Un nodo considera rotto il collegamento verso un vicino ad un hop se
non riceve da questo alcun messaggio di Hello in un dato intervallo di
tempo;
2.2 Il protocollo AODV
Rilevazione dello stato della connessione: il livello MAC normalmente veri ca lo stato del collegamento ogni volta che manda un pacchetto verso un vicino. Se rileva la caduta del collegamento stesso, puo direttamente informare il livello routing.
Se un nodo rileva la perdita di connessione verso un vicino ad un hop che fa parte di una qualsiasi rotta attiva, emette un messaggio di Route Error (RERR), noti cando agli altri nodi la caduta della connessione. Per poter realizzare tutto cio ogni nodo conserva una lista contenente gli indirizzi IP di tutti i vicini di un hop che lo utilizzano come prossimo passo verso una qualche destinazione (a questi nodi vicini verra mandata in unicast la segnalazione di errore). I vari vicini provvederanno quindi a marcare come non valido il percorso corrispondente e a girare questa informazione ai nodi presenti nella lista suddetta.
In gura 2.4 e illustrato il formato del messaggio di Route Error (RERR):
Figura 2.4: Formato messaggio Route Error
Il messaggio e costituito dai seguenti campi:
Type: Identi cativo numerico tipo del messaggio (vale 3 per RERR);
N: No delete ag - Viene posto ad 1 quando un nodo esegue una
riparazione locale di un collegamento e i nodi a monte non devono
cancellare la rotta;
DestCount: Numero di destinazioni non raggiungibili incluse nel messaggio;
Unreachable Destination IP Address: Indirizzo IP della destinazione non raggiungibile a causa di una rottura del collegamento;
Unreachable Destination Sequence Number: Numero di sequenza associato all'entrata della tabella di routing corrispondente alla precedente destinazione non raggiungibile.
A questo punto, se la comunicazione verso la destinazione deve continuare, occorre avviare una nuova fase di ricerca della rotta per stabilire un nuovo percorso.
2.2.3 Ottimizzazioni
Il protocollo AODV adotta alcune strategie per evitare la formazione di cicli nella ricerca delle rotte e per ridurre l'overhead.
Nel protocollo AODV, un nodo che non sa come raggiungere la destinazione, si limita a rimandare in broadcast il RREQ. Per evitare che si formino dei cicli possiamo identi care in modo univoco ciascuna richiesta tramite la coppia (RREQ-ID, Originator IP address). In questo modo un generico nodo puo rilevare se ha gia ricevuto o meno una certa richiesta. A questo punto ogni nodo generera un RREP solo in corrispondenza della prima richiesta ricevuta, scartando tutte le altre. Attraverso questa eliminazione selettiva dei RREQ si riduce l'overhead limitando le possibili scelte per quanto riguarda le rotte inverse, come illustrato in gura 2.5.
Come ulteriore ottimizzazione, per evitare che l'inoltre dei RREQ generi
una grande quantita di traco, specie in reti densamente popolate, il
protocollo prevede che la sorgente della richiesta RREQ ssi un Time to
live (TTL) (massimo numero di hop per cui il messaggio viene inoltrato)
iniziale del pacchetto pari a 1 (TTL-START). Se, trascorso un certo tempo
non riceve alcuna risposta, intuisce che la richiesta non e andata a buon ne
2.3 Il protocollo OLSR
Figura 2.5: Selezione cammino per RREP
e provvede a generarne una nuova con un TTL incrementato, rispetto alla precedente, di 2 unita TTL-INCREMENT.
Il valore dell'intervallo di tempo, trascorso il quale viene generata una nuova richiesta, sara proporzionale al TTL. Questa procedura viene detta
"expanding ring search" [BDP03] in quanto la ricerca della destinazione viene fatta su anelli sempre piu grandi, aventi come centro il nodo sorgente.
Questo permette di ridurre il traco generato durante la ricerca di una rotta.
2.3 Il protocollo OLSR
Il protocollo OLSR (Optimized Link State Routing) [CJ03] e di tipo proattivo ed appartiene alla famiglia degli algoritmi link state. Nei protocolli di tipo link state tradizionali ciascun nodo individua i link con i propri vicini e distribuisce in modo adabile questa informazione di stato in tutta la rete, in modo che ogni altro nodo riesca a costruire una mappa completa della rete stessa.
Il protocollo OLSR cerca di ottimizzare la strategia degli algoritmi link
state riducendo il numero di ritrasmissioni durante la procedura di inoltro in
rete dell'informazione di stato.
Innanzitutto ogni nodo deve selezionare un sottoinsieme dei suoi vicini ad un hop ed adare esclusivamente a loro il compito di inoltrare in rete i suoi messaggi. Tali nodi sono i cosidetti multipoint relay (MPR) del nodo e sono gli unici vicini che ritrasmettono in broadcast i pacchetti del traco di controllo. Questa strategia consente di ridurre notevolmente il numero di ritrasmissioni. Inoltre ciascun nodo si limita ad annunciare la raggiungibilita di un sottoinsieme dei suoi vicini ad un hop, costituito da tutti quelli che lo hanno scelto come MPR (questi vicini sono detti multipoint relay selector del nodo).
Il protocollo OLSR opera in maniera completamente distribuita ed, essendo basato sull'invio periodico dei messaggi di controllo, non ha bisogno di una trasmissione completamente adabile per i propri pacchetti. Quindi
e in grado di tollerare eventuali perdite di pacchetti che si possono veri care all'interno delle reti wireless per problemi di trasmissione.
Il protocollo OLSR e costituito da alcune funzionalita essenziali che devono essere presenti e funzionanti in qualsiasi nodo che voglia operare in un dominio di routing OLSR e delle funzionalita ausiliarie che servono per scopi collaterali (ad esempio per gestire il collegamento con domini di routing diversi dalla MANET, come Internet). Il protocollo consente la coesistenza all'interno di una stessa MANET di nodi che non implementano le funzionalita ausiliarie (o le implementano solo in parte) e nodi che invece dispongono di tali servizi aggiuntivi, a patto che tutti comunque abbiano le funzionalita di base.
Per migliorare le prestazioni del protocollo e la sua capacita di adeguarsi rapidamente ai cambiamenti nella topologia, e possibile ridurre il periodo di emissione dei messaggi di controllo. OLSR fornisce ottime prestazioni all'interno di reti ad hoc densamente popolate e caratterizzate da molte coppie (diverse nel tempo) di nodi in comunicazione.
Come verra analizzato in dettaglio nei paragra seguenti, OLSR associa ad ogni pacchetto un numero di sequenza che consente al ricevitore di riordinare i pacchetti che riceve. Quindi OLSR non ha bisogno di appoggiarsi a protocolli che assicurino una trasmissione ordinata.
Esso inoltre organizza le informazioni di stato acquisite da ciascun nodo in
2.3 Il protocollo OLSR
tabelle (si dice infatti che OLSR e un protocollo "table-driven") e le mantiene consistenti nel tempo.
2.3.1 La tecnica dei multipoint relay
Per poter minimizzare le ritrasmissioni, ogni nodo seleziona un sottoinsieme dei suoi vicini simmetrici ad un hop, che verranno chiamati multipoint relay del nodo. Dato un generico nodo N, indichiamo con MPR(N) l'insieme dei multipoint relay scelti dal nodo. Ogni nodo costruisce indipendentemente il proprio insieme MPR, selezionando un sottoinsieme dei vicini ad un hop simmetrici (ovvero nodi verso cui il collegamento e bidirezionale) in modo che tutti i nodi a 2 hop di distanza siano raggiungibili attraverso almeno un nodo dell' insieme MPR. Anche questa condizione si veri chi occorre che ogni nodo del vicinato di N, raggiungibile in due passi, abbia almeno un collegamento simmetrico verso un nodo dell'MPR(N).
Gli unici nodi vicini ad un hop di un dato nodo N, che ritrasmetteranno i messaggi ricevuti in broadcast, sono quelli che fanno parte dell'MPR(N).
Gli altri si limiteranno ad elaborare il messaggio ricevuto senza inoltrarlo ulteriormente.
In gura 2.6 e riportato un esempio di inoltro dei pacchetti, senza l'ottimizzazione dei multipoint relay (le frecce rappresentano tutte le trasmissioni).
In gura 2.7, invece, e riportato un esempio di inoltro dei pacchetti ottimizzato attraverso l'utilizzo dei nodi MPR (cerchi neri).
Esistono vari algoritmi per il calcolo dell'insieme MPR di un nodo.
L'insieme MPR non deve essere necessariamente formato da tutti e soli i
nodi strettamente necessari per l'inoltro (MPR ottimo) ma puo anche essere
costituito da piu nodi di quelli necessari (MPR ridondante). Tuttavia e
preferibile avere un insieme MPR costituito da meno nodi possibile per
limitare il numero di ritrasmissioni (e conseguentemente avere un overhead
piu basso dovuto al traco di controllo). L'insieme MPR deve essere
ricalcolato ogni volta che si rileva un cambiamento di topologia nei nodi
vicini a 1 e 2 hop.
Figura 2.6: Inoltro pacchetti tradizionale
Figura 2.7: Inoltro pacchetti con ottimizzazione multipoint relay Ogni nodo deve, inoltre, tenere traccia di quali vicini ad un hop lo hanno scelto come MPR. Questi andranno a costituire il cosiddetto insieme MPR Selector. Chiaramente ogni nodo e tenuto a ritrasmettere in broadcast qualsiasi pacchetto (a meno di duplicati) proveniente da un vicino che faccia parte del suo insieme MPR Selector. Ad ognuno di questi insiemi MPR Selector e associato un numero di sequenza che permette di stabilire il livello di aggiornamento dell'informazione. Tale numero verra incrementato ogni volta che ci saranno dei cambiamenti nell' insieme.
Il protocollo OLSR calcola le rotte verso tutte le destinazioni possibili
passando attraverso i vari MPR scelti da ciascun nodo. Un qualsiasi percorso
2.3 Il protocollo OLSR
e quindi una sequenza di passi attraverso i multipoint relay dal nodo sorgente al nodo destinazione.
2.3.2 Formato dei pacchetti
OLSR si appoggia al protocollo UDP per trasferire i propri pacchetti. In particolare l'organizzazione IANA (Internet Assigned Number Authority) ha riservato la porta numero 698 per il traco OLSR. OLSR e in grado di operare su nodi che dispongono di piu interfacce di rete, ciascuna con il proprio indirizzo IP. Tuttavia ciascun nodo dovra scegliere uno di questi indirizzi e selezionarlo come identi cativo del nodo stesso nell'ambito della rete. Tale indirizzo e detto "main address" ed e utilizzato come Originator address per tutti i messaggi emessi dal nodo.
Figura 2.8: Formato pacchetto OLSR
Un pacchetto OLSR (vedere gura 2.8) puo incapsulare uno o piu messaggi di vario tipo ed e caratterizzato da un'intestazione di 4 byte contenente i seguenti campi:
Packet Lenght - Lunghezza in byte dell'intero pacchetto, compresa l'intestazione;
Packet Sequence Number - Numero di sequenza incrementato di uno ad ogni invio di un pacchetto OLSR.
Ciascun messaggio e caratterizzato da un formato standard che prevede un'intestazione (message header) ed un corpo (message body). In questo modo ogni nodo e in grado di accettare e se possibile ritrasmettere qualunque tipo di messaggio, anche se non ne sa interpretare il contenuto. Questo permette di estendere il protocollo con nuovi tipi di messaggio, permettendo la perfetta coesistenza all'interno di una stessa rete di nodi che supportano certi messaggi e nodi che non lo fanno.
Un messaggio OLSR e suddiviso nei seguenti campi:
Message type - Numero intero che identi ca il tipo di messaggio. I messaggi con tipo compreso nell'intervallo 0-127 sono riservati per i messaggi previsti dal protocollo mentre quelli nell'intervallo 128-255 sono da considerarsi "privati" e utilizzabili per estensioni
personalizzate del protocollo;
Vtime - Speci ca per quanto tempo l'informazione contenuta nel messaggio dovra essere considerata valida;
Message size - Dimensione in byte del messaggio, comprensivo di header;
Originator Address - Indirizzo principale del nodo che ha prodotto il messaggio;
Time to Live - Massimo numero di hop per cui il messaggio verra
inoltrato;
2.3 Il protocollo OLSR
Hop Count - Numero di volte in cui il messaggio e gia stato inoltrato;
Message Sequence Number - Numero di sequenza, incrementato di uno ogni volta che viene trasmesso un nuovo messaggio da parte del nodo.
2.3.3 Mantenimento delle informazioni di stato
OLSR e un protocollo di tipo table-driven, ovvero utilizza varie tabelle interne per memorizzare informazioni di stato necessarie per il corretto inoltro dei pacchetti. Tali tabelle devono essere mantenute aggiornate e consistenti nel tempo.
Le principali tabelle previste dal protocollo sono:
Interface Association Set - Registra gli indirizzi di tutte le interfacce presenti in un dato nodo;
Link Set - Registra lo stato di tutti i collegamenti verso i vicini. I collegamenti sono suddivisi in base alle interfacce di rete utilizzate dai singoli nodi. Quindi e possibile che tra due nodi esistano piu
collegamenti;
Neighbor Set - Registra gli indirizzi principali di tutti i vicini ad un hop, sia simmetrici che asimmetrici. Viene aggiornato ogni volta che ci sono dei cambiamenti nel Link Set;
2-hop Neighbor Set - Registra i main address di tutti i nodi che possono essere raggiunti attraverso ciascun vicino ad un hop;
MPR set - Registra i main address dei nodi scelti come MPR dal nodo locale;
MPR Selector Set - Registra i main address di tutti i vicini che
hanno scelto il nodo locale come MPR;
Figura 2.9: Formato messaggio HELLO
Topology Information Base - Memorizza tutte le informazioni sullo stato dei link ricevute dai vari nodi del dominio OLSR;
Duplicate Set - Registra informazioni su messaggi elaborati ed inoltrati recentemente.
2.3.4 Procedura di scoperta dei vicini
Per ottenere una conoscenza completa della topologia della rete, prima di tutto ogni nodo deve recuperare le informazioni relative ai nodi vicini con i quali ha un collegamento diretto e bidirezionale. Periodicamente, quindi, ogni nodo emette dei messaggi di HELLO, che contengono informazioni sui nodi vicini di un hop e sullo stato del collegamento verso di loro. Questi messaggi vengono trasmessi in broadcast, ma i nodi che li ricevono non devono ritrasmetterli ulteriormente.
Descriviamo il signi cato dei campi di un messaggio di HELLO, la cui struttura e schematizzata in gura 2.9:
Reserved - Riservato per uso futuro;
HTime - Intervallo di emissione del messaggio di HELLO;
Willingness - Disponibilita del nodo a inoltrare i messaggi verso altri
nodi;
2.3 Il protocollo OLSR
Link Code - Tipo di collegamento esistente tra l'interfaccia che emette il messaggio di HELLO e le interfacce dei vicini elencate di seguito. Questo campo e formato da due sottocampi fondamentali, lunghi 2 bit ciascuno: Neighbor Type e Link Type.
I valori possibili per il sottocampo Link Type sono:
{ UNSPEC-LINK: Indica che non ci sono informazioni speci che sul tipo dei collegamenti;
{ ASYM-LINK: Indica collegamenti asimmetrici;
{ SYM-LINK: Indica collegamenti simmetrici;
{ LOST-LINK: Indica collegamenti falliti;
I valori possibili per quanto riguarda il sottocampo Neighbor Type sono:
{ SYM-NEIGH: Indica che i vicini annunciati nel messaggio hanno almeno un collegamento simmetrico con questo nodo;
{ MPR-NEIGH: Indica che i vicini annunciati nel messaggio hanno almeno un collegamento simmetrico e sono stati scelti come MPR;
{ NOT-NEIGH: Indica che i vicini annunciati non sono piu (o non sono ancora) vicini simmetrici;
Link Message size - Dimensione in byte del link message, misurata dall'inizio del campo Link Code no al successivo campo Link code, ovvero no alla ne del messaggio se non vengono annunciati altri tipi di collegamento;
Neighbor Interface Address - Indirizzo IP di un interfaccia di un
nodo vicino.
Figura 2.10: Procedura di scoperta dei vicini basata su scambio messaggi HELLO
Tramite un messaggio di HELLO ciascun nodo speci ca sia la lista degli indirizzi dei nodi vicini a cui e collegato da un collegameto bidirezionale
1, sia la lista degli indirizzi dei vicini da cui ha ricevuto un pacchetto di HELLO ma il cui collegamento non e ancora stato riconosciuto come bidirezionale.
Attraverso lo scambio di questi messaggi un nodo conosce i vicini no a 2 hop di distanza e puo quindi calcolare il proprio insieme MPR. I vicini ad un hop che vengono scelti come MPR saranno annunciati con questo stato nei successivi messaggi HELLO e registreranno questa informazione aggiornando i propri MPR Selector set.
In gura 2.10 vediamo, in modo sempli cato, come e realizzata la procedura di scoperta dei vicini: il nodo A (che per ipotesi non conosce ancora alcun vicino) manda per primo un messaggio di HELLO, annunciando il proprio indirizzo. B riceve il messaggio e registra A come vicino asimmetrico, emettendo a sua volta un messaggio di HELLO contenente l'indirizzo di A. Non appena A riceve questo messaggio e vi trova il proprio indirizzo, provvede a trasformare il collegamento con B da asimmetrico a simmetrico e lo annuncia coerentemente nel successivo HELLO. A questo punto anche B trasforma A da vicino asimmetrico in vicino simmetrico e lo annuncia coerentemente nei successivi HELLO.
Attraverso questa procedura ogni nodo costruisce una tabella (neighbor table) in cui registrera gli indirizzi dei vicini ad un hop, il tipo di collegamento che lo lega a ciascuno di essi (simmetrico, asimmetrico o MPR) e gli indirizzi
1
