Protocolli di routing e stack TCP/IP
X-Windows
Telnet
NIS
NFS
SNMP
FTP
Upper Layers
BGP
Transport
TCP
ARP
RARP
Nework
Data Link
ICMP
RPC
RIP
UDP
EGP
OSPF IGRP
IP
Hello
Protocolli di routing
Algoritmo
Link
State
Distance
Vector
Protocollo
Dijkstra SPF
OSPF
Bellman-Ford,
DUAL
EGP, RIP, IGRP
EIGRP
R1
N
C
12.0.0.0 4
20.0.0.0 30
30.0.0.0 30
40.0.0.0 35
Vettore delle
distanze di R1
N = Network
C = Costo
NH = Next Hop
Distance Vector
R2
N
C
12.0.0.0 0
20.0.0.0 10
30.0.0.0 10
40.0.0.0 15
R3
N
C NH
12.0.0.0 9 R1
20.0.0.0 15 R4
30.0.0.0 25 R2
40.0.0.0 15 R4
Tabella di
routing di R3
Vettore delle
distanze di R2
R4
N
10.0.0.0
20.0.0.0
30.0.0.0
40.0.0.0
C
15
10
30
10
Vettore delle
distanze di R4
1) quando riceve un messaggio da un router adiacente confronta ogni coppia
(destinazione, costo) col contenuto della tabella di routing:
a)
se la destinazione non è in tabella e il costo dell’annuncio non è infinito
allora crea una nuova entry per la nuova destinazione e fa partire un timout timer
per la nuova entry;
b) se la destinazione è in tabella e il next hop è il router adiacente che ha fatto
l’annuncio allora aggiorna il costo ed il next hop nella entry e fa ripartire il
timeout timer;
c) se la destinazione è nella tabella e il costo indica un percorso migliore
allora aggiorna il costo e fa ripartire il timeout timer;
2) quando scatta il timeout timer pone il costo a infinito e fa partire il
garbage collection timer;
3) quando scatta il garbage collection timer cancella la entry dalla tabella di routing;
4) ad intervalli regolari trasmette ai router adiacenti un messaggio che riporta tutte le
coppie (destinazione, costo) contenute nella tabella di routing.
Distance vector algorithm
Loop
A
L1
B
Tabella di instradamento di B dopo la caduta del link
B --> ?
Link
B
A
C
local
1
2
Cost=
hops
0
1
inf.
C
L2
Distance Vector proveniente da A
A --> ?
Link
A
B
C
local
1
1
per evitare i loop :
when cos t  16  cos t  
Cost=
hops
0
1
2
Distance Vector: cold start
Cold start:
condizione in cui gli apparati inziano a funzionare tutti
contemporaneamente
Inizialmete tutti i sistemi dispongono di distance vector
che rappresentano se stessi e le stazioni ad essi direttamente
collegate
•Protocolli “neighbour greetings”
•Configurazione manuale
Distance Vector: caratteristiche
• Vantaggi:
– semplice da implementare;
– non appesantisce il router in termini di capacità elaborativa e
memoria occupata.
• Svantaggi:
– possono innescarsi dei loop a causa di particolari variazioni
della topologia;
– converge alla velocità del link più lento e del router più lento;
– difficile capirne e prevederne il comportamento su reti grandi:
nessun nodo ha una mappa della rete (conoscenza locale);
– l’implementazione di meccanismi migliorativi appesantisce
notevolmente il protocollo;
– hop-count-limit impone l’impiego di questo algoritmo in reti
piccole con pochi hop.
Routing InformationProtocol (RIP)
• è stato originariamente progettato da Xerox
per la rete XNS.
• È stato introdotto dall’università di
Berkeley nell’architettura TCP/IP nel 1982,
• Definito come RFC 1058 nel 1988 e
aggiornato come RFC 1388 nel 1993.
RIP (costo=num hops)
A
Distance Vector di A
A --> ? Cost
B
1
64kb/s
L8
A
B
D
C
E
0
1
1
2
2
L2
F
L3
L4
1 Mb/S 1 Mb/S
L7
L6
L5
D
Distance Vector di D
D --> ? Cost
D
A
B
E
C
0
1
2
1
2
C
E
Tabella di instradamento di F
F --> ? Link Cost
F
A
B
C
D
E
local
8
8
7
7
7
0
1
2
3
1
2
A parità di
metriche si
prende l’entry
del DV arrivato
per primo
RIP: Timer
•routing update timer = 30s (intervallo di tempo per l’invio
periodico dei distance vector);
•route invalid timer = 180s (intervallo di tempo dopo cui
una route è dichiarata non più valida (cost = infinito));
Routing update in broadcast
No discovery!
Loop
A = 4 Hop
A = 2 Hop
Net A
Net D
R1
X
E0
R2
Net B
S0
S0
R3
Net C
S1
S0
E0
A = 3 Hop
A = 5 Hop
hop-count-limit in RIP è 15
(16=infinito)
Limite nella dimensione della rete
(RIP per reti al massimo di 1000 nodi.)
Opzioni per la stabilità
• Le opzioni usate in RIP per migliorare la stabilità sono:
– Split Horizon: un router non annuncia una destinazione sull’interfaccia da
cui l’ha appresa
– Split Horizon with Poisonous Reverse:
se un router perde la connettività verso una rete, dopo aver inserito il
valore 16 (inf) nella entry, la mantiene invariata per un determinato
numero di periodi di routing updated; inoltre annuncia in broadcast con
valore infinito (16) il costo per raggiungere quella rete.
Convergenza ancora lenta…
– Triggered update ( inviati immediatamente a fronte di cambiamenti nella
rete)
Loop che coinvolgono più di 2 router…
RIP: formato del pacchetto
command
version
zero
address family identifier(IP=2)
zero
IP address
zero
zero
metric
........
UDP port n° 520
RIP: sintesi
•
•
•
•
•
•
•
•
Largamente disponibile
Facile da implementare
Metrica basata su numero di hop
Update periodici (ogni 30 sec.) inviati in broadcast
Convergenza lenta
Routing loops
Count to infinity
No load balancing
RIP versione 2
•
•
•
•
RFC 1723
Può interoperare con RIPv1
Permette di trasferire anche le netmask
Routing Update trasmessi in multicast
– all’indirizzo di classe D 224.0.0.9
• E’ possibile effettuare l’autenticazione dei
messaggi
• E’ possibile il subnetting solo se tutti i router della
rete hanno la stessa versione (es. RIP2).
RIPv2: routing update in multicast
I messaggi di update vengono trasmessi in
multicast (indirizzo di classe D: 224.0.0.9)
RIPv2: formato del pacchetto
command
version
routing domain
address family identifier
route tag
IP address
subnet mask
next hop
metric
IGRP
• Protocollo Distance Vector proprietario Cisco
• Supera i limiti di RIP
• Metriche sofisticate contenenti:
– ritardo (non misurato, ma associato secondo valori
predefiniti a ciascun tipo di sottorete trasmissiva)
– banda
si tratta di parametri configurati dal gestore in
modo
statico;
se
fossero
misurati
– affidabilità
automaticamente, per via dei diversi istanti di
misura attuati dai router, si potrebbero
– carico
• Trasporta anche:
innescare dei loop)
–numero Hop
– lunghezza massima del pacchetto
Annunci dell’IGRP vengono inviati ogni 90 secondi
Metrica IGRP
D - delay
(1 - 224) (1 = 10 s)
R - reliability (1 - 255) (255 = 100%)
L - load
(0 - 255) (255 = 100%)
B - bandwidth
(1.2 - 107)
(1 = 1 kbit/s)
Bandwidth e Delay sono per default associati al tipo di portante fisico. Es.:
Ethernet
-> B=10000, D=100
CDN 64 kbit/s
-> B=64, D=2000
Per ciascun link B e D possono comunque essere impostati dal gestore
Su un determinato percorso:
B è calcolata come il minimo sul percorso
D è calcolato come la somma sul percorso
Il gestore può impostare 5 parametri di peso: k1, k2, k3, k4, k5
Se k5 = 0 :
Metrica = (107/ B) [k1+ k2 / (256-L)] + k3 x D
Se k5 ‡ 0 : Metrica = Metrica x [ k5 / (R + k4) ]
Per default : k1=k3=1; k2=k4=k5=0.
IGRP: multipath routing e load
balancing
• Più entry per una stessa destinazione vengono installate nella tabella di
routing (max 6 righe)
• Il carico può essere ripartito tra le diverse route in funzione della
metrica associata: la distribuzione dei pacchetti su link differenti, verso
la stessa destinazione avviene in misura inversamente proporzionale al
costo espresso nella tabella.
• Sono usate per il multipath routing solo le route con metrica che rientra
nel range definito dal gestore
Link State Protocols
LSP ricevuto
da un’interfaccia
Link-state
database
Algoritmo di
Dijkstra
Tabella di
routing
LSP ritrasmesso su
tutte le altre interfacce
Il Link State Packet (LSP) generato da ogni router contiene:
•identificativo del router che emette il LSP;
•stato di ogni link connesso al router;
•identità di ogni vicino connesso all’altro estremo del link
•costo del link;
•numero di sequenza per il LSP, utilizzato per individuare diverse versioni emesse
dallo stesso router per scegliere la più recente.
Flooding (1)
A
E
B
LSP
LSP
LSP
D
C
Flooding (2)
A
B
D
C
E
I router A, C, E ritrasmettono il LSP di D su tutte le
interfacce tranne quella da cui lo hanno ricevuto
LSP Database
Costo
A
C
2
1
3
B
LSP DataBase
D
A
B
C
D
E
F
G
H
2
1
E
2
5
1
F
E/2
G/1
G/2
H/1
(replicato su ogni Router )
G
4
B/2
A/2 D/3
D/1
B/3 C/1
B/2 F/5
E/5 H/4
D/1 E/2
F/4 G/1
H
Tabella di routing:
algoritmo di Dijkstra
A
C
2
1
L 1
Tabella di
3
B
routing di B
D
L 2
A
C
D
E
F
G
H
L 3
2
E
2
5
G
1
F
H
L1
L2
L2
L3
L3
L3
L3
Link State: caratteristiche
• Vantaggi:
–
–
–
–
può gestire reti di grandi dimensioni;
ha una convergenza rapida;
difficilmente genera loop;
ogni nodo ha la mappa della rete.
• Svantaggi:
– molto complesso da realizzare (la prima
implementazione ha richiesto a Digital 5 anni);
• È utilizzato nello standard ISO 10589 (IS-IS) e nel
protocollo OSPF (molto diffuso su reti TCP/IP di
grandi dimensioni).
OSPF [Open Shortest Path First]
• Protocollo di tipo link state
• Definito dall’IETF:
– RFC 1247 (1991)
– RFC 1583 (1994) - OSPFv2
OSPF [Open Shortest Path First]
•
•
•
•
•
•
•
Type of service routing
Load balancing (più cammini con lo stesso costo)
Network partition
Message authentication
Network/Subnetw/host_specific routing
Designed_router to accomodate multiaccess net
Virtual Link
Type of service routing
• OSPF consente l’uso di una metrica per ciascuna delle
codifiche ammesse nel campo TOS di IP (D, T, R)
• Ogni LSP puo’ contenere una o piu’ metriche
• Ogni router calcola un albero distinto per ciascuna metrica
• Percorsi diversi per pacchetti con requisiti di servizio
diversi
Esempio di metrica OSPF
RTA
10
128.213.0.0
Costo interfaccia =
108/(bandwidth in bps).
8
RTB
5
5
RTC
192.213.11.0
10
10
RTD
222.211.10.0
5
Load balancing
Algoritmo di Dijkstra
(Approfondimento)
RTA
0
10
10
RTC
RTB
128.213.0.0
510
10
5
RTD
15
5
192.213.11.0
MR
222.211.10.0
195
Designed_router to accomodate
LSA multiaccess net
Designated
router
LSA
LSA
Designated
router
LSA
Designed_router = Pseudo nodo
LAN
Designated
router
A
A
B
D
C
B
LSP
Vicino metrica
LSP
Vicino metrica
A 1
C 1
D 1
Designated
router
D
A 1
C 1
B 1
C
LSP
Vicino metrica
D
A 1
B 1
D 1
Rappresentazione secondo l’algoritmo
Link State della rete LAN
LSP
Vicino metrica
D 1
A
C
B
Rappresentazione a stella della rete LAN
(designed router=pseudo nodo)
Routing gerarchico
La grandezza del database in cui vengono memorizzati i LSP,
il tempo per l’elaborazione delle informazioni di routing e il
volume dei messaggi scambiati aumentano al crescere delle
dimensioni del dominio!
LSP
Database
Area 0
LSP
Database
Area 0
LSP
Database
Area 1
Area #1
Backbone
Area #0
LSP
Area #2
Database
Area 2
LSP
Database
Area 0
LSP
Area #3 Database
Area 3
Network partition
• OSPF ha il concetto di gerarchia
– un AS (dominio OSPF) è suddiviso in aree
– le aree contengono un gruppo di reti contigue
– le aree sono indicate da un area-id su 32 bit
• deve essere specificato per ogni interfaccia
– quando un AS ha più di un’area deve esistere una
backbone area con area-id = 0 e tutte le altre debbono
interconnettersi a questa
OSPF: Topology/Link
State Database
• Un router ha un LSP database distinto per
ogni area alla quale appartiene
• Tutti i router appartenenti alla stessa area
hanno lo stesso database
• Il calcolo SPF è effettuato separatamente
per ciascuna area
• LSP flooding è confinato all’interno di
un’area
Classificazione dei router
Internal Router
Area 2
Area 3
Area 0
Area Border Router
Backbone Router
Area 4
Verso altri domini
Autonomous System
Boundary Router
Ogni area non backbone ha bisogno di un router
di frontiera ABR verso l’area 0 da cui riceve
informazioni sulle destinazioni esterne e in cui
inietta informazioni sulle proprie reti.
Aree non direttamente connesse con il
backbone:Virtual Link
Backbone
Area 0
RouterB
Area 2
RouterA
Virtual Link
Area 1
I virtual link sono link logici punto-punto tra coppie di ABR
che hanno un’area non backbone in comune (detta transit area)
OSPF protocol:
Header comune
vers
type
length
Router ID
Area ID
checksum
autype
authentication
authentication
OSPF protocol: Type
Type
Meaning
1
Hello
2
Database description
3
Link status request
4
Link status update
5
Link status acknowledgement
Hello Protocol
Hello
FDDI
Hello
Hello
Il protocollo di Hello è usato per:
- monitorare quali router siano attivi;
- monitorare quali link siano in funzione;
-eleggere il designated-router e il backup-designated-router
nelle reti multi-accesso broadcast e non broadcast.
Principali campi del pacchetto di Hello
BACKUP
}
ripetuto
per ogni
neighbor
Due router sono vicini o neighbor quando ognuno si riconosce
nel pacchetto di hello dell’altro.
Database Description message
L’adiacenza è lo step successivo al processo di neighboring. I router adiacenti vanno
oltre lo scambio dei pacchetti di Hello e procedono allo scambio dei database.
Due router diventano adiacenti quando si sincronizzano, cioè quando verificano la
situazione dei propri database e si portano in uno stato comune . A tale scopo si utilizza
il Database Description Message.
LINK STATE REQUEST
LINK STATE UPDATE
Link state advertisment
Adiacenze su LAN
2-Way
Ma non adiacenti
DR
BDR
Vengono eletti il DR e il BDR
Sulla LAN tutti i router stabiliscono relazioni di neighbor del
tipo two-way tra di loro, ma un router diventa adiacente solo con il
DR e con il BDR. La sincronizzazione di tutti i router con il DR e con
il BDR fa sì che tutti i router abbiano tutti lo stesso database.
Tipi di route
(approfondimento )
• Un cammino selezionato da OSPF può
essere:
– intra-area: se è interno ad un’area OSPF
– inter-area: se oltrepassa i limiti delle aree
– external: se oltrepassa i limiti del dominio
OSPF
Design Tips
• Numero di router per area:
– tipicamente il numero massimo è di 40/50 router per
area
• Numero di neighbors:
– minore è il numero di neighbors presenti su una LAN
minori sono il numero di adiacenze che un DR o un
BDR deve formare
– se possibile, evitare che uno stesso router sia DR su più
di un segmento
• Numero di aree per ABR
– gli ABRs mantengono una copia del database per
ciascuna delle aree servite
– un router non deve stare in più di tre aree, la backbone
area più una o due aree non backbone
OSPF vs RIP
OSPF
RIP
Scalabilità
Buona
Bassa
Banda
Bassa
Alta
Memoria
Alta
Bassa
CPU
Alta
Bassa
Veloce
Lenta
Moderata
Facile
Convergenza
Configurazione
Algoritmi utilizzati per propagare le
informazioni relative al routing
nel core system.
Vector Distance
Shortest
Path First
(OSPF)
(GGP)
Usato oggi nel Core
in Internet
EGP e IGP
AS3
AS2
R
R
R
R
R
R
R
R
R
R
R
R
R
R
R
R
R
Dominio A
MR
IGP
EGP
R
R
Dominio B
AS1
218
Problema dell’istradamento InterAS
•
Le dimensioni: un router della rete backbone deve essere
in grado di istradare verso una qualsiasi rete in Internet
(anche con l’ausilio di CIRD tali router gestiscono circa
140.000 prefissi..)
• I vari AS utilizzano diversi protocolli di routing e quindi
diverse metriche; confrontare i valori di tali metriche
potrebbe non aver senso.
Trovare un percorso “qualsiasi” che permetta di raggiungere
la destinazione senza loop
EGP
AS34
AS1
Net1
Net1
Net16
AS8
For net in AS1 to send traffic to net in AS16:
• AS16 must announce to AS8.
• AS8 must accept from AS16.
• AS8 must announce to AS1 or AS34.
• AS1 must accept from AS8 or AS34.
For two-way packet flow, similar policies must exist
from AS1 to AS16.
AS16
Funzioni del protocollo EGP
Neighbor acquisition
Acquisition request
Acquisition confirm
Acquisition refuse
Cease request
Cease confirm
Neighbor reachability
Hello
I-heard-you
Routing update
Poll request
Routing update
Error response
Error
Richiede ad un router di divenire un neighbor
Il router accetta
Il router rifiuta
Richiede la fine della relazione
Conferma la fine della relazione
Richiede al neighbor di confermare la relazione
precedentemente stabilita
Conferma
Richiede l'update della network reachability
Informazioni di network reachability (solo reti
interne all’AS se il router non appartiene al Core system)
Risposta a messaggi scorretti
EGP:routing update
No Loop!
EGP HEADER
EGP: svantaggi
• EGP presuppone una relazione “padre/figlio
tra i border gateway. Ciò perche’ EGP è
stato definito quando Internet aveva una
struttura ad albero!
Border Gateway Protocol
• Router adiacenti comunicano attraverso una
connessione di livello trasporto affidabile
– TCP port 179
• Protocollo Distance Vector (Path Vector)
• Per ogni destinazione IP è fornita la sequenza di
Autonomous System (AS) da attraversare
– ognuno è identificato con 2 ottetti
– nel distance vector puro è indicato solamente il costo
– non c’è il problema del conteggio a infinito (“countingto-infinity”)
MR
219
Peers (Approfondimento)
R
Peer
AS3
AS2
R
R
eBGP
eBGP
R
R
R
R
R
R
R
iBGP
R
R
AS1
MR
220
Messaggi BGP
•
•
•
•
Open
Update
Keepalive
Notification
Header comune
Marker
dimensione
tipo
Marker: campo a 16 byte riservato all’autenticazione
Dimensione: dimensione complessiva del messaggio
Tipo: tipo di pacchetto
Messaggio Open
Marker
dimensione
tipo
versione
mio AS
Hold time
Router che ha inviato mess. open
opt dimens.
options
Un BGR crea una relazione di prossimità aprendo una
connessione TCP con il vicino e inviandogli un messaggio
di OPEN
Messaggio update
Marker
dimensione
tipo
Unfeasible route len.
Unfeasible route len
Percorsi annullati
.
Attributi percorso
Path attribute len
Rete notificata
Usato per annullare destinazioni già notificate o per notificare
un percorso verso nuove destinazioni
Messaggio keep-alive
Marker
dimensione
tipo
Messaggio Notification
Marker
dimensione
tipo
Error sub-code
Error data
Error code.
AS200
Processo di decisione
• Per quanto riguarda il processo di decisione, occorre osservare
quanto segue:
– BGP mantiene un solo path-vector per destinazione: il best-path.
La scelta è effettuata in base ad attributi contenuti negli annunci
(AS_PATH) e a politiche di routing implementate (route-map,
access-list) sul router.
– Il path-vector di un annuncio indica quali AS bisogna attraversare
per raggiungere una certa destinazione.
– L’exterior router può scegliere, tra diversi annunci, di mantenere in
memoria ed usare quello relativo a degli AS con cui il proprio AS
ha degli accordi per il trasporto di traffico.
– Anche gli annunci da propagare vengono scelti in base a politiche
di routing; in genere BGP annuncia ai suoi neighbor solo il bestpath.
CIDR (1) (Approfondimento)
198.32.0.0/24
198.32.1.0/24
Senza CIDR
.
.
.
198.32.7.0/24
198.32.0.0/24
198.32.1.0/24
198.32.2.0/24
198.32.3.0/24
198.32.6.0/24
198.32.7.0/24
198.32.4.0/24
198.32.5.0/24
198.32.3.0
198.32.0.0
Token
Ring
198.32.1.0
MR
Token
Ring
Token
Ring
198.32.2.0
Token
Ring
Token
Ring
198.32.5.0
198.32.4.0
Token
Ring
198.32.7.0
198.32.6.0
221
CIDR (2) (Approfondimento)
Con CIDR
198.32.0.0/21
198.32.0.0/22
198.32.6.0/23
198.32.4.0/23
198.32.3.0
198.32.0.0
Token
Ring
198.32.1.0
MR
Token
Ring
Token
Ring
198.32.2.0
Token
Ring
Token
Ring
198.32.5.0
198.32.4.0
Token
Ring
198.32.7.0
198.32.6.0
222
Macrolezione 6:
L’interconnessione di reti eterogenee