Seminario di Reti e Sicurezza Seminario di Reti e Sicurezza
algoritmi di instradamento algoritmi di instradamento
Star: Davide Ferrone
Prof. Stefano bistarelli
Premessa(1) Premessa(1)
Lo strato di rete ha lo scopo di trasportare un pacchetto da un host che spedisce ad uno che riceve
–
in particolare, il livello di trasporto fornisce allo strato di rete un segmento, indicando il mittente ed il
destinatario
–
il livello di rete deve decidere come fare a far giungere
tale pacchetto a destinazione, sapendo che il livello di
collegamento garantisce che ogni singolo passo (hop)
possa essere compiuto
Premessa(2) Premessa(2)
Obiettivi dello strato di rete
Determinazione del percorso:
lo strato di rete deve determinare il tragitto seguito dai pacchetti che fluiscono da un sender ad un receiver
algoritmi di instradamento: algoritmi per il calcolo del percorso
Commutazione:
quando un pacchetto arriva all’ingresso di un router, questo deve trasferirlo all’appropriato link di uscita Impostazione della chiamata (call setup):
impostazione dello stato dei nodi di rete prima dell’inizio della trasmissione dei dati non viene effettuata in
Internet
•Nelle reti datagram, come Internet, ogni pacchetto è contrassegnato dall’indirizzo del mittente e del
destinatario
–incidentalmente, un protocollo di livello rete deve fornire un modo di rappresentare questi indirizzi in modo da
identificare univocamente ogni host della rete
•I commutatori di pacchetto (router) basano la propria azione su una tabella di instradamento
(routing table) che, in base alla destinazione di un datagram, permette di scegliere il link di uscita
–la tabella di routing può variare nel tempo, in risposta alle politiche di instradamento della rete
–per questo motivo, i datagram possono seguire percorsi differenti nella rete e, eventualmente, arrivare fuori
sequenza
Instradamento
• L’idea di fondo è fare in modo che ogni datagram fluisca da – sorgente a destinazione, se sulla medesima rete
– da sorgente a router, e da router a destinazione altrimenti...
– … in mezzo, i router indirizzano il pacchetto ad un router più prossimo alla destinazione
G1 G3
W1
network 1 network 3
W2G2
W1 G1 data G1 G3 data G3 W2 data
network 2
Instradamento
•E’ necessario stabilire un percorso quando l’host
sorgente e l’host destinazione non appartengono alla stessa rete
–in tal caso, il livello di collegamento non permette lo scambio diretto di informazione
•Un terminale è solitamente connesso ad un router che si occupa di gestire il traffico destinato
all’esterno della rete
–questo router è detto router di default
–indicheremo d’ora in poi, come router sorgente il default router dell’host sorgente e come router destinazione il default router dell’host destinazione
•queste definizioni hanno senso in quanto il router sorgente non ha bisogno di un percorso per ricevere datagram dalla sorgente e, parimenti, il router destinazione non ha bisogno di percorsi per fornire datagram alla destinazione
Instradamento
•Un algoritmo di instradamento ha lo scopo di
disegnare un percorso tra un router sorgente ed un
router destinazione, dato un insieme di router collegati da link
–un buon algoritmo di instradamento non si limita a trovare un percorso, ma trova un buon percorso, secondo una
qualche metrica
–la descrizione data del problema lo porta nel dominio della teoria dei grafi: la rete di router è un grafo e si tratta di
trovare al suo interno, se esiste, un percorso tra due nodi dati –spesso gli archi del grafo sono pesati, ovvero ai vari link della rete viene associata una qualche misura della loro
desiderabilità
–quello che si richiede di trovare è solitamente il percorso che minimizza la somma dei costi dei vari link che ne fanno parte
•se assumiamo che ogni link abbia costo 1, allora stiamo
chiedendo di trovare il cammino più breve tra router sorgente e router destinazione
Instradamento
Instradamento nelle reti di dati Instradamento nelle reti di dati
Effetti Effetti
• L’algoritmo di instradamento influenza:
– Direttamente: il ritardo medio per pacchetto (average packet delay)
– Indirettamente: il throughput della rete, definito come:
Throughput=Traffico offerto – Traffico rifiutato
• I due parametri sono regolati dall’algoritmo di controllo di flusso: se il ritardo medio per pacchetto cresce
eccessivamente (cioè il routing è inefficace) il controllo di
flusso interviene riducendo il traffico ammesso nella rete
e quindi il throughput complessivo della rete.
Instradamento nelle reti di Instradamento nelle reti di
dati dati Effetti Effetti
• Un buon algoritmo di routing riesce ad aumentare il throughput a parità di
delay (per alti valori di traffico offerto) ed a diminuire il delay a parità di
throughput (per bassi valori di traffico offerto):
– Distribuito:
• Tutti i nodi si scambiano informazione tra loro (utilizzando protocolli di instradamento)
• Calcolano i percorsi (indipendentemente o in base a quanto fatto dai nodi adiacenti)
Vantaggi: Robusto ai guasti Scambio informazione uniforme su tutta la rete
Svantaggi: • Richiede intelligenza nei nodi • Scambio informazione parziale/errata porta a incongruenze nell’instradamento
Tipologie di instradamento (1)
•Esistono vari criteri per classificare gli algoritmi di routing
Calcolo percorso – Centralizzato:
• Un nodo si occupa di raccogliere l’informazione da tutti gli altri nodi
• Calcola i percorsi
• Ridistribuisce il risultato del calcolo a tutti gli altri nodi
Vantaggi: • Possibile usare di calcolo percorsi algoritmi e metriche complesse • Tutti i nodi usano piano di instradamento coerente
Svantaggi: • Sensibile al guasto nodo centrale • Scambio informazione da/verso nodo centralizzato genera congestione
–statico: i percorsi migliori sono calcolati o calcolabili a priori
–dinamico: i percorsi mutano nel corso del tempo in
funzione della variazione di topologia della rete o del costo dei link
Tipologie di Instradamento (2)
–globale: calcola il percorso di costo minimo supponendo di conoscere completamente la struttura della rete
•esempio: algoritmi basati sullo stato dei link
–decentralizzato (locale): il calcolo del miglior percorso viene eseguito localmente e parzialmente su ogni router;
solitamente, ogni router ha una conoscenza solo dei link e dei router cui è direttamente connesso
•esempio: algoritmi di tipo distance vector
–sensibile al carico: viene assunto che i costi dei link variano anche a seconda del traffico che viene immesso su di essi
–insensibile al carico: non viene considerato il traffico sui link come un parametro per stabilire i percorsi
•Il protocollo di rete usato su Internet è IP (Internet Protocol)
–in un certo senso, IP utilizza un instradamento locale statico insensibile al carico
•Esistono numerosi protocolli di instradamento, che rendono dinamico l’instradamento di IP:
–RIP, OSPF e BGP sono i principali
Instradamento in Internet
•Su Internet vengono impiegati essenzialmente due tipi di algoritmi di instradamento:
–un algoritmo dinamico basato sullo stato globale dei link –un algoritmo dinamico decentralizzato a vettore delle distanze
• • I pesi attribuiti ai links possono essere: I pesi attribuiti ai links possono essere:
– Unitari: si giunge al
– Unitari: si giunge al min-hop path min-hop path
– – Legati alla capacità del link ed al traffico Legati alla capacità del link ed al traffico previsto;
previsto;
– – Variabili nel tempo in seguito al traffico Variabili nel tempo in seguito al traffico misurato sui links stessi
misurato sui links stessi . .
•L’idea è quella che ogni router propaghi a tutti i suoi vicini le informazioni relative ai link cui è
direttamente connesso
–dopo un tempo opportuno, tutti i router di tutta la rete avranno una mappa della rete, contenente tutte le
informazioni
–a questo punto ogni router può calcolare il percorso ottimo tra se stesso e la destinazione
–se la rete è stabile, allora tutti i router calcoleranno sempre lo stesso percorso ottimo, ed è quindi garantito che un datagram percorra la strada migliore per giungere a destinazione
Shortest Path Algorithm
•L’algoritmo di instradamento globale maggiormente impiegato è basato sull’algoritmo di Dijkstra noto
come Shortest Path
–lo scopo dell’algoritmo di Dijkstra è trovare il cammino minimo tra due nodi di un grafo pesato dato
•L’algoritmo di Dijkstra usa le seguenti notazioni:
–c(i, j): costo del link dal nodo i al nodo j, se i nodi non sono collegati, allora si assume che c(i, j) = ;
–D(v): costo del percorso dal nodo sorgente al nodo di
destinazione v con costo minimo, a fine esecuzione;
–N: l’insieme dei nodi di cui è noto il percorso ottimo
•L’algoritmo calcola i percorsi di costo minimo dalla sorgente (data) a tutti gli altri nodi della rete:
-
in ingresso, l’algoritmo prende la matrice c, che descrive completamente la struttura della rete-in ingresso, l’algoritmo prende il nodo A, corrispondente al nodo sorgente
•assumiamo che V sia l’insieme di tutti i nodi (desumibile da c)
Shortest Path Algorithm
N = { A }; // Inizializzazione for ( x in V )
D(x) = c(A,x);
do // ciclo principale
m = ; // cerca il percorso a costo minimo noto for ( x in V \ N )
if (D(x) < m) { w = x;
m = D(w);
}
N = N {w}; // aggiorna l’insieme dei nodi di cui è noto il percorso ottimo
for ( x in V \ N )// aggiorna gli altri percorsi D(x) = min{ D(x), D(w) + c(w,x) };
until ( N == V );
Shortest Path Algorithm
1 Inizializzazione (nodo A):
2 N = {A}
3 per tutti i nodi x . N 4 if n adiacente ad A
5 then D(n) = c(A,x), p(x) = A 6 else D(n) = infinito
8 repeat
9 trova nodo w . N tale per cui D(w) è minimo 10 aggiungi w ad N
11 aggiorna D(x) per tutti gli n adiacenti a w, n . N:
12 if ( D(x) > D(w) + c(w,x))
13 then D(x) = D(w) + c(w,x), p(x) = w
13 /* il nuovo costo verso x è o il vecchio costo verso x o il 14 cammino a minimo costo verso w più costo da w a x*/
15 until tutti i nodi in N
Ovvero……….
N W A
C
B
E
D
F
2 1
3 2
6 6
3 4 7
7
A B: 2 A C: 1 A D: A E: A F:
scegli C
C 1
A,CL’insieme W rappresenta i nodi immediatamente raggiungibile da un nodo in N
Esempio
W N A
C
B
E
D
F
2 1
3 2
6 6
3 4 7
7
scegli B
C 1 B 2
A,C A,B
A B: 2 A D: 4 A E: 7 A F: 8
Esempio
W N
scegli D
C 1 B 2 D 4
A,C A,B A,C,
D
A
C
B
E
D
F
2 1
3 2
6 6
3 4 7
7
A D da C: 4 A D da B: 5 A E da B: 6 A E da C: 7 A F da C: 8 A F da B: 9
Esempio
Esempio
N
W A
C
B
E
D
F
2 1
3 2
6 6
3 4 7
7
scegli E
C 1 B 2 D 4 E 6
A,C
A,C, D A,B
A,B, E
Esempio
N
W A
C
B
E
D
F
2 1
3 2
6 6
3 4 7
7
scegli F
C 1 B 2 D 4 E 6 F 6
A,C
A,C, D
A,C, D,F A,B
A,B, E
• Complessità con M nodi
• Ogni iterazione:
– Controllo tutti i nodi w .N
– Aggiungo w a distanza minima
• M*(M+1)/2 confronti: O(M**2)
• L’implementazione più efficiente possibile: O(nlogn)
Algoritmo di Dijkstra: proprietà
• Vantaggi dell’algoritmo Link-State:
– Elevata accuratezza nell’individuazione del percorso migliore
– Assenza di loops di lunga durata
• Svantaggi:
– Informazione di segnalazione elevata e proporzionale alla frequenza di variazioni topologiche
OVERHEAD INACCETTABILE IN CONDIZIONI DI ELEVATA MOBILITA’ DEI NODI
Pro e Contro dell’algoritmo Link State
Algoritmi Distance Vector
• Il router tiene in una tabella tutti i percorsi di instradamento noti
• Ogni voce identifica una rete di destinazione e la relativa distanza, di solito misurata in salti o
hop.Ogni hop si riferisce al numero di router che un datagram attraversa dalla propria sorgente alla destinazione
• All’avvio, il router inizializza la sua tabella di
routing per contenere una voce per ciascuna rete
con cui è connesso direttamente.
Algoritmi Distance Vector (2)
• Quando dal router J arriva un resoconto al router K, questo esamina l’insieme di destinazioni riportate e le relative distanze
• Periodicamente ogni router invia una copia della propria tabella di routing agli altri router che può raggiungere direttamente
• Se J conosce un percorso più breve per raggiungere una destinazione, o se elenca una destinazione che K non ha nella sua tabella, o se K al momento sta
inviando ad una destinazione tramite J e la distanza
di J a quella destinazione è cambiata, K sostituisce la
voce nella sua tabella
Algoritmi Distance Vector (3)
• Notare che se J riporta la distanza N, una voce
aggiornata in K avrà la distanza N+1 (la distanza per raggiungere la destinazione da J più la distanza per raggiungere J)
• La tabella di routing contiene una terza colonna che specifica il salto successivo
• Quando il router K aggiunge o modifica una voce in
risposta ad un messaggio proveniente da J,assegna il
router J come il salto successivo per quella voce
Algoritmi Distance Vector Algoritmi Distance Vector
Ogni nodo scambia periodicamente con i vicini diretti un vettore contenente:
– le destinazioni che può raggiungere
– la distanza dalle destinazioni misurata in costo (ad esempio: numero nodi da attraversare compreso se stesso)
• Il nodo che riceve il vettore lo confronta con le proprie RT ed effettua modifiche:
– aggiunge nuove destinazioni
– cambia instradamenti se nuovi sono più brevi
– modifica costi se usa nodo adiacente come miglior
scelta
Implementazione
• Struttura dati: tabella distanze
• Ogni nodo possiede la propria
– Una riga per ogni possibile destinazione
– Una colonna per ogni nodo adiacente
• Esempio: nel nodo X, per la destinazione Y
attraverso nodo adiacente Z:
Sorgente
D
X(Y,Z) = c(X,Z) + min {D
z(Y,w)}
Destinazione
Next hop
Distance Vector
Instradamento Distance Instradamento Distance
Vector Vector
• Distribuito:
– ogni nodo avvisa i vicini solo quando il suo cammino migliore verso una certa
destinazione è cambiato
– i vicini avviseranno a loro volta nodi vicini se necessario
• Iterativo, asincrono: una iterazione (locale al nodo) causata da:
– modifica costo canale a cui nodo collegato
– messaggio ricevuto da nodo adiacente, che causa
modifica del cammino ottimo
Algoritmo Distance Vector Algoritmo Distance Vector
Ad ogni nodo X:
1 Inizializzazione:
2 per tutti i nodi adiacenti v:
3 D X(*,v) = infinito /* l’operatore * significa ”per ogni riga" */
4 D X(v,v) = c(X,v)
5 per tutte le destinazioni, y
6 invia min D X(y,w) verso ogni nodo adiacente /* w sono tutti i vicini di X*/
w
7 7
Algoritmo Distance Vector Algoritmo Distance Vector
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: DX (y,V) = DX (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 minW DV(Y,w) */
20 /* call this received new value is "newval" */
21 for the single destination y: DX (Y,V) = c(X,V) + newval 22
23 if we have a new minW DX(Y,w) for any destination Y 24 send new value of minW DX (Y,w) to all neighbors 25
26 forever
