Algoritmi di instradamento

informazioni con i nodi adiacenti, un nodo gradualmente calcola il percorso a costo

minimo verso una destinazione o un insieme di destinazioni. L’algoritmo

d’instradamento decentralizzato è chiamato algoritmo a vettore distanza, DV,

poiché ogni nodo elabora un vettore di stima dei costi (distanze) verso tutti gli altri

nodi nella rete.

Un secondo criterio per classificare gli algoritmi d’instradamento riguarda il fatto di essere

statici o dinamici. Negli algoritmi d’instradamento statici i cammini cambiano molto

raramente. Gli algoritmi d’instradamento dinamici invece determinano gli instradamenti

al variare del volume di traffico o della topologia della rete. Gli algoritmi dinamici

rispondono meglio ai cambiamenti della rete, ma sono anche più soggetti a problemi.

Un terzo modo per classificare gli algoritmi d’instradamento è il fatto di essere sensibili al

carico o meno.

In un algoritmo sensibile al carico, i costi dei collegamenti variano dinamicamente per

riflettere il livello corrente di congestione del collegamento sottostante. Se si associa un

alto costo a un collegamento attualmente trafficato, un algoritmo d’instradamento tenderà

ad evitare di percorrerlo. Gli attuali algoritmi d’instradamento Internet (quali RIP, OSPF e

BGP) sono insensibili al carico, dato che il costo di un collegamento non riflette

esplicitamente il suo attuale (o recente) livello di congestione.

Algoritmo d’instradamento a stato del collegamento (LS)

La topologia di rete e tutti i costi dei collegamenti sono noti, ossia disponibili in input

all’algoritmo LS. Ciò si ottiene facendo inviare a ciascun nodo pacchetti di stato del

collegamento a tutti gli altri nodi della rete. Questi pacchetti contengono identità e costi

dei collegamenti connessi al nodo che li invia. L’algoritmo d’instradamento a stato del

collegamento che presentiamo ora è noto come algoritmo di Dijkstra, dal nome del suo

ideatore. Esso calcola il cammino a costo minimo da un nodo (l’origine, che chiameremo

u) a tutti gli altri nodi nella rete, è iterativo e ha le seguenti proprietà: dopo la k-esima

iterazione, i cammini a costo minimo sono noti a k nodi di destinazione, e tra i percorsi a

costo minimo verso tutti i nodi di destinazione, questi k cammini hanno i k costi più bassi.

Definiamo la seguente notazione.

D(v): costo minimo del cammino dal nodo origine alla destinazione v per quanto

 concerne l’iterazione corrente dell’algoritmo.

p(v): immediato predecessore di v lungo il cammino a costo minimo dall’origine a

 v.

N’: sottoinsieme di nodi che contiene tutti (e solo) i nodi v per cui il cammino a

 costo minimo dall’origine a v è definitivamente noto.

L’algoritmo globale d’instradamento consiste in un passo d’inizializzazione seguito da un

ciclo che viene eseguito una volta per ogni nodo del grafo. Quando termina, l’algoritmo

avrà calcolato il cammino minimo dal nodo origine u a tutti gli altri nodi.

Algoritmo LS dal nodo origine u

1 Inizializzazione:

2 N'={u} 2

3 per tutti i nodi v

4 se v è adiacente ad u

5 allora D(v)=c(u,v)

6 altrimenti D(v)=∞

7

8 Ciclo

9 determina un w non in N' tale che D(w) sia minimo

10 aggiungi w a N'

11 aggiorna D(v) per ciascun nodo v adiacente a w e non in N' :

