Reti di TelecomunicazioneLezione 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

• 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}

1

2

28

7

1

A

B C

E D

DE() A B DA 1 14 5B 7 8 5C 6 9 4D 4 11 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)

– a stabilità raggiunta, ogni tabella contiene la lunghezza del percorso minimo da E a C passando per x

• 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

2

28

7

1

A

B C

E D

DE() A B DA 1 14 5B 7 8 5C 6 9 4D 4 11 2

Algoritmo distance vector// Al nodo Xfor ( 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

1

7

2

Y

X Z

DX Y Z

Y 2 Z 7

Dy Y Z

X 2 Z 1

Dz Y Z

X 7 Y 1

Esempio

1

7

2

Y

X Z

DX Y Z

Y 2 Z 7

Dy Y Z

X 2 Z 1

Dz Y Z

X 7 Y 1

DX Y Z

Y 2 8Z 3 7

Dy Y Z

X 2 8Z 9 1

Dz Y Z

X 7 3Y 9 1

Esempio

1

7

2

Y

X Z

DX Y Z

Y 2 Z 7

Dy Y Z

X 2 Z 1

Dz Y Z

X 7 Y 1

DX Y Z

Y 2 8Z 3 7

Dy Y Z

X 2 8Z 9 1

Dz Y Z

X 7 3Y 9 1

DX Y Z

Y 2 8Z 3 7

Dy Y Z

X 2 8Z 9 1

Dz Y Z

X 7 3Y 9 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 internorouter 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-ASrotta 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?