Protocolli e architetture di instradamento/L'algoritmo Distance Vector

Protocolli e architetture di instradamento

Copertina Protocolli e architetture di instradamento/Copertina

L'algoritmo Distance Vector (DV) è basato sulla distribuzione nell'intorno del router di informazioni sull'intera rete.

Ogni router genera periodicamente un DV, che è un insieme di coppie destinazione-costo:

destinazione: tutte le destinazioni conosciute dal router generante (nelle reti IP reali sono indirizzi di rete con netmask);
costo: il costo del percorso dal router generante alla destinazione.

Il router ricevente apprende da ogni DV:

destinazioni raggiungibili: si aggiungono a quelle già note localmente;
direzione: quelle destinazioni sono raggiungibili tramite il router generante;
costo: quello riportato dal router generante più il costo del link tra il router ricevente e il router generante.

Ogni nodo memorizza tutti i DV che arrivano dai vicini, e li integra selezionando i costi migliori per ogni destinazione al fine di costruire la sua tabella di instradamento e il suo DV:

Algoritmo base

processo principale:
1. il DV viene annunciato ai router adiacenti;
2. si attende per il timeout;
3. si ritorna al punto 1;
alla ricezione di un nuovo DV:
1. il DV viene salvato in memoria;
2. il DV viene unito con i DV memorizzati;
al guasto di un link (rilevato a livello fisico):
1. tutti i DV arrivati da quel link vengono eliminati;
2. i DV rimasti vengono uniti;
quando un DV non è ricevuto entro il timeout:
1. il DV mancante viene eliminato;
2. i DV rimasti vengono uniti.

Osservazioni

affidabilità: i timeout evitano l'uso dei segnali di link-up che possono non essere sempre disponibili (ad es. se il guasto avviene al di là di un hub);
efficienza: al guasto di un link, il router ottiene la nuova tabella di instradamento senza scambiare alcun DV con i nodi adiacenti;
velocità di convergenza: quando un router cambia il suo DV, non lo annuncia ai vicini fino al prossimo timeout del processo principale (no triggered update).

Triggered update

Un router può inviare il suo DV aggiornato non appena aggiorna la sua tabella di instradamento, senza aspettare per il timeout predefinito, per migliorare il tempo di convergenza. Può annunciare l'intero DV o, com'è più frequente nelle implementazioni reali, solo le rotte cambiate.

Il triggered update non reimposta il timeout del processo principale, per evitare che i router comincino a generare i DV allo stesso tempo (sincronizzazione).

Count to infinity

Si scatena un count to infinity quando il costo per raggiungere una destinazione, che non è più raggiungibile, viene progressivamente incrementato all'infinito.

Esempio

Nella figura a lato, un guasto sul link tra A e B scatena un count to infinity:

B rileva il guasto a livello fisico ed elimina il DV di A, ma C non è in grado di rilevare il guasto a livello fisico;
C annuncia a B di poter raggiungere A attraverso un percorso a costo 2, che in realtà era quello vecchio passante per B;
B aggiorna il DV di C, sembrando che A sia tornato raggiungibile tramite un percorso alternativo a costo 3 che passa per C;
B a sua volta invia il suo DV a C, il quale lo aggiorna e incrementa il costo a 4, e così via.

Effetto

B crede di poter raggiungere A tramite C, mentre C crede di poter raggiungere A tramite B → un pacchetto che è diretto ad A comincia a rimbalzare tra B e C (bouncing effect) saturando il link tra B e C finché il TTL non va a 0.

Causa

A differenza del buco nero e del routing loop, il count to infinity è un problema specifico dell'algoritmo DV, dovuto al fatto che le informazioni contenute nel DV non tengono conto della topologia della rete.

Soluzioni possibili

soglia per l'infinito: limite superiore al count to infinity;
algoritmi aggiuntivi: impediscono il count to infinity, ma rendono il protocollo più pesante e tendono a ridurne l'affidabilità perché non possono prevedere tutti i possibili guasti:
- route poisoning: le cattive notizie sono meglio di nessuna notizia;
- orizzonte limitato: se C raggiunge la destinazione A attraverso B, non ha senso per B cercare di raggiungere A attraverso C;
- path hold down: si lascia che il rumore si calmi in attesa della verità.

Soglia per l'infinito

È possibile definire un valore soglia: quando il costo raggiunge il valore soglia, la destinazione è considerata non più raggiungibile.

Ad esempio il RIP ha un valore di soglia pari a 16: non possono essere collegati più di 15 router in cascata.

