Routing in Internet
Crediti
Parte delle slide seguenti sono adattate dalla
versione originale di J.F Kurose and K.W. Ross
(© 1996-2003 All Rights Reserved)
4-1
Routing in Internet
 La “Big” Internet consiste di Autonomous Systems
(AS) interconnessi tra loro:
 Due livelli di routing:


Intra-AS: amministratore di rete sceglie algoritmo di routing
Inter-AS: unico e standard per inter-AS routing: BGP
Inter-AS (exterior gateway) routers
Intra-AS (interior gateway) routers
4-2
Intra-AS Routing
 Detti anche Interior Gateway Protocols (IGP)
 I protocolli di routing Intra-AS più utilizzati:

RIP: Routing Information Protocol

OSPF: Open Shortest Path First

IGRP: Interior Gateway Routing Protocol (Cisco
proprietary)
4-3
RIP ( Routing Information Protocol)
 Algoritmo di tipo Distance Vector
 Incluso nella Distribuzione BSD-UNIX nel 1982
 RFC 1058 (v1), RFC 2453 (v2)
 Metrica di costo: numero di hop (max = 15 hop)
 Distance vectors: scambiati tra i vicini ogni 30 s. via
RIP Response Message (definito anche RIP
advertisement)
 Ogni RIP advertisement: elenca fino a 25 destinazioni
di reti all’interno dell’AS
4-4
RIP: Esempio
z
w
A
x
D
B
y
C
Destination Network
w
y
z
x
….
Next Router
Num. of hops to dest.
….
....
A
B
B
--
2
2
7
1
Routing table in D
4-5
RIP: Esempio
Dest
w
x
z
….
Next
C
…
w
hops
4
...
A
Advertisement
from A to D
z
x
Destination Network
w
y
z
x
….
D
B
C
y
Next Router
Num. of hops to dest.
….
....
A
B
B A
--
Routing table in D
2
2
7 5
1
4-6
RIP: Caduta di un link e recovery
Se nessun “avviso” (advertisement) ricevuto entro 180 s.
--> vicino/link dichiarato irraggiungilbile
 percorsi attraverso il vicino invalidati
 nuovi avvisi inviati ai vicini (ancora raggiungibili)
 vicini a loro volta inviano nuovi avvisi (se le tabelle
sono cambiate)
 l’informazione sulla caduta di un link si propaga
velocemnte per l’intera rete
 poison reverse usato per evitare percorsi ciclici
(distanza infinita = 16 hops)
4-7
RIP: Processamento tabelle di routing
 Routing tables del RIP gestite da un processo a
livello applicazione chiamato routed (daemon)
 Avvisi inviati in pacchetti UDP, ripetuti
periodicamente
routed
routed
Transprt
(UDP)
network
(IP)
link
physical
Transprt
(UDP)
routing
table
routing
table
network
(IP)
link
physical
4-8
RIP: Esempio tabella di routing
Router: giroflee.eurocom.fr
Destination
-------------------127.0.0.1
192.168.2.
193.55.114.
192.168.3.
224.0.0.0
default
Gateway
Flags Ref
Use
Interface
-------------------- ----- ----- ------ --------127.0.0.1
UH
0 26492 lo0
192.168.2.5
U
2
13 fa0
193.55.114.6
U
3 58503 le0
192.168.3.5
U
2
25 qaa0
193.55.114.6
U
3
0 le0
193.55.114.129
UG
0 143454
 Tre reti (LAN) di classe C attaccate
 Il router conosce solo i percorsi alle LAN attaccate
 Default router usato per tutte le altre destinazioni
 Route multicast address: 224.0.0.0
 Interfaccia di loopback (per debugging)
4-9
OSPF (Open Shortest Path First)
 “Open”: disponibile a tutti (v2 in RFC 2178)
 Usa algoritmo Link State
 disseminazione del LS
 mappa topologica completa ad ogni nodo
 calcolo dei percorsi per mezzo dell’algoritmo di Dijkstra
 Router invia info su LS ogni volta che c’è una
variazione (costo o stato)

od ogni 30 minuti
 Avvisi inviati all’intero AS (via broadcast)
 trasportati in messaggi OSPF (protocollo 89) direttamente su
IP (piuttosto che su TCP o UDP)
4-10
Miglioramenti in OSPF (non in RIP)
 Sicurezza: tutti i messaggi OSPF autenticati (per




prevenire intrusioni maliziose)
Percorsi Multipli con lo stesso costo (solo un percorso
in RIP)
Per ogni link, metriche di costo multiple per differenti
TOS (es., costo link satellite posto “low” per best
effort, “high” per real time)
Supporto integrato per routing uni- e multicast:
 Multicast OSPF (MOSPF) usa stesso DB di OSPF
