Lezione 2 – Instradamento
intradominio
Sistemi di elaborazione dell’informazione
Modulo 2 - Protocolli di rete TCP/IP
Unità didattica 7 - Instradamento dinamico
Ernesto Damiani
Protocolli di instradamento intradominio
Interior Gateway Protocols (IGP):
• Routing Information Protocol (RIP).
– Presente in molti sistemi Unix, daemon routed.
• Intermediate System to Intermediate System
(IS-IS).
• Open Shortest Path First (OSPF).
Base di RIP: il routing distance vector
Informazioni limitate sui cammini presenti presso i singoli nodi:
• hop successivo;
• costo.
A
D
Indirizzo
Hop
succ.vo
Costo
Indirizzo
Hop
succ.vo
Costo
A
A
0
A
A
1
B
B
1
B
B
1
C
C
1
C
A
2
D
D
1
D
D
0
E
B
2
E
B
2
F
D
2
F
F
1
G
B
2
G
B
2
H
B
3
H
B
3
A
D
F
C
B
G
E
H
Routing distance vector
• Supponiamo che un nuovo nodo arrivi sulla rete.
I
I
A
D
F
C
B
G
E
H
Indirizzo
Hop
succ.vo
Costo
A
?
∞
B
?
∞
C
?
∞
D
?
∞
E
?
∞
F
?
∞
G
?
∞
H
?
∞
I
I
0
(1)
Routing distance vector
(2)
• Supponiamo che un nuovo nodo arrivi sulla rete.
• Supponiamo che I parli per primo con A.
A
I
A
D
F
C
B
G
E
H
I
Indirizzo
Hop
succ.vo
Costo
0
A
A
1
B
1
B
A
2
C
C
1
C
A
2
D
D
1
D
A
2
E
E
2
E
A
3
F
D
2
F
A
3
G
B
2
G
A
2
H
B
3
H
A
2
I
I
0
Indirizzo
Hop
succ.vo
Costo
A
A
B
Routing distance vector
(3)
• Supponiamo che un nuovo nodo arrivi sulla rete.
• Supponiamo che I parli per primo con A.
• Successivamente I parla con D.
A
D
F
C
B
G
E
I
D
I
H
Indirizzo
Hop
succ.vo
Costo
Indirizzo
Hop
succ.vo
Costo
A
A
1
A
A
1
B
B
1
B
A
2
C
A
2
C
A
2
D
D
0
D
D
1
E
B
2
E
A
3
F
F
1
F
D
2
G
B
2
G
A
2
H
B
3
H
A
2
I
I
0
Algoritmo Distance Vector
• Inizia con tutte le destinazioni a distanza infinita, tranne che
per il nodo stesso, la cui distanza è 0.
• Ogni 30 secondi, o quando si verifica un cambiamento nella
tabella, ogni nodo invia la tabella ai vicini.
• Se un nodo j riceve da un nodo i la distanza dip verso un
prefisso di rete P e questa distanza (più la distanza dji fino a
i) risulta inferiore alla distanza djp (già nota fino a P ), ossia:
djp >= dji + dip,
si aggiorna la distanza verso P e si inviano al nodo i i
pacchetti diretti a P.
Problema del count-to-infinity
A
B
C
D
E




Iniziale
1



1 iterazione
1
2


2 iterazioni
1
2
3

3 iterazioni
1
2
3
4
4 iterazioni
(1)
1. Il tratto da B a A si interrompe e B
cerca un nuovo cammino per A.
2. C annuncia a B che A risulta
raggiungibile tramite lui stesso e la
distanza è 2, ma non dice che il
cammino comprende proprio il
tratto B-A interrotto.
3. Il cammino non è accettabile, ma
al round successivo D annuncia a B
che A risulta raggiungibile tramite
lui stesso e la distanza è 3. Ancora,
il cammino comprende il tratto B-A
interrotto.. E cosi’ via!
A
B
C
D
E
1
2
3
4
Iniziale
3
2
3
4
1 iterazione
3
4
3
4
2 iterazioni
5
3
5
4
3 iterazioni
5
6
5
6
4 iterazioni
Problema count-to-infinity
Il count-to-infinity è un problema:
• genera moltissimi aggiornamenti di instradamento, quindi
causa troppo traffico;
• la rete dovrebbe rilevare che una destinazione è
irraggiungibile.
Una possibile soluzione:
• Limitare superiormente il diametro della rete.
Cosa fare se la rete
cresce?
(2)
Problema count-to-infinity
(3)
Tecniche per ridurre il problema:
• Split horizon: un router non comunica una distanza al vicino
da cui ha appreso la distanza.
• Split horizon con poison reverse: se A annuncia a B la
distanza minima verso un nodo E, B comunica ad A una
distanza infinita verso E.
Queste tecniche funzionano solo per cicli che
coinvolgono due nodi.
Con cicli più lunghi, riducono solo la velocità di
convergenza.
L’unica vera soluzione è usare l’instradamento di
tipo link state: OSPF!
FINE