DSDV

Destination-Sequenced Distance-Vector Routing (DSDV) è un protocollo d'instradamento proattivo per reti ad hoc mobili basato sull'algoritmo di Bellman-Ford. Fu sviluppato da C.Perkins and P.Bhagwat nel 1993. Il più grande contributo all'algoritmo fu quello di risolvere il problema dei loop.

Ogni voce della routing table contiene un numero di sequenza: pari se è attivo e dispari se è fallito. Il numero è generato dalla destinazione ogniqualvolta spedisce un aggiornamento. Le informazioni di routing sono distribuite fra i nodi. In questo, ciascun nodo mantiene la routing table con la entry di ciascun nodo sulla rete e si aggiorna con le informazioni sui vicini, distinguendo le destinazioni vecchie da quelle nuove

DSDV definisce due modalità di aggiornamento delle informazioni: incrementale (per tutti gli Network Protocol Data Units - NPDU) e full dumps; la prima modalità viene utilizzata quando l'aggiornamento per essere spedito necessita di un solo NPDU; la seconda modalità viene utilizzata quando sono necessari più NPDU per contenere le entry da aggiornare oppure quando un nodo rileva una modifica sostanziale alla topologia di rete.

Per esempio la tabella del nodo A potrebbe essere:

Destination	Next Hop	Number of Hops	Sequence Number	Install Time
A	A	0	A 46	001000
B	B	1	B 36	001200
C	B	2	B 28	001500

Naturalmente la tabella descrive tutti i possibili percorsi raggiungibili dal nodo A, oltre al next hop, numero di hops e il numero di sequenza. Ogni nodo utilizza inoltre un valore di Settling Time che definisce il momento in cui una nuova rotta appresa può essere validata ed inoltrata (per evitare loop).

Selezione della Rotta

Se un nodo riceve una nuova informazione relativa ad una rotta confronterà il numero di sequenza nel NPDU col numero di sequenza memorizzato nella tabella di routing. Gli aggiornamenti vengono effettuati solo nel caso in cui i numeri di sequenza ricevuti siano successivi rispetto a quelli salvati.

Data la natura della rete non sono rari i casi in cui un nodo riceva più aggiornamenti relativi alla stessa rotta con associato lo stesso sequence number ma caratterizzati però da numero di hop diversi (sintomo che la destinazione può essere raggiunta da più percorsi). In questo caso il nodo sceglie per l'aggiornamento la rotta con la metrica migliore (minor numero di hop).

Vantaggi

DSDV fu uno dei primi algoritmi disponibili riguardo alle reti mobili. Fu perfetto per reti ad hoc con pochi nodi. Visto che questo algoritmo non presenta delle specifiche formali, non viene quindi utilizzato per scopi commerciali, nonostante siano stati apportati numerosi miglioramenti.

Svantaggi

DSDV richiede aggiornamenti regolari delle tabelle di routing che richiedono spreco di risorse (batteria e banda) anche quando la rete è inutilizzata. Inoltre, affinché i nodi siano in grado di rilevarsi a vicenda, DSDV fa uso di beacon e "hello-packet".

Per ogni aggiornamento da inviare, sarà necessario un nuovo numero di sequenza.

Il caso peggiore si verifica quando avviene un path-break: per ogni singolo fail (frequenti nelle MANET data la mobilità degli host) i nodi sono costretti a scambiarsi NPDU (con numero di sequenza dispari) in flooding, generando overhead sul consumo di banda. Di conseguenza, DSDV risulta inadatto a reti molto dinamiche.

Influenze

Nonostante DSDV non sia molto usato oggi, altri protocolli utilizzano le sue tecniche. Il più conosciuto fra quelli è AODV che, essendo un protocollo reattivo, può utilizzare euristiche più semplici. Babel è un tentativo di rendere DSDV più robusto, efficiente e più portabile rimanendo tuttavia nel filone dei protocolli proattivi.

Bibliografia

• Perkins, Charles E. and Bhagwat, Pravin, Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers (PDF), 1994. URL consultato il 20 ottobre 2006 (archiviato dall'url originale il 10 settembre 2006).

• C. Siva Ram Murthy and B.S. Manoj, Ad Hoc Wireless Networks – Architecture and Protocols, Prentice Hall.