Reti di Telecomunicazione
Lezione 16
Corso di reti per le telecomunicazioni
Programma della lezione
• Algoritmo di instradamento distance vector
– algoritmo di base
– variazioni nei costi e guasti
– poisoned reverse
• Confronto tra gli algoritmi di instradamento
– complessità
– velocità di convergenza
– robustezza
• Instradamento gerarchico
– autonomous system
Algoritmo distance vector
• L’algoritmo distance vector è iterativo, asincrono e distribuito
– ogni nodo è provvisto di una tabella delle distanze
• una riga per ogni destinazione di rete
• una colonna per ciascuno dei vicini direttamente collegati al nodo
– l’algoritmo riempie la tabella di ogni nodo con le distanze minime per
raggiungere dal nodo la destinazione in riga passando per il nodo in
colonna
– ogni nodo esegue una computazione, usando le informazioni provenienti
dai vicini, e le varie esecuzioni cooperano (algoritmo distribuito)
– le esecuzioni delle computazioni da parte dei vari nodi non avvengono
tutte contemporaneamente, ma concorrentemente (algoritmo asincrono)
– il processo complessivo converge, terminando nel momento in cui tutti i
nodi hanno una corretta tabella delle distanze (algoritmo iterativo)
• l’arresto dell’algoritmo è automatico: quando nessuno è più in grado di
aggiornare la propria tabella, l’algoritmo è concluso
Algoritmo distance vector
•
L’elemento alla riga X e colonna Y
della tabella delle distanze del
nodo E, DE(X,Y), denota la
distanza da E a X, passando per Y
B
1
7
8
A
1
•
•
E
Inizialmente, ogni nodo E conosce
la distanza dai propri vicini ed
assume che gli altri nodi siano
inaccessibili
– DE(X,X) = c(E,X)
– tutti gli altri elementi sono 
Successivamente, la tabella viene
aggiornata come
DE(X,Y) = c(E,Y) +
+ min{DZ(X,w) | w vicino di X}
C
DE()
A
B
C
D
A
1
7
6
4
2
2
D
B
14
8
9
11
D
5
5
4
2
Algoritmo distance vector
•
Quando l’algoritmo raggiunge la
stabilità, il percorso minimo da E a
C si ottiene cercando il valore
minimo nella riga C della tabella
DE(C,x)
B
•
A tale valore corrisponde la
colonna D
Il datagram verrà indirizzato al
router D, il quale procederà nello
stesso modo di E
– il percorso è individuato in modo
distribuito: ogni router contiene il
miglior prossimo passo
1
7
8
A
1
– a stabilità raggiunta, ogni tabella
contiene la lunghezza del
percorso minimo da E a C
passando per x
•
C
E
DE()
A
B
C
D
A
1
7
6
4
2
2
D
B
14
8
9
11
D
5
5
4
2
Algoritmo distance vector
// Al nodo X
for ( V adiacente ad X ) {
DX(V,V) = c(X,V);
for (Y diverso da V) DX(Y,V) = ; }
for ( Y possibile destinazione )
for ( V adiacente a X )
send “D(X,Y) = min{DX(Y,w) | w vicino di X}” a V;
while( true ) {
wait( messaggio da un vicino V );
if ( messaggio == “c(X,V) = c(X,V) + d” )
// variazione costo link
DX(Y,V) = DX(Y,V) + d;
else
// messaggio == “D(V,Y) = newval”
DX(Y,V) = c(X,V) + newval;
if (il valore di min{DX(Y,w) | w vicino di X} è cambiato )
for ( V adiacente a X )
send “D(X,Y) = min{DX(Y,w) | w vicino di X}” a V;
}
Esempio
Y
2
X
1
Z
7
DX
Y
Z
Dy
Y
Z
Dz
Y
Z
Y
Z
2


7
X
Z
2


1
X
Y
7


1
Esempio
Y
2
X
1
Z
7
DX
Y
Z
Dy
Y
Z
Dz
Y
Z
Y
Z
2


7
X
Z
2


1
X
Y
7


