Routing
Crediti
Parte delle slide seguenti sono adattate dalla
versione originale di J.F Kurose and K.W. Ross
(© 1996-2003 All Rights Reserved)
4-1
Routing
Routing protocol
Obiettivo: determinare un
“buon” percorso (sequenza di
router) attraverso la rete
da sorgente a destinazione
Teoria dei grafi usata per
gli algoritmi di routing
 i nodi del grafo sono i
router
 gli archi del grafo sono i
link fisici

costo del link: distanza,
costo economico, livello di
congestione, …
5
2
A
B
2
1
D
3
C
3
1
5
F
1
E
2
 “buon” percorso:
 tipicamente significa a
costo minimo
 possibili altre definizioni
4-2
Classificazione algoritmi di routing
Informazione globale
o decentralizzata
Globale
 tutti i router hanno
informazione completa su
topologia e costi dei link
 “link state” algorithms
Decentralizzata
 i router conoscono i costi
dei link dei vicini
fisicamente connessi
 processo di calcolo
interattivo, scambio di
informazioni con i vicini
 “distance vector” algorithms
Statico o dinamico
Statico
 i percorsi cambiano
lentamente nel tempo
Dinamico
 i percorsi cambiano più
velocemente
 aggiornamento
periodico in risposta
ai cambi di costo
dei link
4-3
Algoritmo di routing Link-State
Algoritmo di Dijkstra
 topologia della rete e costi dei
link conosciuti per tutti i nodi
 realizzato attraverso “link
state broadcast”
 tutti i nodi hanno le stesse
informazioni
 calcola i percorsi a costo
minore da un nodo (sorgente)
a tutti gli altri nodi
 fornisce la routing table
per quel nodo
 iterativo: dopo k iterazioni,
determina i percorsi a costo
minore per k destinazioni
Notazioni:
 c(i,j): costo link dal nodo i
al nodo j. Costo infinito se i
e j non direttamente
connessi
 D(v): valore corrente del
costo del percorso (a minor
costo) dalla sorgente al
nodo v
 p(v): nodo precedente
lungo il percorso a minor
costo dalla sorgente a v
 N: insieme di nodi il cui
percorso a costo minore è
definitivamente conosciuto
4-4
Algoritmo di Dijsktra
1 Initialization:
2 N = {A}
3 for all nodes v
4
if v adjacent to A
5
then D(v) = c(A,v)
6
else D(v) = ∞
7
8 Loop
9 find w not in N such that D(w) is a minimum
10 add w to N
11 update D(v) for all v adjacent to w and not in N:
12
D(v) = min( D(v), D(w) + c(w,v) )
13 /* new cost to v is either old cost to v or known
14 shortest path cost to w plus cost from w to v */
15 until all nodes in N
4-5
Algoritmo di Dijkstra: esempio
Step
0
1
2
3
4
5
start N
A
AD
ADE
ADEB
ADEBC
ADEBCF
D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F)
2,A
1,A
5,A
∞
∞
2,A
4,D
2,D
∞
2,A
3,E
4,E
3,E
4,E
4,E
5
2
A
B
2
1
D
3
C
3
1
5
F
1
E
2
4-6
Algoritmo di Dijkstra: considerazioni
Complessità algoritmo: n nodi
 ogni iterazione: controlla tutti i nodi w non in N
 n*(n+1)/2 controlli: O(n2)
 possibile un’implementazione più efficiente: O(nlogn)
Possibili oscillazioni:
 es. costo link = traffico trasportato
D
1
1
0
A
0 0
C
e
1+e
B
e
2+e
D
0
1
inizialmente
A
1+e 1
C
0
B
0
… ricalcola
routing
0
D
1
A
2+e
0 0
B
C 1+e
… ricalcola
2+e
D
0
A
1+e 1
C
0
B
e
… ricalcola
4-7
Algoritmo Distance Vector
Iterativo:
 continua finchè nessun
nodo scambia più
informazioni
 auto-terminante: nessun
“segnale” di stop
Asincrono:
 i nodi non devono
Tabella delle distanze
 ogni nodo ha la sua
 una riga per ogni possibile
destinazione
 una colonna per ogni nodo vicino
direttamente collegato
 esempio: nel nodo X, per dest. Y
attraverso il vicino Z:
scambiare info o
procedere in sincronismo!
Distribuito:
 ogni nodo comunica solo
