Fondamenti di Internet e Reti
Fondamenti di Internet e RetiStrato di rete
Francesco MusumeciDipartimento di Elettronica, Informazione e Bioingegneria (DEIB) – Politecnico di Milano
Fondamenti di Internet e Reti
5e – Algoritmi di instradamento
• Generalità• Distance vector• Link state
Sommario
3F. Musumeci – FIR: Strato di rete
• Generalità• Distance vector• Link state
Sommario
4F. Musumeci – FIR: Strato di rete
• Gli algoritmi di instradamento (o di routing) definiscono i criteri di scelta del cammino nella rete per i pacchetti che viaggiano tra un nodo di ingresso ed uno di uscita– Servono a costruire le tabelle di routing che vengono consultate dai
nodi per effettuare l’inoltro (forwarding) dei pacchettio In alcuni casi l’inoltro (anche indiretto) può essere svolto anche senza
ricorrere a tabelle di routing (instradamento random, flooding,…v. dopo)• Il tipo di rete (datagram, circuito virtuale) determina il criterio di adottare
nella scelta dei cammini, quindi l’algoritmo di instradamento opportuno
Algoritmi di instradamento
5F. Musumeci – FIR: Strato di rete
• Protocollo: scambio fra i router delle informazioni di raggiungibilità (info sulla topologia di rete, sul traffico etc.)
• Algoritmo: costruzione delle tabelle di routing (scelta del percorso "migliore”) sulla base delle informazioni scambiate
• Formalmente il protocollo è solo la parte che descrive lo scambio di messaggi tra i router
• In realtà questo scambio è poi strettamente legato al modo con cui sono calcolate le tabelle di routing
Routing: Algoritmi e Protocolli
6F. Musumeci – FIR: Strato di rete
Routing: Algoritmi e Protocolli
7F. Musumeci – FIR: Strato di rete
IP1
Rete BRete C
Rete D
Rete ERete F
Rete A
IP2
IP3
Tabella di routing R1
Destinazione Next-hop
Rete A IP1
Rete B IP1
Rete C IP2
Rete D IP2
Rete E IP3
Rete F IP3
R2
R3
R4R6
R5
• Info di routing scambiate tra i router tramite un protocollodi routing– Ad es R5 annuncia C e D
• Tramite queste info, ciascun router decide come compilare la propria tabella– usando un algoritmo di
routing
"Da qui si raggiunge Rete C
e Rete D"
R1
Routing: Algoritmi e Protocolli
8F. Musumeci – FIR: Strato di rete
IP1
Rete BRete C
Rete D
Rete ERete F
Rete A
IP2
IP3
Tabella di routing R1R1
R2
R3
R4R6
R5
• Dal punto di vista di R1, raggiungere le varie reti equivale a raggiungere il router che può fare inoltro diretto su quelle reti
Negli alg. di routing si usano i GRAFI (solo router e link, no reti)
Destinazione Next-hop
Rete A R2 IP1
Rete B R2 IP1
Rete C R5 IP2
Rete D R5 IP2
Rete E R6 IP3
Rete F R4 IP3
• digrafo (grafo diretto) G(N,A)– N: insieme dei nodi– A={(i,j), i∈N, j∈N}: insieme degli archi (coppia ordinata di nodi)– Se i link sono bidirezionali si parla di "grafo non diretto"
• percorso: (n1, n2, …, nl) insieme di nodi con (ni, ni+1)∈A• cammino: percorso senza nodi ripetuti• ciclo: percorso con n1= nl
• digrafo connesso: per ogni coppia i, j esiste almeno un cammino da i a j
• digrafo pesato: dij peso associato all’arco (i,j)∈A• costo (lunghezza) di un cammino (n1, n2, …, nl):
dn1, n2+ dn2,n3+…+dn(l-1), nl
Richiami sui grafi
9F. Musumeci – FIR: Strato di rete
• Requisiti di un algoritmo di instradamento– Semplicità– Robustezza– Stabilità– Ottimalità
• Quali pacchetti necessitano di instradamento?– Pacchetti di segnalazione in servizi circuito virtuale– Pacchetti dati in servizi datagram
• Chi decide qual è la migliore soluzione di instradamento?– Algoritmi centralizzati: un unico centro di controllo prende tutte le
decisioni– Algoritmi distribuiti: tutti i nodi cooperano per determinare il migliore
instradamento in ogni nodo– Algoritmi isolati: il nodo sorgente prende le proprie decisioni in modo
autonomo, eventualmente anche in base a informazioni richieste ad altri nodi
Algoritmi di instradamento
10F. Musumeci – FIR: Strato di rete
Tassonomia
11
Instradamentocon tabella
Instradamentosenza tabella
Instradamentogerarchico
Algoritmi diinstradamento
Source routingRandom FissoDinamicoFlooding
Link stateDistance vector
Routing isolato
Routing non isolato (controllo distribuito o centralizzato)
F. Musumeci – FIR: Strato di rete
• Il link uscente è scelto casualmente– Alta variabilità dei tempi di ritardo dei vari pacchetti a destinazione– Molto robusto
• Per avere equa ripartizione del traffico in rete:– Link in uscita scelto in base alla capacità disponibile sui link
– Probabilità di selezionare link i:
• Variazione: Selective random– Instradamento deterministico solo se destinazione è adiacente– Richiede disponibilità di “tabella delle adiacenze” (non più completamente
isolato)
Algoritmi di instradamento senza tabellaRandom
12
∑=
= H
jj
ii
C
Cp
1
F. Musumeci – FIR: Strato di rete
• Il pacchetto è replicato su tutti i link uscenti ad eccezione di quello di ingresso– Aumento del traffico "interno" alla rete– Limitazione del traffico garantita se ogni nodo
o Scarta i pacchetti già transitati, oppureo Scarta i pacchetti il cui massimo numero di salti si è esaurito
– Necessario un contatore nel pacchetto (ad es. TTL)– Se si usa l’info sul “diametro” della rete (distanza massima
tra nodi) si riduce ulteriormente il traffico in rete– Robustissimo (adottato in applicazioni militari)
• Esempio (sorgente A, destinazione C)
Algoritmi di instradamento senza tabellaFlooding
13F. Musumeci – FIR: Strato di rete
• Il pacchetto è replicato su tutti i link uscenti ad eccezione di quello di ingresso– Aumento del traffico "interno" alla rete– Limitazione del traffico garantita se ogni nodo
o Scarta i pacchetti già transitati, oppureo Scarta i pacchetti il cui massimo numero di salti si è esaurito
– Necessario un contatore nel pacchetto (ad es. TTL)– Se si usa l’info sul “diametro” della rete (distanza massima
tra nodi) si riduce ulteriormente il traffico in rete– Robustissimo (adottato in applicazioni militari)
• Esempio (sorgente A, destinazione C)• Variazione: Selective flooding
– Instradamento solo su un gruppo dilinee uscenti (uso di una “tabella” ridotta ccon link diretti verso la destinazione)
Algoritmi di instradamento senza tabellaFlooding
14F. Musumeci – FIR: Strato di rete
• Il nodo sorgente Hs predetermina la strada verso la destinazione Hdscrivendola direttamente nel pacchetto IP (campo options)– Sequenza di interfacce da attraversare: Hs,N1,N2,...,NL,Hd (Ni
identifica l’indirizzo dell’interfaccia al nodo i)– Come apprendere il percorso al nodo sorgente?
1. Fornita da un path server (soluzione centralizzata, semplice ma inaffidabile)
2. Fornita da una procedura di path discovery (soluzione isolata)– Path discovery
o Il nodo sorgente invia in flooding un pacchetto alla destinazioneo Ogni nodo attraversato riempie il primo campo Ni ancora vuotoo Il nodo destinazione sceglie tra i pacchetti arrivati quello che identifica la via
migliore (primo arrivato o quello con il minore numero di nodi attraversati)o Il nodo destinazione comunica al nodo sorgente il percorso migliore
– Problema critico: necessario aggiornare i percorsi periodicamenteo Bisogna tener conto dei cambiamenti di stato della rete
Algoritmi di instradamento senza tabellaSource routing
15F. Musumeci – FIR: Strato di rete
• Grande numero di nodi implica– grande occupazione di memoria per le tabelle di
instradamento– sovraccarico di rete per scambio tabelle di
instradamento in algoritmi distribuiti• Strutturazione dei nodi in regioni
– Instradamento basatosu tabelle semplificate
• Sub-ottimo
Instradamento gerarchico
16
Dest. RouteFull. Hier.
A.1 A.2 A.2A.2 A.2 A.2A.3 A.3 A.3A.4 - -A.5 A.5 A.5A.6 A.3 A.3B.1 B.1
B.1B.2 B.1B.3 B.1B.4 B.1B.5 B.1C.1 A.5
A.5
C.2 A:5C.3 B.1C.4 B.1C.5 A,5C.6 A.5
A.4 routing table
Dettaglio
AggregazioneF. Musumeci – FIR: Strato di rete
• Strutturazione gerarchica dei nodi su L livelli– Nodi suddivisi in M1 regioni (primo livello)– Regioni divise in M2 aree (secondo livello)– Aree divise in M3 zone (terzo livello)– ecc.
Instradamento gerarchico
17
A.1.a
A.1.b A.1.c
A.1.e
A.1.d
A.1.f
B.1
B.5
B.4
B.2
B.3
A.2.a
A.2.b A.2.c
A.2.eA.2.d
A.2.fA.3.a
A.3.b A.3.c
A.3.f
A.3.d
A.3.e
C.1
C6C.5
C.2C.3
C.4
AA.1
A.2
A.3C
B
Rotuing non ottimale
Rotta gerarchica
Percorso più breve
F. Musumeci – FIR: Strato di rete
• Basati su instradamento a distanza minima (o costo minimo)
• Richiede la definizione di una metrica di costo. Ad esempio:– Numero di salti (hop)– Capacità dei link– Ritardo dei link– Numero medio di pacchetti in coda sull’intero percorso– ecc.
• Le tabelle di instradamento indicano per ogni destinazione di rete il nodo successivo verso cui instradare il pacchetto
• Versione “primordiale”: instradamento statico
Algoritmi di instradamento con tabella
18F. Musumeci – FIR: Strato di rete
• Forma più semplice di routing IP• Non richiede segnalazione tra router• Tabelle di routing compilate manualmente dall’amministratore di
rete– Fase di design
o Per ciascun router viene selezionata una rotta per ciascunapossibile altra sottorete
– Fase di configurazioneo Le tabelle di routing sono configurate tramite opportune istruzioni
• Quando è opportuno utilizzarlo?– Periferia della rete– Sistemi (ad es. ISP) con bassa connettività (poche righe da
compilare manualmente)– Necessità di fare load-balancing
Routing statico
19F. Musumeci – FIR: Strato di rete
• I protocolli di routing usati in Internet sono dinamici• Le entry delle tabelle di routing cambiano nel tempo, in base a:
– Guasti nei link (failures)o Quando un link si interrompe è necessario aggirarlo
– Cambiamenti nella topologia di reteo Quando viene aggiunto un nuovo router backbone, considera il suo utilizzo
– Carico di rete e congestioneo Quando un link è poco usato, conviene sfruttarlo
Routing dinamico (adattativo)
20
1. path iniziale
4. nuovo path
2. failure
Aggiornamento delle tabelle di routing possibile SOLOcon protocolli dinamici
3.Scambio messaggi del protocollo di routing
F. Musumeci – FIR: Strato di rete
• Generalità– Algoritmi sui grafi
• Distance vector• Link state
Sommario
21F. Musumeci – FIR: Strato di rete
• La politica di routing utilizzata sin dall’introduzione delle reti TCP/IP è basata sul calcolo dei cammini minimi
• Il calcolo è effettuato sul grafo che rappresenta la rete– ad ogni arco è associato un "peso" opportunamente scelto
(metrica di costo)• Perché?
– i cammini minimi verso una destinazione formano sul grafo l’albero dei cammini minimi, o Minimum Spanning Tree(MST)
– esistono degli algoritmi di calcolo dei MST che possono essere eseguiti in modo distribuito dai router
Routing a cammini minimi
22F. Musumeci – FIR: Strato di rete
• Il problema è di complessità polinomiale– Al crescere del nr di nodi N, il numero di operazioni necessarie per
ottenere i cammini minimi cresce come un polinomio in N
Problema del cammino minimo
Dato un digrafo G(N,A) e due nodi i e j, vogliamo trovare il cammino di costo minimo tra tutti quelli che consentono di andare i a j
Proprietà: Se il nodo k è attraversato dal cammino a costo minimo da i a j, il
sotto-cammino fino a k è anch’esso a costo minimo
23F. Musumeci – FIR: Strato di rete
• Qual è il percorso a costo minimo tra u e z?• L’algoritmo di routing deve trovare tale percorso
Esempio
u
yx
wv
z2
21
1
4
1
2
53
5G = (N,E)
N = insieme di router = { u, v, w, x, y, z }
E = insieme di link = { (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }
c(x,x’) = costo del link (x,x’)ad esempio, c(w,z) = 5
F. Musumeci – FIR: Strato di rete 24
• Generalità• Distance vector• Link state
Sommario
25F. Musumeci – FIR: Strato di rete
• Sfrutta l’istradamento a distanza minima– in ogni nodo la tabella di routing specifica la minima distanza da
ogni altro nodo e quale nodo deve essere utilizzato come next hop• Forma centralizzata
– Applicazione dell’algoritmo di Bellman-Ford per il calcolo centralizzato dell’albero dei cammini minimi
• Forma distribuita– Ciascun nodo riceve solo dai suoi vicini la stima delle distanze
(vettore delle distanze), somma la sua distanza dal vicino e scopre la distanza minima verso ogni altro nodo
– Corrisponde ad applicare in ogni nodo l’algoritmo di Bellman-Ford
Algoritmo distance vector
26F. Musumeci – FIR: Strato di rete
• Data la topologia di rete, costruisce l’albero dei cammini minimi (Minimum Spanning Tree – MST) dal nodo sorgente (s)
• Algoritmo iterativo che considera numero di salti (h) crescente
Distance vectorForma centralizzata: algoritmo di Bellman-Ford
{ }
stoptogoelse
hhthensjDDIf
sjDdDDhh
sjdDh
hjsD
djid
max
hj
hj
hjij
hii
hj
sjhj
hj
ijij
2 1
3
,min1+=2
11salti max con a da costo minimo a viadella Costo
diretto)link senza ( a dalink del costo
1
11
−=
≠∀=
≠∀+=
≠∀=
=
=
∞==
−
−−
27F. Musumeci – FIR: Strato di rete
In un grafo diretto, funziona anche con link di costo negativo, a patto che nella rete non esistano cicli di costo totale negativo
Algoritmo di Bellman-FordEsempio – Nodo A
Dest. h=1 h=2 h=3 h=4Cost Route Cost Route Cost Route Cost Route
A - - - -B 1 B 1 B 1 B 1 BC ∝ 4 B 4 B 4 BD ∝ 9 F 6 F 5 BE ∝ 5 F 4 B 4 BF 3 F 2 B 2 B 2 B
Tabella di instradamento del nodo A
28F. Musumeci – FIR: Strato di rete
• Il DV è inviato ai soli nodi adiacenti• Il DV è inviato periodicamente o a seguito di un cambiamento nella topologia di rete
– Ogni nodo esegue il ricalcolo del proprio DV se cade/nasce una linea attiva a cui è connesso
Appena riceve un DV da un vicino, il nodo…1. Aggiunge a ciascuna destinazione inclusa nel DV il costo del link verso il vicino2. Per ognuna di queste destinazioni:
– se la destinazione non era già inclusa nella tabella di routingo aggiunge la destinazione/distanza
– altrimentio se il next hop nella tabella di routing corrisponde al mittente del DV
– sostituisce l’informazione della tabella di routing con quella nuova (anche se peggiorativa)
o altrimenti– se la distanza indicata nel DV è minore di quella attualmente scritta nella tabella di
routing» Sostituisci l’informazione della tabella di routing con quella nuova
Distance vectorForma distribuita: scambio dei DV tra router adiacenti
29F. Musumeci – FIR: Strato di rete
Dest. Costo N.H.
30
Distance vectorEsempio: aggiornamento della tabella di routing
F. Musumeci – FIR: Strato di rete
CR
DV CR
costo = 1
Tabelladi routing in R
• Calcolo della tabella di instradamentonel nodo A– Aggiornamento ogni T s– In [0,T] A vede solo i suoi vicini– Primo vettore ricevuto in A
da B e F a t = T+εo Nuova tabella in A
disponibile a t = 2T– Secondo vettore …
• t = 2T : B riceve DV da F
1
3
15
3
2
2
1
6
F E
A D
B C
Distance vectorEsempio in una rete (1/2)
31F. Musumeci – FIR: Strato di rete
• t = T+ε : rottura link D-E– t = 2T: E invia il nuovo DV a F
• t = 2T+ε : variazione costo F-E 2 3• t = 3T: F cambia la propria
tabella (aggiorn. su D e E)– Nuova tabella in A a t = 4T
• Le info negative arrivano a B • F le aveva già ricevute…• Nuova tabella in A a t = 5T
Distance vectorEsempio in una rete (2/2)
32F. Musumeci – FIR: Strato di rete
1
3
15
3
2
2
1
6
F E
A D
B C
x 3
• Diversa efficacia all’occorrenza di eventi di cambiamenti di topologia– Aggiunta di nodi (“notizie positive”): propagazione veloce
dell’aggiornamento– Rimozione di nodi (“notizie negative”): può dare luogo a problemi
• Esempio (notizie positive)– Hp: costi unitari
– Nuovo nodo D raggiungibile in rete
Algoritmo distance vectorNuovo nodo in rete
33
A B C D
Node A Node B Node C EventsStep Dest. Cost Next hop Cost Next hop Cost Next hopInit
1- D 1 D C-D = 11 D 2 C 1 D C → B2 D 3 B 2 C 1 D B → A3 D 3 B 2 C 1 D
A B C
F. Musumeci – FIR: Strato di rete
• Esempio (notizie negative)– Hp: costi unitari– Il nodo D diventa irraggiungibile
Algoritmo distance vectorProblema: Nodo irraggiungibile - Count to infinity
34
A B C D
Node A Node B Node C EventsStep Dest. Cost Next hop Cost Next hop Cost Next hopInit D 3 B 2 C 1 D
1- D 3 B 2 C ∝ C-D = ∝1 D 3 B 4 A ∝ C → B, A → B2 D 5 B 4 A 5 B B → A, B → C3 D 5 B 6 A 5 B A → B4 D 7 B 6 A 7 B B → A, B → C5 D 7 B 8 A 7 B A → B6 D 9 B 8 A 9 B B → A, B → C7 D 9 B 10 A 9 B A → B
... D ∝ ∝ ∝
A B C D
F. Musumeci – FIR: Strato di rete
• Se il nodo A manda a D i pacchetti destinati al nodo X, non ha senso che A annunci a D la raggiungibilità di X nel suo Distance Vector
• Split-Horizon– Il nodo A non annuncia a D con quale costo raggiunge X
Count to infinity: rimedio
A DX
35F. Musumeci – FIR: Strato di rete
• Rimedio al count-to-infinity– Split horizon: stima di distanza verso una destinazione non viene trasferita sul
collegamento utilizzato per raggiungere quella destinazione– Split horizon with poisonous reverse: stima di distanza inviata a tutti i vicini, ma
la distanza è posta a infinito se il collegamento è utilizzato per raggiungere la destinazione
• Esempio– Costi unitari– Il nodo D diventa irraggiungibile in rete
– Split horizono A Bo B C
Algoritmo distance vectorSoluzione: Split horizon
36
A B C D
Node A Node B Node C EventsStep Dest. Cost Next hop Cost Next hop Cost Next hopInit D 3 B 2 C 1 D
1- D 3 B 2 C ∝ C-D = ∝1 D 3 B ∝ ∝ C → B2 D ∝ ∝ ∝ B → A
A B C D
Node A Node B Node C EventsStep Dest. Cost Next hop Cost Next hop Cost Next hopInit D 3 B 2 C 1 D
1- D 3 B 2 C ∝ C-D = ∝
//
F. Musumeci – FIR: Strato di rete
• Split horizon potrebbe non funzionare con certe topologie– Dipende dalla successione dei vettori inviati
• Esempio– Initial split horizon
o A Co B C
Problemi con split horizon
37
A B C D
Node A Node B Node C EventsStep Dest. Cost Next hop Cost Next hop Cost Next hopInit D 2 C 2 C 1 D
1- D 2 C 2 C ∝ C-D = ∝1 D 2 C ∝ ∝ C → B2 D 2 C 3 A ∝ A → B3 D 2 C 3 A 4 B B → C4 D 5 C 3 A 4 B C → A5 D 5 C 6 A 4 B A → B6 D 5 C 6 A 7 B B → C7 D 8 C 6 A 7 B C → A
... D ∝ ∝ ∝
Node A Node B Node C EventsStep Dest. Cost Next hop Cost Next hop Cost Next hopInit D 2 C 2 C 1 D
1- D 2 C 2 C ∝ C-D = ∝
//
(∞)(2)(3)(4)(5)(6)(7)
F. Musumeci – FIR: Strato di rete
• Generalità• Distance vector• Link state
Sommario
38F. Musumeci – FIR: Strato di rete
• Ogni nodo misura il costo dei collegamenti (ad esempio secondo la metrica “distanza” o “ritardo”) verso tutti i suoi vicini– Invia un vettore di “link state”– Link state funziona solo con costi di segno positivo
• Questa distanza è comunicata a tutti gli altri nodi con tecnica flooding
• Ogni nodo ha visibilità completa della rete e può così costruire i percorsi a minima distanza verso ciascun altro nodo
• I costi dei link possono variare serve inviare nuovi link state all’occorrenza
• Anche se non ci sono aggiornamenti i link state vengono comunque inviati periodicamente
Algoritmo link state
39F. Musumeci – FIR: Strato di rete
• Algoritmo di Dijkstra:– si applica al generico nodo sorgente (s)
Instradamento a minima distanza Link state
40F. Musumeci – FIR: Strato di rete
Algoritmo di DijkstraEsempio
41
Tabella di instradamento del nodo A
Dest. M={A} M={A,B} M={A,B,F} M={A,B,E,F} M={A,B,C,E,F} M={A,B,C,D,E,F}Cost Route Cost Route Cost Route Cost Route Cost Route Cost Route
A - - - - - -B 1 B 1 B 1 B 1 B 1 B 1 BC ∝ 4 B 4 B 4 B 4 B 4 BD ∝ ∝ 8 B 5 B 5 B 5 BE ∝ 6 B 4 B 4 B 4 B 4 BF 3 F 2 B 2 B 2 B 2 B 2 B
1
3
15
3
2
2
1
6
B C
F E
A D
F. Musumeci – FIR: Strato di rete
Algoritmo di DijkstraEsempio
42
Tabella di instradamento del nodo A
Dest. M={A} M={A,B} M={A,B,F} M={A,B,E,F} M={A,B,C,E,F} M={A,B,C,D,E,F}Cost Route Cost Route Cost Route Cost Route Cost Route Cost Route
A - - - - - -B 1 B 1 B 1 B 1 B 1 B 1 BC ∝ 4 B 4 B 4 B 4 B 4 BD ∝ ∝ 8 B 5 B 5 B 5 BE ∝ 6 B 4 B 4 B 4 B 4 BF 3 F 2 B 2 B 2 B 2 B 2 B
1
3
15
3
2
2
1
6
B C
F E
A D
F. Musumeci – FIR: Strato di rete
Algoritmo di DijkstraEsempio
43
Tabella di instradamento del nodo A
Dest. M={A} M={A,B} M={A,B,F} M={A,B,E,F} M={A,B,C,E,F} M={A,B,C,D,E,F}Cost Route Cost Route Cost Route Cost Route Cost Route Cost Route
A - - - - - -B 1 B 1 B 1 B 1 B 1 B 1 BC ∝ 4 B 4 B 4 B 4 B 4 BD ∝ ∝ 8 B 5 B 5 B 5 BE ∝ 6 B 4 B 4 B 4 B 4 BF 3 F 2 B 2 B 2 B 2 B 2 B
1
3
15
3
2
2
1
6
B C
F E
A D
F. Musumeci – FIR: Strato di rete
Algoritmo di DijkstraEsempio
44
Tabella di instradamento del nodo A
Dest. M={A} M={A,B} M={A,B,F} M={A,B,E,F} M={A,B,C,E,F} M={A,B,C,D,E,F}Cost Route Cost Route Cost Route Cost Route Cost Route Cost Route
A - - - - - -B 1 B 1 B 1 B 1 B 1 B 1 BC ∝ 4 B 4 B 4 B 4 B 4 BD ∝ ∝ 8 B 5 B 5 B 5 BE ∝ 6 B 4 B 4 B 4 B 4 BF 3 F 2 B 2 B 2 B 2 B 2 B
1
3
15
3
2
2
1
6
B C
F E
A D
F. Musumeci – FIR: Strato di rete
Algoritmo di DijkstraEsempio
45
Tabella di instradamento del nodo A
Dest. M={A} M={A,B} M={A,B,F} M={A,B,E,F} M={A,B,C,E,F} M={A,B,C,D,E,F}Cost Route Cost Route Cost Route Cost Route Cost Route Cost Route
A - - - - - -B 1 B 1 B 1 B 1 B 1 B 1 BC ∝ 4 B 4 B 4 B 4 B 4 BD ∝ ∝ 8 B 5 B 5 B 5 BE ∝ 6 B 4 B 4 B 4 B 4 BF 3 F 2 B 2 B 2 B 2 B 2 B
1
3
15
3
2
2
1
6
B C
F E
A D
F. Musumeci – FIR: Strato di rete
Algoritmo di DijkstraEsempio
46
Tabella di instradamento del nodo A
Dest. M={A} M={A,B} M={A,B,F} M={A,B,E,F} M={A,B,C,E,F} M={A,B,C,D,E,F}Cost Route Cost Route Cost Route Cost Route Cost Route Cost Route
A - - - - - -B 1 B 1 B 1 B 1 B 1 B 1 BC ∝ 4 B 4 B 4 B 4 B 4 BD ∝ ∝ 8 B 5 B 5 B 5 BE ∝ 6 B 4 B 4 B 4 B 4 BF 3 F 2 B 2 B 2 B 2 B 2 B
1
3
15
3
2
2
1
6
B C
F E
A D
F. Musumeci – FIR: Strato di rete
• Algoritmi distance vector e link state convergono alla stessa soluzione in condizioni statiche
• Algoritmo distance-vector– Ha convergenza più lenta in condizioni dinamiche– Semplice da implementare
o Ogni nodo deve conoscere solo ciò che vedono i suoi vicini (i distance vector sono inviati solo ai nodi vicini)
• Algoritmo link state– Alta velocità di convergenza– Difficile da implementare
o Nella forma distribuita, ogni nodo deve “vedere” l’intera rete (i vettori di link state devono essere inviati a tutti i nodi della rete)
o Elevata quantità di informazioni scambiate in flooding
Instradamento a minima distanzaOsservazioni
47F. Musumeci – FIR: Strato di rete
Fondamenti di Internet e Reti
5f – Instradamento in IPRIP, OSPF
• Non possiamo pensare di applicare DV/LS direttamentea tutta Internet– Scalabilità: Internet è formata da milioni di nodi
o LS genera troppa informazione (flooding), DV convergerebbemolto lentamente
– Sicurezza: ISP non vogliono rivelare la struttura dellapropria rete (es., con un LS) oppure vogliono evitaredi attraversare alcuni domini
Routing in Internet: Distance Vector o Link State?
49F. Musumeci – FIR: Strato di rete
Backbone
ASAS
AutonomousSystem (AS)
ExteriorGateway
InteriorGateway
• Internet è suddivisa in Autonomous Systems (AS)– Porzione di rete gestita dalla stessa autorità– Un router interno a un AS si chiama Interior Gateway– Un router al bordo di un AS si chiama Exterior Gateway
Architettura di routing di Internet
50F. Musumeci – FIR: Strato di rete
ASAS
ExteriorGateway
InteriorGateway
• All’interno di ciascun AS il routing è indipendente dagli altri AS– Gli Interior Gateway si scambiano informazioni di routing
"intra-AS" usando un Interior Gatweay Protocol (IGP)– Condivisione completa delle informazioni topologiche
Architettura di routing di Internet
IGP
51
AutonomousSystem (AS)
Backbone
F. Musumeci – FIR: Strato di rete
ASAS
ExteriorGateway
InteriorGateway
• Il routing tra AS è gestito in modo differente– Gli Exterior Gateway si scambiano informazioni di routing
usando un Exterior Gateway Protocol (EGP)– Utilizza un approccio diverso da quello DV/LS
IGP EGP
52
AutonomousSystem (AS)
Backbone
Architettura di routing di Internet
F. Musumeci – FIR: Strato di rete
• Diretto– Il NETID degli host sorgente e destinazione coincidono– Il forwarding è effettuato mediante la rete di livello 2 (associazione tra HOSTID indirizzi MAC)
• Indiretto– Il NETID degli host sorgente e destinazione sono diversi ma appartengono allo stesso AS– Il forwarding avviene mediante Interior Gateways usando IGP
• Indiretto gerarchico– Sorgente e destinazione sono in AS diversi– Nell’AS sorgente il
pacchetto è instradato con IGP fino all’ExteriorGateway
– Usando EGP e ExteriorGateways si arriva all’AS destinazione
– Nell’AS destinazione il pacchetto è instradato con IGP fino all’hostdestinazione
• L’EGP annuncia all’interno le destinazioni esterne raggiungibili• Gli Exterior Gateway si scambiano informazioni sintetiche di raggiungibilità
La strada per la destinazione …
53
Diretto
Indiretto
Indirettogerarchico
F. Musumeci – FIR: Strato di rete
ExteriorGateway
• In un AS possono essere configurati più IGP– Devono essere gestiti in modo da garantire la consistenza del routing– Il caso più frequente è tuttavia un unico IGP in tutto l’AS
• Il dominio di routing (Routing Domain, RD) è una porzione di AS in cui è implementato un unico protocollo IGP
• Alcuni router appartengono a più RD e implementano più protocolli di routing sulle diverse interfacce
Interior Gateway Protocols (IGP)
54
AS
RD
RD
RD
F. Musumeci – FIR: Strato di rete
RD RD
Prot. AProt. B
• I router su più domini possono “ridistribuire” le informazioni di un dominio nell’altro e viceversa
• La traduzione delle informazioni dal Prot. A al Prot. B dipende dall’implementazione e dalle caratteristiche dei due protocolli A e B
• I due protocolli possono anche essere un IGP e un EGP
Ridistribuzione
55F. Musumeci – FIR: Strato di rete
• IGP– RIP (Routing Information Protocol), versione 1 e 2– IGRP (Interior Gateway Routing Protocol)
proprietario CISCO– IS-IS (Intermediate System Intermediate System)– OSPF (Open Shortest Path First)
• EGP– BGP (Border Gateway Protocol)
I Protocolli di Routing più usati
Link State
DistanceVector
Path Vector
56F. Musumeci – FIR: Strato di rete
• RIP• OSPF• BGP
Sommario
57F. Musumeci – FIR: Strato di rete
• Routing Information Protocol (RIP): RFC 1058 (1988)– Si affida ad UDP come protocollo di trasporto utilizzando la
“well known port” #520– Basato su Distance Vector
o DV scambiati tra nodi adiacentio Ogni router usa Bellman-Ford per il calcolo dei cammini minimi
– Metrica di costo: hop count– Massima distanza: 15 hop
o costo = 16 corrisponde a rete irraggiungibile– Info di aggiornamento (DV) inviate tipicamente ogni 30 s
• Pro– Facile implementazione
• Contro– Elevata complessità (sinonimo di algoritmo lento): ~O(N3)
o N: numero di nodi della rete– Possono verificarsi loop– Possibile count-to-infinity
Routing Information Protocol (RIP)Concetti base
58F. Musumeci – FIR: Strato di rete
RIPFormato dei messaggi
IP header UDP header RIP message
IP datagramUDP datagram
59F. Musumeci – FIR: Strato di rete
• Messaggi RIP trasportati da datagrammi UDP, a loro voltaincapsulati in pacchetti IP:– Header RIP: 4 byte– Header UDP: 8 byte– Payload RIP: fino a 25 record, ciascuno da 20 byte
o tot: 500 byte (=25*20 byte)– Un datagramma UDP usato per trasportare messaggi RIP ha
al max 512 byte (PL+OH) in genere è necessario più di un datagramma UDP per annunciare intere tabelle di routing (costituite da ben più di 25 rotte)
• RIP versione 1– Command (8 bit): tipo di messaggio (ad es., request (1), response (2))– Version (8 bit): assume valore 1 o 2– Address Family (16 bit): stack protocollare usato (2 per TCP/IP)– IP Address (16 byte): indirizzo della rete di destinazione (4 byte per IPv4)– Metric o Distance (32 bit): hop count dal router che fa l’annuncio fino alla rete di
destinazione indicata nel campo Addresso Valori ammessi: da 1 a 15 (16= rete irraggiungibile)
0 7 8 15 16 31
0IP address
Command (1-6) Version (1) 0Address family (2)
20bytes
00Metric
Si possono inserire fino a 24 rotte in più con lo stesso formato
60F. Musumeci – FIR: Strato di rete
Quale altra informazionesarebbe opportuno inserire?
RIPFormato dei messaggi
un router che annuncia una rete ad esso adiacente la
considera a distanza 0
• Appena avviato RIP, i router inviano speciali richieste suciascuna interfaccia, specificando alcuni campi del messaggio come segue– command = 1 (indica che si tratta di una request)– address family = 0 (invece di 2)– metric = 16
• Ciò serve a richiedere a ciascuno dei router vicini l’invio dell’intera tabella di routing in loro possesso– Consente di scoprire l’identità e le distanze dei router
vicini
61F. Musumeci – FIR: Strato di rete
RIPInizializzazione
• Request– Usato per ottenere info di routing su specifici indirizzi di rete che
vengono indicati nel messaggio di richiesta• Response
– Restituisce la lista di indirizzi di rete ed il relativo costo– Se il router interpellato non ha informazioni sulla destinazione (rete IP)
richiesta, restituisce costo 16 per quella rete• Regular update (ogni 30 s)
– I router inviano tutta la tabella di routing (o parte di essa) ai router vicini– Ciascun router elimina una entry della tabella (cioè setta il relativo
costo a 16) se l’informazione di routing non è aggiornata da più di 6 cicli (180s)o La reale cancellazione della entry avviene dopo ulteriori 60s per assicurarsi della
effettiva irraggiungibilità della rete• Triggered update
– Inviati non appena si verifica un cambiamento del costo di una rotta (sitrasmette solo l’informazione relativa alle reti che hanno subito un aggiornamento)
RIPOperazioni successive all’inizializzazione
62F. Musumeci – FIR: Strato di rete
• Le Request sono inviate da un router che– si è appena connesso, oppure– ha alcune entry in scadenza
• Con le Request si possono richiedere ai propri vicini– entry specifiche, oppure– tutte le entry in loro possesso
RIPRequest message
63
Source: Forouzan, 2004
F. Musumeci – FIR: Strato di rete
• Le Response possono essere– Solicited (regular update), cioè inviate in risposta ad una Request,
oppure– Unsolicited (triggered update), inviate periodicamente (ogni 30 s)
64F. Musumeci – FIR: Strato di rete
RIPResponse message
• Triggered update– Appena cambia il costo di una rotta, la nuova tabella di routing è
inviata immediatamente, senza aspettare lo scadere del periodo di agiornamento base di 30 s
• Split horizon
• Poison reverse
RIPAltre caratteristiche
65
Source: Forouzan, 2004
F. Musumeci – FIR: Strato di rete
• Hop count è una metrica di costo fin troppo semplice– Bellman-Ford non richiede necessariamente di usare hop count!– Quindi RIP potrebbe essere facilmente esteso considerando diverse
metriche di costo…il cuore dell’algoritmo sarebbe invariatoo Lunghezza della coda (~occupazione buffer) nella linea d’uscitao Ritardoo Probabilità di perdita (ad esempio misurata in precedenza)o etc…
• RIP converge lentamente– Router a distanza N hanno bisogno di N passi dell’algoritmo (=30*N
secondi) per arrivare a conoscere l’effettiva distanza che li separa• Limitato a reti di piccole dimensioni
– Poichè costo=16 equivale a rete irraggiungibile, due nodi non possono trovarsi a distanza maggiore di 15 hop
RIPLimiti
66F. Musumeci – FIR: Strato di rete
• Versione 2– Sfrutta meglio tutti i campi lasciati vuoti in RIPv1– Pensato per mantenere compatibilità con router RIPv1
• Nuovi campi introdotti– Route tag (16 bit): indica un numero (ID) dell’Autonomous System
o Consente di distinguere le rotte in base all’origine dell’informazione (rotte scoperte con RIP, con altro IGP o con EGP)
– Subnet mask (4 byte): quindi è supportato anche CIDR (finalmente!)– Next hop IP address (4 byte): indica esplicitamente l’indirizzo IP dell’
interfaccia verso cui instradare i pacchetti diretti alla specifica sottorete
RIPv2Formato dei messaggi
67
0 7 8 15 16 31
Route tagIP address
Command (1-6) Version (2) 0Address family (2)
20bytes
Subnet maskNext hop IP addressMetric
Source: Forouzan, 2004
F. Musumeci – FIR: Strato di rete
• RIP• OSPF• BGP
Sommario
68F. Musumeci – FIR: Strato di rete
• Algoritmo di routing link state– Si adotta routing shortest path (Dijkstra)– Ogni router ha cognizione dell’intera rete del dominio di
routing e può calcolare il MST– Si inviano aggiornamenti al seguito di eventi di modifica dei
costi dei link (event update)– Ciascun router non invia grandi tabelle di routing come in DV
o Invia solo lo stato dei link direttamente connessi• Ogni router deve
– “Scoprire” i suoi vicini– Misurare il costo per raggiungere ciascun vicino– Costruire un pacchetto Link State Packet (LSP) che
contenga le informazioni su tutti i link connessi– Inviare il pacchetto a tutti gli altri router (non solo ai vicini),
tipicamente con tecnica flooding
Protocollo Open Shortest Path First (OSPF)Concetti base
69F. Musumeci – FIR: Strato di rete
70
Protocollo Open Shortest Path First (OSPF)Caratteristiche
• Metrica di costo generica: una qualunque combinazione di ritardo, costo, bit-rate, etc.– Configurata dall’amministratore di rete– Il costo di attraversamento di ciascun link/rete è visto
indipendentemente dai router adiacentio Costo definito sulla “outgoing interface”o In linea teorica ai due lati di un link i due router possono definire due costi diversi
(ad es. per decidere localmente il load balancing)
• Load balancing dinamico– ottenuto specificando rotte multiple– da utilizzare quando più rotte hanno lo stesso costo
• Supporta routing gerarchico
F. Musumeci – FIR: Strato di rete
Messaggi OSPF
71F. Musumeci – FIR: Strato di rete
• Header dei messaggi (commune a tutti i tipi di messaggio)
• Tipi di messaggi– Hello Testa la raggiungibilità dei vicini– Database description (LSDB) Annuncia quali update possiede il sender– Link state request (LSR) Richiede informazioni su uno specifico link– Link state update (LSU) Fornisce il costo dei link vicini al sender– Link state ack (LSA) Riscontra un LSU
Messaggi OSPF
72
Bit31160
1
2
3
4
5
Source router IP address
Message lengthVersion
Area ID
Authentication typeChecksum
Authentication (octets 0-3)
8
Type
Authentication (octets 4-7) 6
F. Musumeci – FIR: Strato di rete
OSPF topology discoveryEsempio - 1
73
Router A
Pacchetti ricevuti Network discovery
BA 4C 2F 6
A
B C
F
42
6
CB 2D 3E 1
A
B C
E FD
42
63
1
DC 3F 7
2
A
B C
E FD
4 63
1
7
F. Musumeci – FIR: Strato di rete
Router A
FB 6D 7E 8
Conferma
EA 5C 1F 8
A
B C
E FD
42
63
1
75
8
OSPF topology discoveryEsempio - 2
74
Pacchetti ricevuti Network discovery
DC 3F 7
2
A
B C
E FD
4 63
1
7
F. Musumeci – FIR: Strato di rete
Load balancingShortest path multipli
Singolo shortest path
Più shortest path
12
4
11
3
3 2
costo del link
1
path cost = 6
path cost = 6
12
4
11
3
3 21
75F. Musumeci – FIR: Strato di rete
Load balancingAspetti negativi
Consegna pacchetti fuori sequenza!
50%
50%3 2 145
1
2
3
4
5
4 1 235
equal cost paths
76F. Musumeci – FIR: Strato di rete
OSPF e inoltro gerarchicoClassificazione dei router
F. Musumeci – FIR: Strato di rete 77
• Tipologie di router in un AS– Internal routers: tutte le interfacce appartengono alla stessa area– Area border routers: hanno interfacce su aree diverse– AS boundary routers: connessi ad almeno un router esterno all’AS
Autonomous System (AS)
Rete reale
Source: TCP/IP Protocol Suite, B. Forouzan
Rappresentazioneusata da OSPF
F. Musumeci – FIR: Strato di rete 78
OSPFRappresentazione della topologia
• Gli area border router diffondono in ciascuna area un "riassunto" delle informazioni relative alle altre aree– indicano solo le destinazioni raggiungibili, non i router
attraversati– "contaminazione" con approccio distance vector– Inoltro indiretto gerarchico
OSPFRidistribuzione delle info di routing
Visto nell’Area 2
Area 2
Area 1
Area 3
F. Musumeci – FIR: Strato di rete 79
• RIP• OSPF• BGP
Sommario
80F. Musumeci – FIR: Strato di rete
• Border Gateway Protocol version 4 (BGP-4): RFC 4271– Consente a router di diversi AS di scambiarsi
informazioni di routing (è un protocollo di tipo EGP)– Algoritmo di tipo path vector
o I gestori di AS decidono il routing in base a delle propriepolitiche, conoscendo i percorsi usati per raggiungere altri AS
– Indipendente dai protocolli IGP adottati dentro gli AS – Esistono due “tipologie” di BGP
o eBGP (external BGP): usato da diversi AS border routers per scambiare tra loro informazioni di routing
o iBGP (internal BGP): usato da un AS border router per propagare l’informazione di routing dentro l’AS
Boarder Gateway Protocol (BGP)Concetti base
81F. Musumeci – FIR: Strato di rete
• BGP (path vector) è simile al distance vector, ma nelle info scambiate tra i nodi non è indicata una “distanza dalla destinazione”, ma l’intero percorso verso la destinazione (sequenza degli AS da attraversare)
BGPPath vector (1)
Rete Router successivo
Percorso
N01 R01 AS2,AS5,AS7,AS12N02 R07 AS4,AS13,AS6,AS9N03 R09 AS11,AS12,AS8,AS6… … …
F. Musumeci – FIR: Strato di rete 82
• In realtà un messaggio di path vector che si scambiano due router EG vicini non contiene un percorso ma una sequenza di “attributi”
• Si distinguono attributi obbligatori, che devono essere interpretati da tutte le implementazioni di BGP, e attributi facoltativi
• Tra gli attributi obbligatori:– ORIGIN: protocollo IGP da cui proviene l’informazione (ad es.
OSPF, RIP, IGRP)– AS_PATH: sequenza di AS attraversati– NEXT_HOP: prossimo router
F. Musumeci – FIR: Strato di rete 83
BGPPath vector (2)
• Ogni router BGP invia il proprio path vector ai router BGP vicini (peers)• L’informazione del path vector è trasmessa su connessioni TCP
– La connessione TCP è aperta dal trasmittente verso il router vicino – BGP usa la well-known port #179
• Tipi di messaggio:– OPEN: apre la connessione TCP e gestisce l’autenticazione
reciproca dei router– UPDATE: annuncia una nuova rotta (o ne annulla una vecchia)– KEEPALIVE: mantiene attiva la connessione in caso di assenza di
UPDATE (usato anche come ACK ai messaggi OPEN)– NOTIFICATION: notifica errori in messaggi precedenti (usato anche
per chiudere la connessione)
84F. Musumeci – FIR: Strato di rete
BGPScambio dei messaggi
• Messaggi eBGP iniziali inviati tramite connessioni TCP– R2 R3: N1, N2, R2, AS1
– R3 R2: N3, N4, N5, N6, R3, AS2
– R6 R7: N3, N4, N5, N6, R6, AS2
– R7 R6: N7, N8, R7, AS3
• Messaggi iBGP scambiati internamente agli AS ed altri messaggi eBGP– R3 R2: N7, N8, R3, AS2 AS3
– …
BGPEsempio
85
AS2
N6
N5
N4
AS1 AS3
N7N8
R1
R2 R3
R4
R5
R6
R7N2
N3
N1
F. Musumeci – FIR: Strato di rete
• BGP consente di distribuire informazioni su un percorso verso una destinazione
• ... ma in realtà l’amministratore dell’AS è libero di– scegliere come fare l’instradamento – decidere se propagare l’informazione ad altri ASPolicy based routing
F. Musumeci – FIR: Strato di rete 86
BGPPolicy based routing
• Un router BGP che riceve un path vector da un peer può decidere di effettuare o meno quanto segue:– Aggiungere alla propria tabella di routing la destinazione
specificata dal path vector– Inoltrare il path vector ai suoi vicini
• In base alla politica di routing implementata localmente• Agli AS è assegnato un Autonomous System Number
(ASN) globale da IANA (come per indirizzi IP)
Policy based routing
F. Musumeci – FIR: Strato di rete 87
• B non modifica la propria tabella di routing e non inoltra il path vector ricevuto da A perché è contro alla politica di routing locale
Policy based routing: esempio 1
A B
D
C
N01, RD, D
N01, RA, A-D
Rete Router successivo
Percorso
N01 RD D
F. Musumeci – FIR: Strato di rete 88
AutonomousSystem
• D non modifica la propria tabella di routing e non inoltra il path vector ricevuto da B perché nel percorso specificato è indicato anche l’AS di cui fa parte.
Policy based routing: esempio 2
A B
D
Rete Router successivo
Percorso
N01 RD D
N01, RD, D
Rete Router successivo
Percorso
N01 RA A-D
N1, RB, B-A-D
N01, RA, A-D
F. Musumeci – FIR: Strato di rete 89
• D non vuole inoltrare traffico tra A e B, dunque non inoltra il path vector ricevuto da B ad A, e viceversa.
Policy based routing: esempio 3
A B
D
Rete Router successivo
Percorso
N01 RA A-X-Y
N01, RA, A-X-Y
Rete Router successivo
Percorso
N02 RB B-W-H
N02, RB, B-W-H
F. Musumeci – FIR: Strato di rete 90
Top Related