OSPF gerarchico in domini estesi
4-11
OSPF gerarchico
4-12
OSPF gerarchico (cont.)
 Gerarchia a due livelli: area, backbone.
Avviso su link-state solo all’interno dell’area
 ogni nodo ha topologia dettagliata dell’area;
conosce solamente la direzione (shortest path) alle
reti nelle altre aree
Internal router: esegue solo instradamento intra-AS
Area border router: “riassume” le distanze alle reti
della propria area, informa gli altri Area Border
router
Backbone router: esegue OSPF routing limitatamente
al backbone
Boundary router: connette agli altri AS





4-13
Inter-AS routing in Internet: BGP
R4
R5
R3
BGP
AS1
AS2
(RIP intra-AS
routing)
(OSPF
intra-AS
routing)
BGP
R1
R2
AS3
(OSPF intra-AS
routing)
Figure 4.5.2-new2: BGP use for inter-domain routing
4-14
Inter-AS routing in Internet: BGP
 BGP (Border Gateway Protocol): lo standard de
facto
 Path Vector protocol:




simile al Distance Vector protocol
ogni Border Gateway invia in broadcast ai vicini
(peers) l’intero percorso (cioè la sequenza degli AS)
alla destinazione
BGP instrada verso le reti (AS) non verso i singoli
host
Es., Router X può inviare per la destinazione Z (tipo
128.119.40/24)
• il suo percorso : Path (X,Z) = X,Y1,Y2,Y3,…,Z
• l’identità del prossimo router lungo il percorso
4-15
Inter-AS routing in Internet: BGP
Ipotesi: router X invia il suo percorso al pari router W
 W può o no selezionare il percorso offerto da X
 motivi: costo, policy (non instradare attraverso AS
dei competitori), prevenzione dei loop
 Se W seleziona percorso suggerito da X allora:
Path (W,Z) = w, Path (X,Z)
 N.B. X può controllare il traffico entrante
controllando i percorsi da ”suggerire” ai pari:
 es. se non si vuole instradare traffico verso Z ->
non suggerire alcun percorso verso Z
4-16
BGP: controllo dell’instradamento
legend:
B
W
provider
network
X
A
customer
network:
C
Y
Figure 4.5-BGPnew: a simple BGP scenario
 A,B,C sono reti dei provider
 X,W,Y sono clienti (dei network providers)
 X è dual-homed: attaccato a due reti
X non vuole instradare da B via X a C
 .. allora X non informerà B del percorso verso C

4-17
BGP: controllo dell’instradamento
legend:
B
W
provider
network
X
A
customer
network:
C
Y
 A “avvisa” B del percorso AW
Figure 4.5-BGPnew: a simple BGP scenario
 B “avvisa” X del percorso BAW
 Dovrebbe B “avvisare” C del percorso BAW?
 No! B non “guadagna” dall’instradare CBAW poichè nè W nè C
sono clienti di B
 B vuole forzare C a instradare verso W via A
 B vuole instradare solo a/da i suoi clienti!
4-18
BGP: Operazioni
D: Cosa fa un router BGP?
 Riceve e filtra le informazioni ricevute tramite gli
annunci dei vicini direttamente collegati
 Seleziona il percorso
 Per instradare verso la destinazione X, quale
percorso (dei vari percorsi suggeriti) verrà
scelto?
 Politica di instradamento (non specificata in BGP)
 Invia annunci sui percorsi ai vicini
4-19
BGP: messaggi
 Messaggi BGP scambiati usando TCP (port 179)
 Messaggi BGP:
OPEN: apre connessioneTCP con il pari e autentica
il sender
 UPDATE: annuncia nuovo percorso (o rimuove uno
esistente)
 KEEPALIVE mantiene la connessione attiva in
asenza di UPDATE; funziona da ACK alla richiesta
di OPEN
 NOTIFICATION: informa su errori del messaggio
precedente; utilizzato anche per chiudere la
connessione

4-20
Perchè routing differente per Intra- e Inter-AS?
Policy:
 Inter-AS: ogni AS vuole pieno controllo sul traffico
instradato, su chi instrada attraverso la sua rete
 Intra-AS: amministrazione singola, nessuna decisione
politica necessaria
Scalabilità:
 Inter-AS: fondamentale
 Intra-AS: meno vincolante
 routing gerarchico salva la dimensione delle tabelle, riduce
traffico di update
Performance:
 Inter-AS: policy può influire più delle prestazioni
 Intra-AS: può focalizzarsi sulle prestazioni
4-21