1
DX
Y
Z
Dy
Y
Z
Dz
Y
Z
Y
Z
2
3
8
7
X
Z
2
9
8
1
X
Y
7
9
3
1
Esempio
Y
2
X
1
Z
7
DX
Y
Z
Dy
Y
Z
Dz
Y
Z
Y
Z
2


7
X
Z
2


1
X
Y
7


1
DX
Y
Z
Dy
Y
Z
Dz
Y
Z
Y
Z
2
3
8
7
X
Z
2
9
8
1
X
Y
7
9
3
1
DX
Y
Z
Dy
Y
Z
Dz
Y
Z
Y
Z
2
3
8
7
X
Z
2
9
8
1
X
Y
7
9
3
1
Variazione di costo dei link
• Quando avviene una variazione di costo in un link, l’algoritmo
distance vector
– aggiorna la propria tabella delle distanze
– se questa variazione è significativa, ovvero se modifica una qualche
distanza minima, invia un messaggio ai vicini
– per l’asincronia dell’algoritmo, esso inizierà a convergere verso un nuovo
insieme di percorsi minimo
• Se un link si guasta, si può usare un trucco:
– basta segnalare un cambiamento nel costo del link guasto: dal valore
precedente a infinito
Poisoned reverse
• Studiando il tempo di propagazione di una variazione di costo di
un link, si scopre che:
– le buone notizie (riduzioni dei costi) viaggiano velocemente
– le cattive notizie (aumento dei costi) viaggiano lentamente
• il problema nasce dal fatto che l’algoritmo considera anche percorsi ciclici,
ovviamente inutili; tuttavia, si può dimostrare che, solo quando i dati sono
stabili, i percorsi ciclici vengono sicuramente eliminati
• Per evitare il problema di propagazione lenta, si usa una tecnica
nota come poisoned reverse:
– se Z instrada i datagram attraverso Y per raggiungere X, allora Z
informerà Y che la distanza da Z a X è infinita
• questa tecnica previene i percorsi ciclici tra due nodi, ma non i cicli che
coinvolgono più di due nodi
Confronto
• I parametri di confronto tra gli algoritmi di instradamento visti
sono:
– efficienza (in termini di scambio di messaggi):
• l’algoritmo di Dijkstra richiede O(n·E) messaggi, con n numero di nodi ed E
numero di link, in modo che ciascun nodo della rete conosca il costo di
ciascun link
• in Distance Vector, ogni nodo invia messaggi solo ai propri vicini, quindi il
costo di comunicazione dipende dal numero di iterazioni dell’algoritmo e dalla
topologia della rete
• tuttavia, in pratica, Distance Vector, su reti ragionevoli come topologia e con
un range di costi piccolo, tende a non scambiare molti messaggi
• quindi, nessuno dei due algoritmi è definitivamente migliore dell’altro, in
questo senso
Confronto
• I parametri di confronto tra gli algoritmi di instradamento visti
sono:
– efficienza (in termini di velocità di convergenza)
• nel caso dell’algoritmo di Dijkstra, si può mostrare che, con una opportuna
codifica, esso richiede O(n2) passi di computazione, con n numero di nodi
• nel caso dell’algoritmo Distance Vector, il costo in termini di passi di calcolo è
difficile da valutare, dipendendo dal valore dei costi dei link
• tuttavia, in pratica, Distance Vector, su reti ragionevoli come topologia e con
un range di costi piccolo, tende a convergere abbastanza in fretta
• quindi, ancora una volta, nessuno dei due algoritmi è certamente superiore
all’altro
Confronto
• I parametri di confronto tra gli algoritmi di instradamento visti
sono:
– robustezza
• in caso di guasti a nodi o a link, l’algoritmo di Dijkstra, essenzialmente,
richiede di ricomputare tutti i percorsi minimi
• invece, l’algoritmo Distance Vector può gestire la situazione, a patto di
considerare il problema dei percorsi ciclici
• nel caso di informazioni errate sul costo di un link, per entrambi gli algoritmi,
queste influenzeranno solo i percorsi ottimi che contengono quel link
• nel caso dell’algoritmo di Dijkstra, questa informazione tenderà a restare
confinata nei nodi più vicini al link sbagliato, risparmiando gli altri
• nel caso di Distance Vector, invece, questa informazione verrà propagata, in
un certo qual senso, per tutta la rete
Confronto
• Complessivamente, possiamo dire che nessuno dei due algoritmi
è vincente sull’altro
– l’algoritmo di Dijkstra è più controllabile, più robusto rispetto alle
informazioni mantenute
– l’algoritmo di Distance Vector è più flessibile, spesso più efficiente e
genera spesso meno traffico
• Quindi la scelta tra i due algoritmi dipende dal tipo di
instradamento che stiamo cercando
– se vogliamo un instradamento su una rete con molta variabilità sulla
topologia, ma in cui le informazioni sono date correttamente, la scelta è
Distance Vector, che sopporta variazioni di topologia e di costi
– se vogliamo un routing efficiente su una rete abbastanza stabile, allora
l’algoritmo di Dijkstra è superiore, dal momento che effettua tutto il lavoro
una volta sola
Instradamento gerarchico
• Se una rete è formata da molte sottoreti, gli algoritmi di
instradamento visti sono inesorabilmente inefficienti
– essi computano la distanza minima tra due router della rete, per ogni
coppia di router
– quindi ogni router deve mantenere una tabella che ha un grande numero
di percorsi
• per entrambi gli algoritmi, la tabella finale contiene tante righe quanti sono i
percorsi
• Tuttavia, se la destinazione fosse una intera sottorete, allora
avrei un instradamento tra reti
– posso definire un router come interno o di frontiera
– i router di frontiera definiscono la rete, mentre i router interni fanno parte
delle sottoreti
Instradamento gerarchico
•
La divisione in router interni e di
frontiera rende scalabile il
problema dell’instradamento
– ogni sottorete risolve il problema
dell’instradamento al suo interno,
considerando i propri router di
frontiera come tutte le altre
destinazioni
– la rete delle reti risolve il problema
di instradamento solo tra i router
di frontiera, considerando questi
come la somma delle destinazioni
della sottorete
•
La divisione in sottoreti è comoda
per definire i confini amministrativi
delle organizzazioni
router interno
router di frontiera
Autonomous System
• Su Internet, una sottorete che sia visibile all’esterno come una
singola entità dal punto di vista dell’instradamento, è detta
Autonomous System (AS)
• In effetti, Internet è una rete di Autonomous System, almeno per
quanto riguarda i problemi di instradamento
• Esistono quindi protocolli di routing
– intra-autonomous system: si occupano di instradare i datagram tra nodi
dello stesso sistema, eventualmente delegando ai router di frontiera il
problema dell’instradamento se la destinazione è esterna
– inter-autonomous system: si occupano di instradare i datagram tra
sistemi, ovvero tra i loro router di frontiera
Autonomous System
•
L’instradamento di un datagram
avviene per parti:
– all’interno dell’autonomous system
di origine
– tra autonomous system intermedi
– all’interno dell’autonomous system
di destinazione
•
La rotta seguita può non essere
ottimale
– anzi, non è nemmeno garantito
che funzioni, potrebbe risultare
ciclica!
•
L’architettura risultante è
estremamente complessa, ma il
procedimento è scalabile
rotta inter-AS
rotta intra-AS
Autonomous System
• I protocolli di instradamento usati su Internet sono
– RIP (Routing Internet Protocol)
• intra-AS, basato su Distance Vector
– OSPF
• intra-AS, basato su Dijkstra
– BGP
• inter-AS, basato su Distance Vector
• Un protocollo di instradamento è un ibrido:
– agisce sul livello di rete
• le tabelle usate per l’instradamento sono strutture dati di questo livello
– computa sul livello applicazione
• i messaggi atti al suo funzionamento sono trasportati da UDP o TCP
Conclusione
• Questa lezione è tratta da:
– Kurose, cap. 4.2 e 4.3
• Esercizi:
– Provate l’algoritmo distance vector sulla rete a cinque elementi di queste
slide
– Provate a costruire un esempio che mostri come la propagazione di
cattive notizie in distance vector sia lenta
– Provate a costruire un esempio in cui la tecnica di poisoned reverse non
funzioni
– Discutete cosa si intende per destinazione in una rete con sottoreti. Come
è possibile indirizzare un insieme di nodi?