Prof.

Michele Livio Perilli

Reti di Telecomunicazioni per la Tracciabilità e la Logistica
Dipartimento di Scienze Agrarie, Alimenti, Risorse Naturali e Ingegneria
CORSO DI LAUREA IN INGEGNERIA GESTIONALE
 Lezione 6
Protocolli di Routing
 Esempio di tabelle di routing
Indirizzo Rete Costo Linea di
Destinazione Uscita/Next hop
[Link]/8 …. eth0
[Link]/8 …. eth1
[Link]./24 …. eth0
[Link]./24 …. eth0
[Link]/24 …. eth1
Default Route ….. eth0
3

Docente: Michele Livio Perilli email: [Link]@[Link]

 Operazioni svolte dal router

u Ricerca nella routing table una entry con lo stesso indirizzo di rete del
destinatario
u Se la entry corrisponde ad una rete direttamente connessa al router allora
viene individuata la sottorete e poi il datagram è inoltrato
u Se la entry corrisponde ad una rete remota il datagram è inoltrato
(forwarding)
u Se nessuna entry è trovata allora viene utilizzato il default route

Docente: Michele Livio Perilli email: [Link]@[Link]

 Esempio di tabelle di routing
rete
[Link]
/24

rete
[Link]/8 rete
[Link]
eth0 /24
R1
eth1
rete
rete
[Link]/8 [Link]
/24

Docente: Michele Livio Perilli email: [Link]@[Link]

 Esempio di tabelle di routing
Indirizzo Rete Costo Linea di
Destinazione Uscita/Next hop
[Link]/8 …. eth0
[Link]/8 …. eth1
[Link]./24 …. eth0
[Link]./24 …. eth0
[Link]/24 …. eth1
Default Route ….. eth0
6

Docente: Michele Livio Perilli email: [Link]@[Link]

 Esempio di tabelle di routing
Indirizzo Rete Costo Linea di
Destinazione Uscita/Next hop
[Link]/8 …. eth0
[Link]/8 …. eth1
[Link]./24 …. eth0
[Link]./24 …. eth0
[Link]/24 …. eth1
Default Route ….. eth0
7

Docente: Michele Livio Perilli email: [Link]@[Link]

 Classless Inter Domain Routing (CIDR)

u Si elimina il concetto di classi

u In questo modo è possibile ridurre le dimensioni delle tabelle di routing
u Il formato dell’indirizzo è a.b.c.d/x dove x indica il numero di bit più
significativi che individua la rete
u Es. [Link]/24 e [Link]/24 à [Link]/21 (supernetting)

Docente: Michele Livio Perilli email: [Link]@[Link]

 Metriche per il costo del path

u Si possono utilizzare diverse metriche per definire il costo dei percorsi (path)
verso una data destinazione
u Bandwidth: la capacità di un link (es. generalmente un link a 10 Mbps è preferibile
rispetto ad una linea a 64 kbps)
u Delay: il tempo necessario ad ogni pacchetto per andare dalla sorgente alla destinazione
u Load: il carico di lavoro degli elementi della rete come i router o i link
u Reliability: l’affidabilità è generalmente riferita al tasso di errore di ogni singolo link
u Hop count: il numero di router che un pacchetto deve attraversare per raggiungere la
destinazione
u Ticks: il ritardo un un collegamento dati in multipli di un IBM PC clock tick
(approssimativamente 55 ms)
u Cost: un valore arbitrario, generalmente basato sulla banda, sul costo economico di un
link, o su altre misure stabilite dall’amministratore di rete

Docente: Michele Livio Perilli email: [Link]@[Link]

 Instradamento gerarchico in Internet
u L’insieme di router amministrati dallo stesso gestore è definito
Autonomous System (AS)
u Si distinguono algoritmi di routing intra ed inter AS
u RIP: Routing Information Protocol
u OSPF: Open Short Path First
u BGP: Border Gateway Protocol
interior routing protocol
Autonomous System (intra AS): RIP, OSPF, ecc.

exterior routing protocol

Autonomous System
(inter AS): BGP
10

Docente: Michele Livio Perilli email: [Link]@[Link]

 Distance Vector
u Ogni router invia, periodicamente o quando c’è un cambiamento topologico, il
distance vector (informazioni della propria tabella di routing riguardo i nodi
conosciuti e le relative distanze)
u I router scelgono la strada migliore confrontando i distance vector ricevuti
u Ogni router non conosce l’intera topologia

Distance
Vector

Distance Distance
Vector Vector
Distance
Distance Vector
Vector

