RETI DI CALCOLATORI II
Facoltà di Ingegneria
Università degli Studi di Udine
Ing. DANIELE DE CANEVA
RETI DI CALCOLATORI II
Facoltà di Ingegneria
Università degli Studi di Udine
a.a. 2009/2010
ARG OM ENT I DELLA LEZIONE
ROUTING DINAMICO
o OSPF o BGP
ROUTING BROADCAST o N VIE
o FLOODING o RPF
o ALBERO DI COPERTURA
ROU TING DINAMICO
ALGORITMO SHORTEST PATH FIRST
Sviluppato nel 1959 da Dijkstra
1. a tutti i percorsi associato un costo infinito
2. si definisce come working node il nodo di origine
3. ciclo che termina quando tutti i nodi hanno etichetta permanente:
I. aggiorna il costo dei nodi adiacenti al working node II. tra tutti i nodi con etichetta non permanente si
definisce come working node quello con costo
minore e si contrassegna la sua etichetta come
permanente
ROU TING DINAMICO
ALGORITMO SHORTEST PATH FIRST
w
z
y
5
2 v
u
x 2
1
5
2 3
1
1
3
w(5,u)
y(∞) v(2,u)
u
x(1,u) 2
1
5
z(∞)
ROU TING DINAMICO
ALGORITMO SHORTEST PATH FIRST
w(4,x)
y(2,u) v(2,u)
u
x(1,u)
z(∞) 3
1 2
ROU TING DINAMICO
ALGORITMO SHORTEST PATH FIRST
w(3,y)
y(2,u) v(2,u)
u
x(1,u)
z(4,y) 2
1
ROU TING DINAMICO
ALGORITMO SHORTEST PATH FIRST
w(3,y)
y(2,u) v(2,u)
u
x(1,u)
z(4,y) 3
ROU TING DINAMICO
ALGORITMO SHORTEST PATH FIRST
w(3,y)
y(2,u) v(2,u)
u
x(1,u)
z(4,y) 5
ROU TING DINAMICO
ALGORITMO SHORTEST PATH FIRST
w(3,y)
y(2,u) v(2,u)
u
x(1,u)
z(4,y)
ROU TING DINAMICO
ALGORITMO SHORTEST PATH FIRST
ROU TING DINAMICO
ALGORITMO SHORTEST PATH FIRST
A
B C
D
E F
G H
7 2
6
1 2
4 2
3 2
3
2
A
B(2,A) C(∞)
D(∞) E(∞) F(∞)
G(6,A) H(∞)
2
6
ROU TING DINAMICO
ALGORITMO SHORTEST PATH FIRST
A
B(2,A) C(9,B)
D(∞) E(4,B) F(∞)
G(6,A) H(∞)
7
2
ROU TING DINAMICO
ALGORITMO SHORTEST PATH FIRST
A
B(2,A) C(9,B)
D(∞) E(4,B) F(6,E)
G(5,E) H(∞)
1 2
ROU TING DINAMICO
ALGORITMO SHORTEST PATH FIRST
A
B(2,A) C(9,B)
D(∞) E(4,B) F(6,E)
G(5,E) 4 H(9,G)
ROU TING DINAMICO
ALGORITMO SHORTEST PATH FIRST
A
B(2,A) C(9,B)
D(∞) E(4,B) F(6,E)
G(5,E) H(8,F)
3 2
ROU TING DINAMICO
ALGORITMO SHORTEST PATH FIRST
D(10,H) A
B(2,A) C(9,B)
E(4,B) F(6,E)
G(5,E) H(8,F)
2
2
ROU TING DINAMICO
ALGORITMO SHORTEST PATH FIRST
A
B(2,A) C(9,B)
D(10,H) E(4,B) F(6,E)
G(5,E) H(8,F)
7 2
6
1 2
4 2
3 2
3
2
ROU TING DINAMICO
ALGORITMO SHORTEST PATH FIRST
ROU TING DINAMICO
OSPF
Sviluppato per dare risposta ai grossi problemi di scalabilità e velocità di convergenza del protocollo RIP
1988 l’IETF iniziò a lavorare su OSPF (Open Shortest Path First), standardizzato nel 1990 con RFC 2338
Attualmente alla versione 2, è utilizzato dagli ISP di livello
superiore
ROU TING DINAMICO - OSPF
OBIETTIVI PERSEGUITI DALL’IETF:
basato su standard aperto
diverse metriche
dinamico e rapido
routing basato su tipo del servizio (type of service IP)
funzionalità rimossa in seguito
supporto per sistemi gerarchici
sicurezza
ROU TING DINAMICO - OSPF
CARATTERISTICHE
triggered updates incrementali
anche periodico (30 min) per robustezza
classless
metrica: non viene imposta una politica dei pesi, costi definiti dall’amministratore
hop
capacità del link = inverso della banda dell’interfaccia
sicurezza: possibile autenticazione
password in chiaro
firma MD5 con numeri di sequenza per protezione da
attacchi ripetuti
ROU TING DINAMICO - OSPF
CARATTERISTICHE
multipath load balancing: fino a 16 equal-cost route per ogni destinazione (utilizzati 4 di def)
supporto multicast: MOSPF
instradamento gerarchico
riconosce aree e AS
ROU TING DINAMICO - OSPF
SVANTAGGI
memoria: più memoria per contenere topologia e tabella routing
carico computazionale: richiede extra CPU (specialmente all’accensione)
design: più complesso per gestire la divisione della gerarchica in aree
configurazione e troubleshooting
ROU TING DINAMICO - OSPF
GERARCHIA
gerarchia a 2 livelli: backbone + aree
area 0 area: gruppo di reti contigue usate per confinare il propagarsi delle informazioni di routing
bene per flapping routes
ROU TING DINAMICO - OSPF
AREE
CARATTERISTICHE:
• non si sovrappongono
• la topologia di un’area è invisibile all’esterno
• tutte le aree sono collegate alla dorsale
ROU TING DINAMICO - OSPF
backbone
Area 1
Area 2
Area 3 boundary
router
backbone router
border router
altro AS
altro AS
internal router
ROU TING DINAMICO - OSPF
4 CLASSI DI ROUTER
• internal router: completamente interno a un’area
• border router: collegamento tra 2 o più aree
• backbone router: appartiene alla dorsale
• boundary router: router di confine con altri AS
le classi possono sovrapporsi! es. router di confine sono
anche di dorsale
ROU TING DINAMICO - OSPF
3 TIPI DI PERCORSO
• intra-area: il router sorgente conosce già il percorso più breve
• inter-area: dalla sorgente alla dorsale, attraverso alla dorsale, fino alla destinazione
• inter-AS
ROU TING DINAMICO - OSPF
ROUTER ID
• ID univoco su tutta la rete
• criteri di scelta dell’ID:
1. l’indirizzo IP più alto sulle interfacce di loopback del router
interfaccia logica e non fisica
1. in assenza di interfacce di loopback viene utilizzato
l’IP più elevato sulle interfacce attive al momento
dell’accensione
ROU TING DINAMICO - OSPF
SCAMBIO LSA
• lo scambio di LSA avviene tra nodi adiacenti
non equivale a dire vicini
una coppia di router devono creare un’adiacenza per essere considerati “neighbors” e scambiare LSA
• i vicini vengono contattati con messaggi di HELLO
poi inviati ogni 10 secondi come keepalive
se keepalive mancanti, dopo 40 sec considerato
guasto
ROU TING DINAMICO - OSPF
SCAMBIO LSA
Per ottenere adiacenza:
• numero area
• tempi di hello e dead sulle interfacce connesse
• password preconfigurata (se presente)
• area stub flag che indica il tipo di area
• dimensione massima MTU sulle interfacce
ROU TING DINAMICO - OSPF
SCAMBIO LSA
raggiunto il two-way state si verifica un processo di elezione
router A router B
HELLO (values)
LSACK
if match
ROU TING DINAMICO - OSPF
SCAMBIO LSA
Per evitare inefficienza viene creato un design client/server per ogni segmento di broadcast
fanno eccezione i point to point WAN
Designated router: nodo che mantiene le informazioni
aggiornate di topologia e le propaga in tutto il segmento di broadcast
Backup designated router: per fault tollerance in caso di guasto del designated router
se DR cade viene sostituito e si elegge un nuovo BDR
Drothers: tutti gli altri nodi
ROU TING DINAMICO - OSPF
ELEZIONE DEL DR
• il router con più alta priorità (su 8 bit da 0 a 255, def 1)
se uguale a zero il router viene escluso dall’elezione
• a parità di priorità si sceglie il router con ID più alto
ID = 10.37.82.1 Priority = 1 A
ID = 10.37.83.37 Priority = 1 B
ID = 10.37.82.40 Priority = 1 C
BDR
ID = 10.37.81.25 Priority = 1 D
ID = 10.37.83.39 Priority = 1 E
DR
ROU TING DINAMICO - OSPF
POST-ELEZIONE DEL DR
! un router può fare capo a più DR/BDR se si affaccia su diversi segmenti broadcast
• si formano coppie master-slave che portano alla sincronizzazione tra DR e router (FULL STATE)
master quello con ID più alto, non necessariamente il DR
utilizzati speciali pacchetti che consentono di
scambiarsi info temporali e fare query
ROU TING DINAMICO - OSPF
POST-ELEZIONE DEL DR
In caso di caduta di un collegamento:
1. il router avvisa il DR (multicast 224.0.0.6)
2. il DR propaga l’info agli altri router del segmento (multicast 224.0.0.5)
anche se trasmissione multicast il DR si aspetta un acknowledge da ogni altro router per conferma ricezione
! per robustezza i DR manda in flooding il suo database dei
collegamenti ogni 30 minuti
ROU TING DINAMICO - OSPF
POST-ELEZIONE DEL DR
A B C
BDR
D E
DR
C invia un messaggio a DR/BDR su
224.0.0.6
DR inoltra
l’informazione a
tutti su 224.0.0.5
AS1
AS2
AS3
IGP
BGP
IGP
IGP BGP
ROU TING DINAMICO - BGP
ROUTING TRA AS
Protocolli diversi per ragioni:
• politico-amministrative
• scalabilità
• prestazioni
ROU TING DINAMICO - BGP
BGP
Attualmente utilizzata la versione 4
definita nelle RFC da 1771 a 1774
std de facto per il routing tra AS
Scopi:
• ottenere info raggiungibilità dagli AS confinanti
• propagare tali info all’interno della propria rete
• determinare i precorsi più brevi verso tali destinazioni
ROU TING DINAMICO - BGP
BGP
Caratteristiche:
• utilizza sessioni TCP semipermanenti sulla porta 173
le connessioni tra i router non corrispondono necessariamente a collegamenti fisici
• le destinazioni non sono host ma prefissi CIDR
• eBGP per scambio dei prefissi
• iBGP per inoltro delle info dentro l’AS
ROU TING DINAMICO - BGP
BGP
AS1
AS2
AS3
iBGP
eBGP
iBGP
iBGP eBGP
ROU TING DINAMICO - BGP
BGP
“route BGP”: prefisso + attributi
tra cui:
• AS_PATH: elenco degli AS attraversati dall’annuncio
ottenuto per accodamento ASN
possibilità di rilevare annunci reiterati
possibilità di scelta tra diversi path
• NEXT_HOP: l’indirizzo IP dell’interfaccia utilizzata
per inoltrare l’annuncio
ROU TING DINAMICO - BGP
BGP
Scelta tra percorsi alternativi:
• attributo di preferenza locale: assegnato
dall’amministratore, si sceglie valore preferenza più alto
• AS_PATH più breve: hop come metrica
• next hop più vicino
hot potato routing
• identificatori BGP
! Nella realtà è più complesso di così
ROU TING DINAMICO - BGP
BGP
Politiche di instradamento:
• solo il traffico che ha origine e/o destinazione in una rete cliente
• accordi di peering: negoziati privati tra ISP
B
A C Z
X
Y
ROU TING DINAMICO - BGP
MULTIPATH ROUTING?
DST
A
B C
D
Host SRC
