Routing in Internet
 Internet consiste di Sistemi Autonomi (Autonomous
Systems AS) interconnessi fra loro:



Stub AS: piccolo
Multihomed AS: grande (no transit)
Transit AS: provider
 Routing a due livelli:
 Intra-AS: amministratore e’ responsabile per la scelta
 Inter-AS: standard unico
4: Network Layer
4a-1
Formato datagramma IP
numero versione
protocol lo IP
lunghezza
header (bytes)
“type” di dati
max number
hop rimanenti
(decrementato
a ogni router)
protocollo strato
super. a cui dare
payload
32 bits
head. type of
length
len service
fragment
16-bit identifier flgs
offset
time to upper
Internet
layer
live
checksum
ver
lunghezza total
datagramma (bytes
usato per
frammentazione/
riassemblamento
32 bit source IP address
32 bit destination IP address
Options (if any)
data
(lunghezza variabile
di solito un segmentop
TCP o UDP)
P.es. timestamp,
percorso seguito,
specifica lista di
routers da visitare
4: Network Layer
4a-2
Frammentazione/ Riassemblamento
 link di rete hanno un limite
sulla max dimens. pacchetto
trasferibile MTU.
 diversi tipi di link, diverse
MTU
 datagrammi IP grandi sono
divisi (“frammentati”) nella
rete
 un datagramma diviene
diversi datagrammi
 “riassemblamento” e’ fatto
solo alla destinaz. finale
 intestazione IP e’ usata
per identificare e ordinare
frammenti correlati
framentazione :
in: un datagramma
out: 3 datagrammi
reassembly
4: Network Layer
4a-3
Frammentazione/ Riassembl. IP
length ID fragflag offset
=4000 =x
=0
=0
un datagramma grande e’ frammentato in
diversi datagrammi piu’ piccoli
length ID fragflag offset
=1500 =x
=1
=0
length ID fragflag offset
=1500 =x
=1
=1480
length ID fragflag offset
=1040 =x
=0
=2960
4: Network Layer
4a-4
ICMP: Internet Control Message Protocol
 usato da host, routers,
gateways per comunicare a
livello di rete
 error reporting: host non
raggiungibile, network,
port, protocol
 richiesta/ replica di echo
(p.es. ping)
 strato di rete “sopra” IP:

Type
0
3
3
3
3
3
3
4
Code
0
0
1
2
3
6
7
0
8
9
10
11
12
0
0
0
0
0
msg ICMP usano datagr. IP
 messaggio ICMP : tipo, codice,
piu’ 8 bytes di datagramma IP
che da’ errore
descrizione
risposta echo (ping)
rete dest. non raggiung.
host dest non raggiung.
protocollo dest non raggiung.
porta dest non raggiung.
rete dest ignota
dest host ignoto
source quench (controllo
congestione)
richiesta di echo (ping)
annuncio route
scoperta di un router
TTL e’ spirato
header IP errato
4: Network Layer
4a-5
Internet : Gerarchia di AS
4: Network Layer
4a-6
Intra-AS Routing
 Noto anche come Interior Gateway Protocols (IGP)
 Diversi protocolli IGP, piu’ comuni:

RIP: Routing Information Protocol

OSPF: Open Shortest Path First

IGRP: Interior Gateway Routing Protocol (Cisco
propr.)
4: Network Layer
4a-7
RIP ( Routing Information Protocol)
 Basato su Distance vector
 Incluso in BSD-UNIX (1982)
 Metrica della distanza: # di salti (hops) (max = 15
hops)
 Vettore Distanze: scambiato ogni 30 sec via un
Response Message (anche detto Advertisement)
 Ogni Advertisement contiene fino a 25 reti
destinazione
4: Network Layer
4a-8
RIP (Routing Information Protocol)
Destination Network
1
20
30
10
….
Next Router
A
B
B
-….
Num. of hops to dest.
2
2
7
1
....
4: Network Layer
4a-9
RIP: Interruzione Link (Link Failur)
 Se non c’e’ messaggio di avvertimento dopo 180 sec, il




link e’ considerato morto
Routes via il vicino sono rese non valide; un nuovo
avvertimento e’ mandato ai vicini
Vicini propagano informazione (se le loro tavole
cambiano)
Notizia dell’interruzione si propaga velocemente a
tutta la rete
Si usa “Poison reverse” per prevenire cicli (si assume
che distanza infinita = 16 hops)
4: Network Layer 4a-10
Processamento Tavole RIP
 Le tavole di routing RIP sono elaborate da un
processo a livello applicazione detto route-d
(route daemon)
 Gli Avvertiemnti sono incapsulati in pacchetti UDP
(non si richiede consegna affidabile; gli
avvertimenti sono mandati periodicamente)
4: Network Layer 4a-11
Processamento Tavole RIP
4: Network Layer 4a-12
RIP Table example (continued)
Esempio Tavola RIP
Three attached class C networks (LANs)
 Router only knows routes to attached LANs
 Default router used to “go up”
 Route multicast address: 224.0.0.0
 Loopback interface (for debugging)