Protocolli con metriche complesse (ad es. IGRP) richiedono un valore soglia molto elevato per tenere conto dei costi differenziati: ad esempio una metrica basata sulla larghezza di banda può risultare in un ampio intervallo di valori di costo.

Se il bouncing effect ha luogo su un link a basso costo, è necessario troppo tempo per aumentare i costi fino al valore soglia → è possibile utilizzare due metriche allo stesso tempo:

una metrica per i costi dei percorsi (ad es. basata sulla larghezza di banda del link);
una metrica per il count to infinity (ad es. basata sul numero di hop).

Quando la metrica usata per il count to infinity restituisce "infinito", la destinazione è considerata non raggiungibile a prescindere dal costo del percorso.

Route poisoning

Il router che ha rilevato il guasto propaga le destinazioni non più raggiungibili con costo pari a infinito → gli altri router apprendono del guasto e propagano a loro volta l'informazione "avvelenata".

Orizzonte limitato

Ogni router differenzia i DV inviati ai suoi vicini: in ogni DV omette le destinazioni che sono raggiungibili tramite un percorso che passa per il vicino a cui lo sta inviando → non si innesca la comparsa di percorsi "fantasma" verso una destinazione non più raggiungibile in seguito all'invio di informazioni obsolete nel DV.

Caratteristiche

evita il count to infinity tra due nodi (tranne in caso di cicli particolari);
migliora il tempo di convergenza dell'algoritmo DV;
i router devono calcolare un DV diverso per ogni link.

Orizzonte limitato con poisoned reverse

Nelle implementazioni reali, il DV può essere frammentato in più pacchetti → se vengono omesse delle entry nel DV, il nodo ricevente non sa se quelle entry sono state volontariamente omesse dal meccanismo dell'orizzonte limitato o se i pacchetti in cui erano contenute sono andati persi.

Nell'orizzonte limitato con poisoned reverse, le destinazioni invece di essere omesse vengono trasmesse comunque ma "avvelenate" con costo infinito, così il nodo ricevente è sicuro di aver ricevuto tutti i pacchetti che compongono il DV → aumenta la velocità di convergenza.

Path hold down

Se il percorso verso una destinazione aumenta di costo, probabilmente si sta per innescare un count to infinity → quella entry viene "congelata" per uno specifico periodo di tempo in attesa che il resto della rete trovi un eventuale percorso alternativo, dopodiché se nessuno annuncia più quella destinazione essa sarà considerata non raggiungibile e la sua entry sarà cancellata.

DUAL

Il Diffusing Update Algorithm (DUAL) è un algoritmo aggiuntivo che mira a migliorare la scalabilità dell'algoritmo DV garantendo l'assenza di routing loop anche durante il transitorio:

cambiamento di stato positivo: se un qualsiasi nodo vicino annuncia un percorso alternativo a costo inferiore, esso viene subito accettato perché sicuramente non provocherà un routing loop;
cambiamento di stato negativo: se
- il next hop corrente annuncia l'incremento del costo della rotta corrente (gli annunci peggiorativi da parte di altri nodi vicini sono ignorati), oppure
- il router rileva a livello fisico un guasto sul link appartenente alla rotta corrente
allora è necessario attivare l'algoritmo DUAL:
1. selezione di un vicino accettabile: viene selezionato un altro vicino solo se garantisce che il percorso alternativo attraverso di esso non provocherà routing loop;
2. processo di diffusione: se non si riesce a trovare alcun vicino accettabile, il nodo entra in una sorta di "modalità di panico" e chiede aiuto ai vicini, aspettando che qualcuno segnali un percorso ammissibile verso quella destinazione.

Selezione di un vicino accettabile

Se la rotta corrente non è più disponibile a causa di un cambiamento di stato negativo, un percorso alternativo è selezionato solo se è possibile dimostrare che il nuovo percorso non crea dei cicli, cioè se è certo che il nuovo next hop non utilizza il nodo stesso per raggiungere la destinazione.

Un nodo vicino $K$ è un vicino accettabile per il router $R$ se e solo se la sua distanza verso la destinazione $D$ è più piccola della distanza che il router $R$ aveva prima del cambiamento di stato:

d\left(K,D\right)<d\left(R,D\right)

Ciò garantisce che il vicino $K$ può raggiungere la destinazione $D$ utilizzando un percorso che non passa per il router $R$ : se il percorso $K\rightarrow D$ passasse da $R$ , il suo costo non potrebbe essere inferiore a quello del sottopercorso $R\rightarrow D$ .

