Distance vector

In informatica e telecomunicazioni, l'instradamento distance vector (routing basato sul vettore delle distanze), noto anche come routing di Bellman-Ford perché basato sull'omonimo algoritmo, è un tipo di algoritmo di routing dinamico, che tiene conto del carico istantaneo della rete.

Schema di una sottorete

Caratteristiche

Mentre gli algoritmi di tipo link state prevedono che ogni router sia informato dei cambiamenti occorsi nell'intera topologia della rete, i protocolli basati su distance vector - come RIP ed EIGRP - sono invece più leggeri: ogni router misura la distanza (secondo una metrica che può includere vari fattori) che lo separa dai nodi adiacenti ricevendo i dati dai router vicini. A partire da tali dati, utilizzando l'algoritmo di Bellman-Ford, il router costruisce una tabella che associa ad ogni destinazione conosciuta:

• la stima della distanza che lo separa dalla destinazione
• il primo passo del percorso calcolato

Periodicamente poi il router aggiorna le misure di distanza dai router adiacenti e comunica la propria tabella ai vicini. Dopo sufficienti scambi di informazioni, ciascun router potrà avere una riga per ogni altro nodo nella rete.

Esempio

Un processo di aggiornamento è riportato qui di seguito: si consideri una sottorete come in figura. Si supponga che F abbia stimato i ritardi dai router vicini C, I e G.

1. C sa di poter raggiungere A in 5 ms; quindi F, che ha calcolato un ritardo da C di 2 ms, sa di poter raggiungere A tramite C in 5+2=7 ms.
2. G sa di poter raggiungere A in 3 ms; quindi F, che ha calcolato un ritardo da G di 3 ms, sa di poter raggiungere A tramite G in 3+3=6 ms.
3. I sa di poter raggiungere A in 6 ms; quindi F, che ha calcolato un ritardo da I di 1 ms, sa di poter raggiungere A tramite I in 6+1=7 ms.

Il valore totale migliore è 6, quindi F crea nella sua tabella di routing un valore associato ad A registrando il ritardo pari a 6 ms e la linea di trasmissione G.

Problemi

Ogni router memorizza solo il primo passo dei percorsi che ha nella tabella. Questo implica che se A pubblica un percorso verso C, i vicini di A non possono sapere se sono stati inclusi da A nel percorso calcolato. Quindi:

• possono formarsi cicli
• quando si interrompe un collegamento si può avere una situazione di count-to-infinity

Una parziale soluzione sono le tecniche di Split horizon e di Poison reverse, che evitano di pubblicizzare le route attraverso le stesse interfacce di rete da cui hanno ricevuto le stime originali. L'introduzione di tempi di attesa prima di aggiornare una route scoraggia la formazione di cicli. Protocolli come EIGRP e DSDV evitano del tutto la formazione di cicli scambiando ulteriori informazioni.

Count-to-infinity

Si supponga di avere una rete "lineare" A-B-C-D-E-F e che si interrompa il collegamento con A. Al momento di aggiornare la propria tabella, B noterà che non può più raggiungere A tramite il suo collegamento diretto. Tuttavia C (che è ancora inconsapevole della situazione) sta dichiarando di poter raggiungere A in due passi; B riterrà quindi di poter raggiungere A in tre passi tramite C.

Questa situazione può propagarsi sulla rete generando stime di distanza sempre maggiori.

Voci correlate

• Router
• Algoritmi basati su link state
• Algoritmo di Bellman-Ford