Protocollo di Routing AODV

| | 3 Comments

Il protocollo AODV (Ad-hoc On-demand Distance Vector) è di tipo reattivo ed è pensato per essere usato in reti manet composte da un numero variabile di nodi tra le decine e le migliaia. Essendo stato appositamente studiato per l’ambito ad hoc offre un rapido adattamento alle condizioni variabili dei link, un basso utilizzo della rete (essendo reattivo produce traffico solo quando viene richiesta una rotta se questa non è già presente nella tabella di routing), una richiesta non eccessiva di memoria e di potenza di calcolo.
Si assicura l’assenza di rotte cicliche con l’utilizzo dei sequence number e evitando il problema del counting to infinity si assicura una veloce convergenza quando la topologia di rete viene modificata.


Ogni nodo mantiene in memoria una tabella di routing nella quale vengono memorizzate le seguenti informazioni:
• indirizzo IP del nodo destinazione (destination IP);
• numero di sequenza del nodo destinazione (destination sequence number);
• flag di validità della rotta (indica se la rotta è valida o invalida o in riparazione);
• distanza in numero di hop (hop count);
• lista dei precursori per quella rotta;
• tempo di validità (lifetime).
Tenendo presente che:
RREQ sono messaggi di Route REQuest e sono utilizzati nella fase iniziale di
Discovery, ed RREP I messaggi di Route REPlay che sono utilizzati nella fase finale di discovery, si supponga ora che un nuovo nodo X entri a far parte della rete e voglia comunicare con A;
a) poiché S non ha una riga nella sua tabella di routing riferita ad X, dà inizio alla procedura di Route Discovery: per prima cosa genera un messaggio RREQ nel quale inserisce il suo indirizzo IP nel campo Originator IP Address e quello di X nel campo Destination IP Address; quindi spedisce il messaggio in broadcast locale, inserendo il valore 255.255.255.255 nel campo Destination Address dell’header IP. I nodi E, F e G ricevono il messaggio di S e aggiornano le loro tabelle di routing avendo ottenuto informazioni nuove sulla rotta per raggiungere S.
b) I nodi E, F e G rispediscono la RREQ in broadcast locale. I nodi G, F , E e S ricevono una seconda copia dello stesso messaggio RREQ, se ne accorgono e lo scartano. I nodi A e D apprendono una rotta verso S inserendo in tabella come next hop G e E rispettivamente. Il nodo C riceve un primo messaggio da E ed aggiunge una rotta verso S passando per E; quando riceve il secondo messaggio da F, lo scarta.
c) I nodi A, C e D rispediscono la RREQ in broadcast locale. B e X la ricevono e aggiornano le loro tabelle aggiungendo una rotta verso S passante per C (ipotizzando che arrivino prima i messaggi provenienti da C piuttosto che quelli provenienti da A e D). Tutti gli altri nodi scartano il messaggio ricevuto avendolo ricevuto anche in precedenza. Il nodo X si accorge che il suo indirizzo IP coincide con il Destination IP Address indicato nel messaggio RREQ e prepara quindi un messaggio di risposta RREP copiando il proprio indirizzo nel campo Destination IP Address e quello di S nel campo Originator IP Address.
d) Questa RREP deve essere spedita in unicast a S, quindi X controlla nella sua tabella di routing verso quale nodo spedire il messaggio e, trovando l’informazione inserita poco prima, imposta come next hop C; il messaggio RREP viene quindi inserito in un pacchetto IP e spedito a C in unicast. Nel frattempo il nodo B inoltra la RREQ a X, D e C che la scartano essendo un duplicato di quella precedente.
e) Il nodo C, ricevendo la RREP da parte di X, aggiorna la rotta verso quest’ultimo nella sua tabella di routing. Inoltre, poiché ha ricevuto dal suo vicino X la RREP destinata a S, inserisce X nella lista dei precursori associata al nodo S. A questo punto inoltra il messaggio RREP verso il nodo F.
f) F riceve la RREP, aggiorna la rotta verso X inserendo C come next hop, aggiunge C nella lista dei precursori per la destinazione S ed inoltra il messaggio RREP a S.
g) A questo punto è stato instaurato un cammino da S verso X e viceversa e S può iniziare la comunicazione.

