Instradamento in Rete

Accetta grafi con cammini caratterizzata da pesi solo positivi e ha come unico scopo

quello di trovare i cammini da tutti i nodi a un nodo destinazione.

A differenza dell’algoritmo di Bellman-Ford, ad ogni iterazione l’etichetta con peso

minore diventa permanente (a partire da quella della destinazione).

Complessità:

Bellman-Ford: O(N^3)

 Dijkstra: O(N^2)



Tipi di instradamento:

Globale: ogni router vede in modo completo la topologia della rete (tipico degli

 algoritmi Link State)

Decentralizzato: i router conoscono solo i vicini direttamente connessi a loro e

 il peso di questi link; le tabelle sono determinabili solo scambiando informazioni

con i nodi a cui i router sono connessi in modo diretto (tipico degli algoritmi

Distance Vector)

Algoritmi di instradamento a costo minimo

Distance Vector

Produce una tabella di instradamento in ogni nodo che specifica la minima distanza da

ogni altro nodo e quale next-hop a valle deve essere utilizzato; permette

un’implementazione centralizzata o distribuita, con quest’ultima che viene

generalmente preferita: il nodo riceve le stime delle distanze dai suoi vicini, vi

aggiunge la sua distanza dai vari vicini e scopre così il costo minimo del percorso

verso ogni altro nodo e il nodo a valle relativo.

Le informazioni scambiate tra i router sono contenute nei Distance Vector – DV – che

viene inviato solo ai nodi adiacenti in modo periodico (o nel caso di un cambiamento

topologico della rete); per la stima delle distanze viene utilizzato l’algoritmo di

Bellman-Ford distribuito.

Ogni nodo esegue un ricalcolo delle distanze quando riceve un DV diverso da quello

memorizzato oppure quando nasce/cade una linea attiva a cui è connesso.

Il Distance Vector risulta molto facile da implementare ma, di contro, sia ha:

Lentezza nella convergenza: il tempo necessario alla convergenza cresce in

 modo proporzionale al numero dei nodi

Limitazione di velocità imposta dal nodo più lento

 Loop che si possono instaurare dopo un cambiamento

 Comportamento difficilmente stabile su reti grandi

 Problema di stabilità (counting to infinity): si possono creare dei loop tra nodi

 nel caso in cui si rompano dei link; questo genere di problema può essere risolto

nei seguenti modi:

Hop Count Limit: si rappresenta il valore infinito con un numero maggiore

o del peso massimo di un percorso nella rete. Quando la distanza da un

nodo raggiunge tale valore il nodo viene marcato come non raggiungibile;

questo porta a una convergenza lenta verso uno stato stabile

Split-Horizon: ogni nodo manda messaggi di routing personalizzati sulle

o sue interfacce, con due possibili varianti:

Forma semplice: il nodo omette ogni informazione sulle

 destinazioni che raggiunge tramite quel link

Con Poisonous Reverse: il nodo include nel messaggio tutte le

 destinazioni ma pone a distanza infinita quelle raggiungibili tramite

quel link

Hold down (utilizzo dei contatori):

o Un router segna una rotta come non attiva (hold down) quando

 riceve un DV con distanza infinita per quella rotta oppure quando

non riceve il DV che segnala quella rotta dal nodo del primo hop

per un tempo T invalid

Le rotte poste in hold down non vengono annunciate nei DV (o

 vengono poste con costo infinito); inoltre non vengono considerati

validi per queste i DV ricevuti da altri nodi con metrica peggiore

ma solo eventuali DV migliorativi (e in questo caso la rotta esce

dall’hold down)

Dopo un tempo T la rotta viene cancellata

 flush

I triggered update sono le notifiche, inviate in modo istantaneo, di eventuali

cambiamenti nella rete che permettono di aumentare la velocità di convergenza e di

rendere noti in minor tempo i guasti.

Link State

Ogni nodo conosce le destinazioni a lui vicino e le distanze per raggiungerle, inviando

poi queste informazioni in flooding a tutti gli altri nodi della rete attraverso dei Link

State Packet (LSP); tutti i nodi mantengono un database di LSP e una mappa completa

della rete. Sulla base delle informazioni note vengono poi calcolati i cammini minimi

verso tutte le destinazioni.

Presenta dei vantaggi rispetto all’approccio Distance Vector: ogni nodo ha una mappa

completa della rete (e, questo, permette un routing ottimale), è necessario inviare gli

LSP solo dopo un cambiamento della rete e, per questo, i nodi sono subito informati di

eventuali cambiamenti nella rete.

Ha però anche degli svantaggi: è necessario utilizzare il flooding per la trasmissione

degli LSP così come per mantenere le informazioni sui vicini bisogna utilizzare un

protocollo dedicato (Hello); presenta inoltre una maggiore difficoltà

nell’implementazione e la necessità di ricevere un riscontro per i pacchetti inviati.