Distance
Distance Vector
Vector
Distance
Vector
11

Docente: Michele Livio Perilli email: [Link]@[Link]

 Problemi: Routing Loop

Pippo [Link] Pluto [Link] Topolino

[Link] [Link]

P1 P2 P1 P2 loop P1 P2
X
Destination Cost Line Destination Cost Line Destination Cost Line

[Link] 0 P1 [Link] 1 P1 [Link] 2 P1

[Link] 0 P2 [Link] 0 P1 [Link] 1 P1

[Link] 1 P2 [Link] 0 P2 [Link] 0 P1
[Link] 2 P2 [Link] 1 P2 [Link] 0 P2

Destination Cost Line Destination Cost Line Destination Cost Line

[Link] 2 P1
[Link] 0 P1 [Link] 1 P1
[Link] 1 P1
[Link] 0 P2 [Link] 0 P1
[Link] 0 P1
[Link] 1 P2 [Link] 0 P2
[Link] Down P2
[Link] 2 P2 [Link] 1 P2

Destination Cost Line Destination Cost Line Destination Cost Line

… … … … … … … … …

[Link] 2 P2 [Link] 1 P2 [Link] 2 P1

Destination Cost Line Destination Cost Line Destination Cost Line

… … … … … … … … …
[Link] 4 P2 [Link] 3 P2 [Link] 2 P2

12

Docente: Michele Livio Perilli email: [Link]@[Link]

 Soluzioni

• La definizione di un massimo blocca il “Counting to infinity”

• Per evitare i loop si può usare
Ø Split horizon: non si inviano informazioni su una destinazione (“route”)
all’indietro verso la porta da cui l’informazione è giunta
Ø Split horizon with poisoned reverse: le destinazioni (“route”) vengono
annunciate con metrica “infinity” sulla rete su cui si trova il loro next hop
se apprese da quest’ultimo
Ø Trigger Update: gli aggiornamenti delle tabelle di routing sono inviate
ogni qualvolta vi è un cambiamento topologico e non solo allo scadere del
route timer
Ø Una rete dichiarata irraggiungibile è considerata tale (la sua entry è
eliminata) solo allo scadere di un hold-down timer

13

Docente: Michele Livio Perilli email: [Link]@[Link]

 Routing Information Protocol (RIP)

u È adatto a reti di piccole dimensioni

u È un protocollo di routing di tipo Distance Vector
u Usa come metrica gli hop count
u Il valore massimo è 15; il valore 16 indica rete irraggiungibile
(per evitare il counting to infinity)
u Ne esistono 2 versioni; la seconda cambia il formato dei
pacchetti. In RIPv2 si trasmette la subnetmask e i pacchetti
sono autenticati.
u Ogni router comunica lo stato della propria tabella di
distanze ai router direttamente raggiungibili (routing
update ogni 30 s o ad ogni cambiamento topologico; hold-
down timer pari a 120 s)
u Si utilizza UDP a livello di trasporto per lo scambio di
messaggi RIP (porta 520)

14

Docente: Michele Livio Perilli email: [Link]@[Link]

 Processo di routing update in RIP
Ricezione
Inizio
Routing Update

Elaborazione di una Route,

Metrica = min{Metrica +1, 16}

NO C’è una entry per la stessa

rete da raggiungere
indicata nella route?
NO SI
Metrica=16
SI

NO Metrica dell’update SI
Inserisce la route
in nuova entry inferiore
SI a quella della entry?
Next hop
diverso? SI NO
Next hop
NO uguale
aggiorna sostituisce
SI NO entry route
Metrica
uguale

aggiorna
entry
Azzera SI
route timer Metrica=16
NO

avvia cancellazione
NO entry
elaborata
ultima route?

SI

Fine
15

Docente: Michele Livio Perilli email: [Link]@[Link]

 Open Shortest Path First (OSPF)

u Ogni nodo conosce la topologia della rete (algoritmo Link State)

u Il miglior percorso è determinato con l’algoritmo di Dijkstra
u Possono essere utilizzate molteplici metriche per ognuno dei servizi
previsti dal campo ToS del protocollo IP:
u Banda Disponibile
u Affidabilità
u Ritardo
u ecc.
u Ogni AS è diviso in aree ognuna definita da 4 ottetti (struttura
gerarchica)
u OSPF opera in maniera indipendente in ogni area
u Limitando la dimensione delle aree e i messaggi tra aree, OSPF è
altamente scalabile

16

Docente: Michele Livio Perilli email: [Link]@[Link]

 Link State Advertisement