Routing AODV

AODV è un protocollo di tipo Distance vector, cioè usa come fattore discriminante tra due rotte verso la stessa destinazione il numero di hop che la separa dalla sorgente. Questo sarebbe adeguato per un ambito classico (reti cablate).
In ambito manet invece, a causa della scarsa affidabilità del canale radio e, soprattutto, della mobilità dei nodi, la topologia può cambiare imprevedibilmente e quindi la scelta della rotta più breve potrebbe non essere la migliore. Per questo motivo in AODV si sono introdotti i numeri di sequenza. In generale il numero di sequenza associato ad un nodo è monotonamente crescente; per questo motivo un messaggio M1 con numero di sequenza maggiore di un messaggio M2 contiene informazioni più aggiornate. Ne risulta che la scelta tra due rotte verso la stessa destinazione in AODV viene fatta prima valutando il numero di sequenza della destinazione e poi, in caso questi siano uguali, si discrimina in base al numero di hop. Per questo motivo i numeri di sequenza sono importanti anche per evitare
che si creino cicli nei cammini di routing. Un nodo aggiorna il proprio numero di sequenza in due casi:
• prima di generare una richiesta (RREQ) destinata ad un qualsiasi altro nodo della rete;
• prima di generare un messaggio RREP, in risposta ad un RREQ proveniente da un altro nodo della rete.
In caso un nodo perda il proprio numero di sequenza (per esempio in caso di riavvio della macchina) il protocollo prevede una procedura per ripristinarlo senza correre il rischio di compromettere le funzionalità di rete.
Per evitare di sovraccaricare la rete con richieste RREQ, nell’RFC di AODV è consigliato che il nodo sorgente che voglia iniziare una route discovery imposti il campo TTL dell’header IP secondo le seguenti regole:
• se è noto un precedente valore dell’hop count per la destinazione desiderata (derivante da un rotta presente in tabella ma invalidata perché non utilizzata per un periodo troppo lungo), viene usato tale valore, opportunamente incrementato per contemplare un eventuale allontanamento tra i nodi;
• altrimenti il TTL viene impostato a 1.
A causa di un riavvio del dispositivo, un nodo può perdere il proprio numero di sequenza. Tale valore, come si è visto, è importante per distinguere i messaggi nuovi da quelli vecchi; quindi il nodo X, appena riavviato, non può riprendere il normale funzionamento impostando il suo numero di sequenza a zero poiché in questo modo rischierebbe di utilizzare numeri di sequenza vecchi (troppo bassi); se così fosse i messaggi di segnalazione da lui generati non sarebbero presi in considerazione dagli altri nodi della rete, che li scarterebbero in quanto considerati obsoleti. Per evitare questa situazione il nodo X che si riavvia può decidere di:
• aspettare un intervallo di tempo relativamente lungo per far scattare in questo modo tutti i timeout nelle tabelle di routing degli altri nodi della rete; così facendo non vi sarà più nessuna rotta verso X memorizzata ed il numero di sequenza di X può ripartire da zero;
• imparare il proprio numero di sequenza dai messaggi RREQ a lui destinati;
infatti il nodo sorgente che genera i messaggi RREQ inserisce l’ultimo valore a lui noto del Sequence Number nel campo Destination Sequence Number e i nodi intermedi lo possono a loro volta aggiornare, se ne conoscono uno più recente.

Il protocollo AODV è stato dichiarato dall’IETF come un protocollo experimental, esso non tratta nessun problema di sicurezza, che nelle reti wireless è una questione fondamentale, per questo si è cominciato a discutere di SAODV, un implementazione di AODV che include un meccanismo di protezione del protocollo.

Precedente <- Manet
Successivo -> Problema dell’energia nelle Manet

Tags: , ,

Category: Computer

About the Author ()

Studio Ingegneria Informatica e Bio. all' Università Magna Graecia di Catanzaro, sono appassionato di informatica, e mi piace praticare la pesca nelle acque dolci.