4: Network Layer 4a-13
RIP Table example
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
4: Network Layer 4a-14
OSPF (Open Shortest Path First)
 “open”: disponibile pubblico
 Usa algortimo di Link State
 pacchetti LS sono disseminati
 Ogni nodo conosce la topologia della rete
 Calcolo Route con Dijkstra
 Avvertimento OSPF ha un’informazione per router
vicino
 Avvertimenti disseminati a tutti i Sistemi Autonomi
(via flooding)
4: Network Layer 4a-15
Caratteristiche “avanzate” di OSPF
(non in RIP)
 Sicurezza: tutti i messaggi OSPF sono autenticati
(per prevenire intrusioni maliziose); si usano
connessioni TCP
 Cammini multipli sono possibili (con lo stesso costo) (in
RIP uno solo)
 Per ogni link, si hanno metriche diverse per servizi con
diversa qulita’ di servizio (QoS) (p. es. costo link
satellite e’ “basso” per best effort; alto per real
time)
 Supporto multicast integrato:

Multicast OSPF (MOSPF) usa stesso data base di OSPF
 OSPF gerarchico in domini grandi
4: Network Layer 4a-16
OSPF Gerarchico
4: Network Layer 4a-17
OSPF Gerarchico
 Gerarchia a due livelli: local area e backbone.
 Avvertimenti Link-state non lasciano rispettive aree.
 I nodi in ogni area hanno una topologia dettagliata dell’area ma
conoscono solo la direzione verso reti in altre aree.
 Router “Area Border”: “riassumono” distanze a reti nell’area e
avvertono altri router tipo Area Border.
 Backbone routers eseguono algoritmo OSPF solo per la
backbone.
 Boundary routers si connettono a altri Sistemi Autnomi (AS).
4: Network Layer 4a-18
IGRP (Interior Gateway Routing Protocol)
 Proprieta’ CISCO; successore di RIP
 Distance Vector (come RIP)
 diverse metriche di costo (ritardo, banda,
affidabilita’, carico ecc. )
 usa TCP per scambiare aggiornamenti
 tavole di routing sono scambiate solo quando si
modificano costi
 Algoritmo di routing e’ DUAL (Distributed
Updating Alg.) e’ libero da cicli: dopo incremeno di
distanza, la tavola di routing e’ congelata finoa
quando tutti i nodi influenzati sanno del
cambiamento.
4: Network Layer 4a-19
Routing Inter-AS
4: Network Layer 4a-20
Routing Inter-AS (cont)
 BGP (Border Gateway Protocol): standard di fatto
 Protocollo Path Vector estende Distance Vector
 ogni Border Gateway comunica a tutti i vicini
(broadcast) tutto il cammino (cioe’ la seq. di AS)
fino a destinazione
 Ad esempio, gateway X puo’ memorizzare per la
destinazione Z il cammino:
Path (X,Z) = X,Y1,Y2,Y3,…,Z
4: Network Layer 4a-21
Inter-AS routing (cont)
 Se il Gwy X manda il suo cammino a Gwy peer W
 Gwy W puo’ o non puo’ selezionare il cammino offerto
da Gwy X, per il costo o per questioni politicheeconomiche o per ragioni di loop.
 Se Gwy W seleziona il cammino annunciato da Gwy X:
Path (W,Z) = w, Path (X,Z)
Nota: la selezione del cammino e’ basata piu’ che sul
costo (ad es. # di AS hops), ma piu’ su aspetti politici
e amministrativi (p.es. non passare attraverso
concorrenti)
4: Network Layer 4a-22
Inter-AS routing (cont)
Peers scambiano messaggi BGP usando TCP;
diversi tipi di messaggi:
 OPEN msg apre connessione TCP e autentica mitt.
 UPDATE msg avverte di una modifica (un nuovo
cammino o eliminazione di un cammino)
 KEEPALIVE msg mantiene connessione attiva in
assenza di UPDATES; da’ anche ACK a rich. OPEN
 NOTIFICATION msg riporta errori in messggi
precedenti e chiude connessione
4: Network Layer 4a-23
Perche’ diversi routing Intra- and Inter-AS?
 Politica: Inter si concentra con aspetti politici (quale
provider scegliere o evitare); Intra si applica in una
singola organizzaz. cui si applica stessa politica
 Dimensioni: In questo modo si realizza un routing
gerarchico e si diminuisce il traffico per aggiornare le
tavole di routing
 Prestazioni: Intra si concentra su prestazioni; in
Inter e’ difficile propagare velocemente informazioni
su costi (latenza, riservatezza ecc.); inoltre aspetti
politici sono prevalenti.
4: Network Layer 4a-24