u Periodicamente, ogni nodo invia lo stato dei suoi collegamenti (Link
State Packet, LSP), cioè indica i nodi con cui è collegato e a quale
costo. In OSPF, ogni LSP contiene più Link State Advertisement (LSA),
che specifica lo stato dei singoli link.
u Ogni LSA è inviato dagli Internal Router ai vicini mediante Selective
Flooding (i pacchetti identici già ricevuti vengono scartati per evitare
loop).
u Ogni LSA contiene il router ID e un sequence number incrementato per ogni nuovo
LSA generato
u Ogni router conserva gli LSA più recenti

Area 3

Area 1
External
Backbone Network
Area (0)

Internal Boundary
AS
Area Border Area 2
17

Docente: Michele Livio Perilli email: [Link]@[Link]

 Propagazione LSA

u I pacchetti OSPF sono direttamente incapsulati in pacchetti IP

(prot. type 0x59)
u L’autenticazione può essere basata su una password in possesso
dei router che comunicano o su meccanismi più complessi di
cifratura
u Le basi dati dei router OSPF devono essere sincronizzate
u Le informazioni di routing di un’area sono diffuse sulla backbone
area dagli area border router e sono propagate fino a raggiungere
gli altri area border router
u La backbone area deve avere alta affidabilità e buone prestazioni
u Con pochi router conviene avere una sola area
u I router conoscono con dettaglio solo la topologia della propria
area
u La ricezione degli LSA può essere confermata con pacchetti di ACK
u Per ridurre l’overhead da segnalazione, il LSP è inviato solo quando
si ha un effettivo cambiamento dello stato dei link, oppure almeno
ogni 30 minuti
18

Docente: Michele Livio Perilli email: [Link]@[Link]

 Border Gateway Protocol (BGP)
u Consente lo scambio di informazioni utili all’instradamento tra router di differenti sistemi
autonomi
u si ottengono informazioni sulla raggiungibilità delle reti da parte degli AS (Autonomous System)
confinanti
u si propagano agli altri AS le informazioni sulla raggiungibilità delle reti interne al proprio AS
u si definiscono i percorsi verso le varie reti sulla base delle informazioni di raggiungibilità e le
politiche adottate
u Vi sono diversi tipi di AS
u Stub AS: trasporta solo traffico di cui è origine o destinazione ed è collegato ad un solo AS esterno
u Multihomed AS: trasporta solo traffico di cui è origine o destinazione ed è collegato a più AS esterno
u Transit AS: è collegato a più AS e trasporta anche traffico tra AS diversi

Stub AS

Multi-Homed AS

19

Transit AS
Docente: Michele Livio Perilli email: [Link]@[Link]
 Principi generali di funzionamento del BGP (1)
u Coppie di router (peer BGP router) si scambiano le informazioni di
instradamento usando una connessione TCP (porta 179)
u Anche router interni di uno stesso AS possono partecipare allo scambio di
informazioni BGP
u Se i router sono interni ad uno stesso AS, si parla di Interior BGP Session
u Se i router appartengono a due differenti AS, si parla di Exterior BGP Session

u Il router di frontiera invia messaggi di open per indicare la sua disponibilità

allo scambio di tabelle di routing
u La richiesta può essere accettata o rifiutata (sulla base degli accordi stipulati)

Peer BGP Peer BGP

Router Router

ext. BGP Session

20

Docente: Michele Livio Perilli email: [Link]@[Link]

 Principi generali di funzionamento del BGP (2)
u Ogni AS ha un identificativo unico (ASN, Autonomous System Number)
u La tabella di instradamento contiene, per ogni rete raggiungibile, la
sequenza di AS da attraversare (approccio path vector)
u Ogni router annuncia le diverse reti (prefissi) utilizzando l’indirizzamento
CIDR ed, eventualmente, aggregando insieme gli indirizzi
u L’annuncio dei router BGP, detto rotta (route), contiene i prefissi e gli
attributi BGP
u Attributi importanti sono
u AS-PATH: elenco degli AS attraverso cui è passato l’annuncio di quel particolare
prefisso
u NEXT-HOP: scelta del nodo successivo nel caso vi siano più rotte per uno stesso
prefisso
u Un router può accettare o meno gli annunci che gli giungono in base alle sue
policy
u Tra le diverse rotte si sceglie quella con AS-PATH più breve; in caso di rotte
con stesso costo, si sceglie quella con NEXT-HOP più vicino; in ultima istanza
ci si basa sugli altri attributi in relazione alla policy adottata
21

Docente: Michele Livio Perilli email: [Link]@[Link]