12 D(v)= min((D(v),D(w)+c(w,v))

13 /* il nuovo costo verso v è il vecchio costo verso v oppure il costo del cammino

14 minimo noto verso w più il costo da w a v */

15 finché N'=N.

Ad esempio consideriamo la rete nella figura e calcoliamo i percorsi a costo minimo da u a

tutte le destinazioni.

1. Nel passo d’inizializzazione, i valori dei cammini a costo minimo noti da u ai suoi

nodi adiacenti, v, w e x, sono posti rispettivamente a 2, 5 e 1. In particolare il costo

verso w vale 5 dato che questo è il costo del collegamento diretto (un hop) da u a

w. I costi verso y e z sono posti a infinito dato che tali nodi non sono adiacenti a u.

2. Nella prima iterazione, prendiamo in considerazione i nodi non ancora aggiunti

all’insieme N’ e determiniamo il nodo a costo minimo come alla fine della

precedente iterazione. Tale nodo è x, di costo 1, e pertanto x viene aggiunto

all’insieme N’. Viene poi eseguita la riga 12 dell’algoritmo LS per aggiornare D(v)

per tutti i nodi, ottenendo i risultati mostrati nella seconda riga (passo 1) della

tabella. Il costo del cammino verso v non è cambiato. Il costo del cammino verso w

(che era 5 al termine dell’inizializzazione) passando per il nodo x è diventato 4.

Viene quindi selezionato questo cammino a costo inferiore e il predecessore di w

lungo il cammino minimo da u diventa x. In modo simile, il costo verso y

(attraverso x) viene calcolato essere 2, e la tabella viene aggiornata di conseguenza.

3. Nella seconda iterazione, si trova che i nodi v e y hanno cammini a costo minimo

(2), ne scegliamo arbitrariamente uno e aggiungiamo y all’insieme N’ che ora

conterrà u, x e y. I costi verso i nodi rimanenti non ancora in N’, ossia v, w e z sono

aggiornati dalla riga 12 dell’algoritmo LS, ottenendo i risultati mostrati nella terza

riga della tabella.

4. E così via….

Tabella di esecuzione dell’algoritmo LS sulla rete della figura

passo N’ D(v), p(v) D(w), p(w) D(x), p(x) D(y), p(y) D(z), p(z)

0 u 2, u 5, u 1, u ∞ ∞

1 ux 2, u 4, x 2, x ∞

2 uxy 2, u 3, y 4, y

3 uxyv 3, y 4, y

4 uxyvw 4, y 3

5 uxyvwz

Quando l’algoritmo LS termina, abbiamo per ciascun nodo il suo predecessore lungo il

cammino a costo minimo dal nodo origine. Per ciascun predecessore, abbiamo il rispettivo

predecessore, e in questo modo riusciamo a costruire l’intero percorso dall’origine a tutte

le destinazioni. La tabella d’inoltro in un nodo, diciamo u, può pertanto essere costruita da

queste informazioni memorizzando, per ciascuna destinazione, il nodo del successivo hop

sul cammino a costo minimo da u alla destinazione. Complessivamente il numero totale di

nodi da cercare in tutte le iterazioni è n(n+1)/2.

Algoritmo d’instradamento con vettore distanza (DV)

Mentre LS usa informazioni globali, l’algoritmo con vettore distanza, DV, è iterativo,

asincrono e distribuito. E’ distribuito nel senso che ciascun nodo riceve parte

dell’informazione da uno o più dei suoi vicini direttamente connessi cui, dopo aver

effettuato il calcolo restituisce i risultati. E’ iterativo nel senso che questo processo si ripete

fino a quando non avviene ulteriore scambio informativo tra vicini. Aspetto interessante,

l’algoritmo è anche auto-terminante: non vi è alcun segnale che il calcolo debba fermarsi,

semplicemente si blocca. L’algoritmo è asincrono nel senso che non richiede che tutti i

nodi operino al passo con gli altri. Discutiamo ora la relazione esistente tra costi e percorsi

a costo minimo. Sia d(y) il costo del percorso a costo minimo dal nodo x al nodo y. Allora i

costi minimi sono correlati dalla nota formula di Bellman-Ford:

d(y)=min{c(x,v)+d(y)}

dove min riguarda tutti i vicini di x. Tale relazione è piuttosto intuitiva. Infatti se, dopo

aver viaggiato da x a v, consideriamo il percorso a costo minimo da v a y, il costo del

cammino sarà c(x,v)+d(y). Dato che dobbiamo iniziare viaggiando verso qualche vicino v,

il costo minimo da x a y è il minimo di c(x,v)+d(y) calcolato su tutti i nodi adiacenti v.

L’idea di base è la seguente. Ciascun nodo x inizia con D(y), una stima del costo del

percorso a costo minimo da se stesso al nodo y, per tutti i nodi in N. Sia D=[D(y):y in N] il

vettore distanza del nodo x, che è il vettore delle stime dei costi da x a tutti gli altri nodi, y,

in N. Con l’algoritmo DV, ciascun nodo x mantiene i seguenti dati d’instradamento.

 Per ciascun vicino v, il costo c(x,v) da x a v

 Il vettore distanza del nodo x, che è D=[D(y):y in N], contenente la stima presso x

del costo verso tutte le destinazioni, y, in N.

 I vettori distanza di ciascuno dei suoi vicini, ossia D=[D(y):y in N], per ciascun

vicino y di x.

In questo algoritmo distribuito e asincrono, di quando in quando un nodo invia una copia

del proprio vettore distanza a ciascuno dei suoi vicini. Quando un nodo x riceve un nuovo

vettore distanza da qualcuno dei suoi vicini v, lo salva e quindi usa la formula di Bellman-

Ford per aggiornare il proprio vettore distanza come segue: 4

D(y)=min{c(x,v)+D(y)} per ciascun nodo y in N

Se il vettore distanza del nodo x è cambiato per via di tale passo di aggiornamento, il nodo

x manderà il proprio vettore distanza aggiornato a ciascuno dei suoi vicini, i quali a loro

volta aggiornano il proprio vettore distanza.

Algoritmo con vettore distanza

A ciascun nodo x:

1 Inizializzazione:

2 per tutte le destinazioni y in N:

3 D(y)=c(x,y)/* se y non è adiacente, allora c(x,y)= */

4 per ciascun vicino w

5 D(y)= per tutte le destinazioni y in N

6 per ciascun vicino w

7

8 invia il vettore distanza D=[D(y): y in N] a w

9 Ciclo

10 attendi (finché vedi cambiare il costo di un collegamento verso

11 qualche vicino w o finché richiedi un vettore distanza

12 da qualche vicino w)

13 per ogni y in N:

14 D(y)=minv { c(x,v)+Dv(y)}

15

16 se D(y) è cambiato per qualche destinazione y

17 invia il vettore distanza D=[D(y):y in N] a tutti i vicini

18

19 continua

L’algoritmo DV mostra come un nodo x aggiorni la propria stima del vettore distanza

quando vede il cambiamento di costo in uno dei collegamenti direttamente connessi o

quando riceve da qualche vicino un vettore distanza aggiornato. Ma per aggiornare la

propria tabella d’inoltro per una data destinazione y, ciò che il nodo x ha davvero bisogno

di sapere non è la distanza sul percorso minimo verso y bensì il nodo vicino v*(y) che

rappresenta il router dell’hop successivo lungo il percorso più breve verso y. Come ci si

potrebbe aspettare, il router del successivo hop v*(y) è il vicino v che ottiene il minimo

nella riga 14 dell’algoritmo DV. Se esistono più vicini v che ottengono il minimo, allora

v*(y) può essere uno qualunque tra questi. Pertanto, nelle righe 13 e 14, per ciascuna

destinazione y il nodo x determina anche v*(y) e aggiorna la propria tabella d’inoltro per

la destinazione y.

Ricordiamo che l’algoritmo LS è globale nel senso che richiede a ciascun nodo di ottenere

innanzitutto una mappa completa della rete prima di mandare in esecuzione l’algoritmo

di Dijkstra. L’algoritmo DV è invece decentralizzato e non usa tale informazione globale.

Infatti le sole informazioni ottenute dal nodo sono il costo dei collegamenti verso i vicini

direttamente connessi e quelle ricevute da questi vicini. Ogni nodo attende aggiornamenti

5

dai suoi vicini (righe 10 e 11), quando riceve un aggiornamento calcola il proprio nuovo

vettore distanza (riga 14) e lo distribuisce ai suoi vicini (righe 16 e 17).

Esempio

figura

La illustra il funzionamento dell’algoritmo DV in una rete a tre nodi. Il

funzionamento dell’algoritmo viene mostrato in modo sincrono, in quanto tutti i nodi

ricevono simultaneamente i vettori distanza dai propri vicini, calcolano i rispettivi nuovi

vettori distanza e informano i vicini degli eventuali cambiamenti. Dopo aver studiato

questo esempio, vi dovreste convincere che l’algoritmo opera correttamente anche in

modo asincrono, con calcoli ai nodi e generazione e ricezione di aggiornamenti in qualsiasi

istante.

La colonna di sinistra della figura mostra tre tabelle d’instradamento iniziali per ciascuno

dei tre nodi (ad esempio, in alto a sinistra è indicata quella del nodo x). All’interno di una

specifica tabella d’instradamento, le righe rappresentano i vettori distanza: più

precisamente, la tabella d’instradamento di ciascun nodo include il proprio vettore

distanza e quello dei suoi vicini. Pertanto, la prima riga nella tabella d’instradamento

iniziale del nodo x è D=[D(x),D(y),D(z)]=[0,2,7]. La seconda e la terza riga di questa tabella

rappresentano i vettori distanza ricevuti più di recente rispettivamente dai nodi y e z.

Poiché al momento dell’inizializzazione il nodo x non ha ricevuto nulla dai nodi y e z, i

valori della seconda e della terza riga sono posti a infinito.

Dopo l’inizializzazione, ciascun nodo invia il proprio vettore distanza ai suoi vicini come