In caso esista più di un vicino accettabile, viene selezionato il vicino $X$ che offre il percorso a più basso costo verso la destinazione $D$ :

\min {\{L\left(R,X\right)+d\left(X,D\right)\}}

dove:

$L\left(R,X\right)$ è il costo del link tra il router $R$ e il suo vicino $X$ ;
$d\left(X,D\right)$ è la distanza tra il vicino $X$ e la destinazione $D$ .

Il vicino accettabile selezionato non è garantito essere il vicino attraverso il quale passa il percorso migliore possibile verso la destinazione. Se il meccanismo non seleziona il vicino migliore, quest'ultimo continuerà ad annunciare il percorso veramente migliore senza variare il suo costo → il router riconoscerà l'esistenza di un nuovo percorso migliore che non era stato selezionato e adotterà il nuovo percorso (cambiamento di stato positivo).

Processo di diffusione

Se il router $R$ non riesce a trovare alcun vicino accettabile per la destinazione:

congela temporaneamente la entry nella tabella di instradamento relativa alla destinazione → i pacchetti continuano a prendere il percorso vecchio, che di sicuro è privo di cicli e al più non è più in grado di condurre a destinazione;
entra in uno stato attivo:
1. invia a ognuno dei suoi vicini, eccetto il next hop del percorso vecchio, un messaggio di query chiedendo a esso se riesce a trovare un percorso che sia migliore del suo percorso vecchio e che sia sicuramente privo di cicli;
2. attende la ricezione di un messaggio di reply da ognuno dei suoi vicini;
3. sceglie il percorso migliore uscendo dallo stato attivo.

Ogni router vicino $X$ che riceve il messaggio di query dal router $R$ invia in risposta un messaggio di reply contenente il suo DV relativo a un percorso attraverso di esso:

se il router $R$ non è il suo next hop verso la destinazione, e quindi il costo del suo percorso verso la destinazione non è cambiato, allora il router $X$ segnala che il router $R$ può usare quel percorso;
se il router $R$ è il suo next hop verso la destinazione, allora il router $X$ deve mettersi a sua volta alla ricerca di un percorso nuovo, selezionando un vicino accettabile o entrando anch'esso nello stato attivo.

Vantaggi e svantaggi

Vantaggi

molto facile da implementare, e i protocolli basati sull'algoritmo DV sono semplici da configurare;
richiede risorse di elaborazione limitate → hardware nei router economico;
adatto per reti piccole e stabili con cambiamenti di stato negativi non troppo frequenti;
l'algoritmo DUAL garantisce reti libere da cicli: non possono avvenire routing loop, neanche nel transitorio (anche se i buchi neri sono ancora tollerati).

Svantaggi

l'algoritmo ha un caso peggiore esponenziale e ha un funzionamento normale tra $O\left(n^{2}\right)$ e $O\left(n^{3}\right)$ ;
la convergenza può essere piuttosto lenta, proporzionale al link più lento e al router più lento nella rete;
difficile capire e predire il suo comportamento nelle reti grandi e complesse: nessun nodo ha una mappa della rete → è difficile rilevare eventuali routing loop;
può scatenare routing loop dovuti a particolari cambiamenti nella topologia;
le tecniche aggiuntive per migliorare il suo funzionamento rendono il protocollo più complesso, e comunque non risolvono completamente il problema della mancanza di conoscenza della rete;
la soglia "infinito" limita l'utilizzo di questo algoritmo alle sole reti piccole (ad es. con pochi hop).

L'algoritmo Path Vector

L'algoritmo Path Vector (PV) aggiunge informazioni sulle rotte annunciate: viene annunciato anche il percorso, ovvero la lista dei nodi attraversati lungo di esso:

La lista dei nodi attraversati permette di evitare la comparsa di routing loop: il nodo ricevente è in grado di rilevare che la rotta annunciata passa attraverso di esso osservando la presenza del suo identificativo nella lista, scartandola invece di propagarla → non possono formarsi percorsi che passano due volte per lo stesso nodo.

Il Path Vector è un algoritmo intermedio tra il Distance Vector e il Link State: aggiunge le informazioni strettamente necessarie sui percorsi annunciati senza avere la complessità associata al Link State dove è necessario conoscere l'intera topologia della rete.

Applicazione

L'algoritmo PV viene utilizzato nell'instradamento inter-dominio dal protocollo BGP: B5. Border Gateway Protocol#Algoritmo Path Vector.