Ad-hoc On-demand Distance Vector

algoritmo di routing

AODV è un algoritmo di routing per reti ad-hoc mobili e supporta sia l'instradamento unicast che multicast. Si basa su un protocollo di tipo reactive poiché ricerca dei percorsi nella rete solo su richiesta, al contrario dei protocolli più comuni in Internet e nelle reti cablate che individuano tutti i nodi ed i percorsi possibili della rete indipendentemente dal loro uso (protocolli di tipo proactive). Come suggerisce il nome, AODV è un derivato per reti ad-hoc del protocollo distance vector.

Funzionamento dell'algoritmo

modifica

Ogni nodo possiede un proprio numero di sequenza (sequence number) che cresce monotonamente nel tempo e che garantisce l'assenza di cicli nei percorsi utilizzati. Inoltre ogni componente della rete adibito alla funzionalità di routing memorizza un suo indice dei percorsi, che contiene l'indirizzo del prossimo nodo in direzione della destinazione (next hop), il suo numero di sequenza e la distanza complessiva indicata in salti (hops), o eventualmente in altre metriche atte alla misurazione della qualità del collegamento.

In AODV la rete rimane completamente silente finché non è richiesta una connessione per l'inoltro di un pacchetto dati. Quando è necessario cercare dei percorsi sulla rete, AODV ricorre ai seguenti pacchetti definiti dal suo protocollo:

  • Route request (RREQ)
  • Route reply (RREP)
  • Route error (RERR)

Questi messaggi possono essere implementati come semplici pacchetti UDP, per cui il routing si basa comunque sul Internet Protocol (IP).

I pacchetti RREQ vengono inviati in broadcast dal nodo sorgente, per cui si genera un'esplosione di messaggi che vengono inoltrati attraverso tutta la rete. Quando un nodo della rete riceve un pacchetto di richiesta può inviare un pacchetto di RREP attraverso un percorso temporaneo fino al nodo richiedente, che potrà dunque sfruttare l'informazione appena ricevuta. Generalmente ogni nodo confronta i diversi percorsi in base alla loro lunghezza e sceglie il più conveniente. Se un nodo non è più raggiungibile viene generato un messaggio di RERR per avvertire il resto della rete.

Ogni RREQ ha un "time to live" che limita le volte che può essere ritrasmesso. Inoltre AODV implementa un meccanismo di backoff binario nel caso il nodo non riceva risposta al suo RREQ, per cui le richieste vengono ripetute a intervalli di tempo crescenti linearmente fino ad un massimo stabilito dall'implementazione.

Valutazione

modifica

Il vantaggio principale di AODV è quello di non generare traffico nel caso di percorsi già stabiliti e funzionanti. In effetti, l'algoritmo stesso è del tutto ininfluente finché non risulta necessario inviare un pacchetto ad un nodo di cui non si conosce il percorso. Al di là di questo, il routing basato su distance vector risulta semplice dal punto di vista computazionale e non richiede grandi quantitativi di memoria.

Tuttavia il protocollo richiede tempi più lunghi rispetto ad altri protocolli per stabilire una connessione tra due nodi di una rete.

Voci correlate

modifica

Collegamenti esterni

modifica
  Portale Telematica: accedi alle voci di Wikipedia che parlano di reti, telecomunicazioni e protocolli di rete