con i vicini direttamente
collegati
X
D (Y,Z)
distanza da X a
= Y, via Z come next hop
= c(X,Z) + min {DZ(Y,w)}
w
4-8
Tabella distanze: esempio
7
A
B
1
C
E
cost to destination via
D ()
A
B
D
A
1
14
5
B
7
8
5
C
6
9
4
D
4
11
2
2
8
1
E
2
D
E
D (C,D) = c(E,D) + min {DD(C,w)}
= 2+2 = 4
w
E
D (A,D) = c(E,D) + min {DD(A,w)}
E
w
= 2+3 = 5
loop!
D (A,B) = c(E,B) + min {D B(A,w)}
= 8+6 = 14
w
loop!
4-9
Distance table fornisce routing table
E
cost to destination via
Outgoing link
D ()
A
B
D
A
1
14
5
A
A,1
B
7
8
5
B
D,5
C
6
9
4
C
D,4
D
4
11
2
D
D,2
Distance table
to use, cost
Routing table
4-10
Distance Vector Routing: generalità
Iterativo, asincrono: ogni
iterazione locale causata
da:
 modifica costo link locale
 messaggio dal vicino: il suo
percorso a costo minore è
cambiato
Distribuito:
 ogni nodo notifica i vicini
solo quando cambia il suo
percorso a costo minore
verso una qualunque
destinazione

Ad ogni nodo:
wait for (change in local link
cost or msg from neighbor)
recompute distance table
if least cost path to any dest
has changed, notify
neighbors
i vicini notificano i loro
vicini solo se necessario
4-11
Algoritmo Distance Vector: Bellman-Ford
Per tutti i nodi X:
1 Initialization:
2 for all adjacent nodes v:
3
D X(*,v) = ∞
/* the * operator means "for all rows" */
4
D X(v,v) = c(X,v)
5 for all destinations, y
6
send min D X(y,w) to each neighbor /* w over all X's neighbors */
w
4-12
Distance Vector Algorithm (cont.):
8 loop
9 wait (until I see a link cost change to neighbor V
10
or until I receive update from neighbor V)
11
12 if (c(X,V) changes by d)
13 /* change cost to all dest's via neighbor V by d */
14 /* note: d could be positive or negative */
15 for all destinations y: D X(y,V) = D X(y,V) + d
16
17 else if (update received from V wrt destination Y)
18 /* shortest path from V to some Y has changed */
19 /* V has sent a new value for its min DV(Y,w) */
w
20 /* call this received new value "newval" */
21 for the single destination y: D X(Y,V) = c(X,V) + newval
22
23 if we have a new min DX(Y,w) for any destination Y
w
24
send new value of min D X(Y,w) to all neighbors
w
25
26 forever
4-13
Distance Vector Algorithm: esempio
X
2
Y
7
1
Z
X
Z
X
Y
D (Y,Z) = c(X,Z) + minw{D (Y,w)}
= 7+1 = 8
D (Z,Y) = c(X,Y) + minw {D (Z,w)}
= 2+1 = 3
4-14
Distance Vector Algorithm: esempio (cont.)
X
2
Y
7
1
Z
4-15
Distance Vector: variazione costi nei link
Costo del link diminuisce:
 nodo rileva variaz. costo link locale
 aggiorna distance table
 se il costo cambia nel percorso a
costo minore, informa i vicini
“solo”
due
itera
zioni
1
X
4
Y
50
1
Z
algoritmo
termina
4-16
Distance Vector: variazione costi nei link
Costo del link aumenta:
 Percorso ciclico, per raggiungere X:


Y passa attraverso Z
Z passa attraverso Y
 conteggio all’infinito
60
X
4
Y
50
1
Z
algoritmo
continua!
4-17
Distance Vector: poisoned reverse
Se Z instrada attraverso Y per
raggiungere X:
 Z informa Y che la distanza da Z a X è
infinita (così Y non instrada verso X via Z)
 non risolve completamente il problema del
conteggio all’infinito
60
X
4
Y
50
1
Z
algoritmo
termina
4-18
Confronto tra gli algoritmi LS e DV
Complessità del messaggio
 LS: con n nodi ed E link, inviati
O(nE) messaggi
 DV: scambio solo tra vicini
 tempo di convergenza varia
Velocità di convergenza
 LS: Algoritmo O(n2) richiede
O(nE) messaggi
 può avere oscillazioni
 DV: tempo di convergenza
varia
 può avere percorsi ciclici
 problema di conteggio
all’infinito
Robustezza: cosa accade se
il router non funziona?
LS:


un nodo può trasmettere
un costo del link
incorretto
ogni nodo calcola la sua
tabella
DV:


un nodo può trasmettere
un costo di percorso
incorretto
tabella di ogni nodo usata
da altri iterativamente
• errore si propaga
attraverso la rete
4-19