Univ. “G. D’ Annunzio”
Corso di “reti di calcolatori e sicurezza”
Prof. Bistarelli
2004/2005 CLEIS
INSTRADAMENTO
IN INTERNET
Micolucci Marianna
n.matr. 3028856
Sommario
 Cos’è
un AS
 Algoritmi di instradamento intra AS (rip e
ospf)
 Algoritmi di instradamento inter AS (bgp)
 Perché protocolli diversi
Protocolli di instradamento
Funzione: determinare il percorso seguito da
un datagram dalla sorgente alla destinazione
2 macroclassi :
protocolli all’interno di un AS (Rip, Ospf)
protocolli tra AS multipli (Bgp)
Sistema Autonomo : AS
I router vengono aggregati in regioni:
Un AS è insieme di routers sotto un'unica
amministrazione tecnica (sotto il controllo di un
unico ente).
Un "AS“ gestisce una propria "politica di routing"
Ogni AS avrà uno o più router responsabili di
instradare I pacchetti all’ esterno ( Exterior
Router Gateway)
A.a, A.c, B.a, C.b sono router gareway
Porzione del percorso che usa il protocollo inter-AS
Porzione del percorso che usa il protocollo intra-AS
C.b
a
C
B.a
A.a
b
A.c
d
A
a
Instradamento inter-AS e intra AS
nel gateway A.c
b
c
a
c
B
b
RIP: Routing Information Protocol
 Protocollo
Distance Vector le (informazioni
sono vettori di percorsi invece che
distanze)
 Link a costo 1
 Max percorso=15
 Scambio tabelle di instradamento (30 sec.)
Messaggio di replica del RIP (Avvisi)
Il router inoltre può:

Modificare la sua
tabella locale di rilancio
(es. dopo 180 sec non
ha notizie da un vicino)
Propagare informazione
ai vicini

Richiedere
informazioni sul costo
dei vicini verso una
destinazione
messaggio di richiesta
Pacchetto RIP

command
Version
(=1)
Address family
Identifier
Must be zero


Must be zero

IP address

Must be zero

Must be zero

Metric
Command : può avere due valori (1
se è un messaggio di richiesta o 2 se
è messaggio di aggiornamento).
Version : per indicare la versione del
protocollo.
Address Family Identifier : è
sempre uguale a 2 per il protocollo
IP
IP Address : è l' indirizzo di
destinazione può essere una rete o
una sottorete
Metric : è l' hop count e puo'
assumere un valore compreso tra 1 e
16.
Campo Zeros Fornisce la
compatibilità verso protocolli
precedenti, inoltre può essere usato
per riservare spazio per utilizzi
futuri.
Tutti i campi sono espressi come
interi a 32 bit che vengono trasmessi
in ordine di rete, ossia prima il byte
piu' significativo.
RIP: come funziona
z
w
A
x
D
B
...
.
y
C
Rete di destinaz.
w
y
z
x
….
Router successivo
A
B
B
-….
Rotabella di routing di D
N.hop verso la dest.
2
2
7
1
....
RIP: come funziona
Dest
w
x
z
….
Succ. N.hops
C
4
…
...
w
A
Avviso dal router A
z
x
Rete di destinazione
w
y
z
x
….
D
B
y
C
Router successivo N.di hop verso la dest.
A
B
B A
-….
Tabella di routing di D dopo l’ avviso di A
2
2
7 5
1
....
Cosa succede ai vari livelli?
 Udp
porta 520
 RIP è un protocollo dello strato dell’
applicazione che funziona su UDP
routed
Trasporto
(UDP)
rete
(IP)
Collegamento
Fisico
routed
Trasporto
(UDP)
tabelle di
rilancio
Rete
Tabelle di
(IP)
rilancio
Collegamento
Fisico
OSPF: Open Shortest Path First
 Protocollo
basato sullo stato dei link
 Suddivisione della rete in parti indipendenti
(aree) connesse attraverso la “backbone”
ciascun router mantiene lo stesso database realizzato mediante lo scambio di
messaggi LSA e calcola il cammino minimo da sé, verso ogni altro router
appartenete alla medesima area, incluso il router che è connesso alla backbone
Il costo del protocollo è proporzionale al formato dell’ area e non
della rete
Miglioramenti di OSPF
 Sicurezza
 Percorsi
multipli con lo stesso costo
 Supporto per instradamento Multicast e
unicast
 Supporto della gerarchia all’ interno del
dominio di un singolo router
Un AS OSPF può essere configurato in aree:
ASBR: Scambia
informazioni di
instradamento con
router di altri AS
Eseguono l’ instradamento
entro la backbone ma non
sono router di bordo area
Sono all’ esterno della
backbone ed eseguono solo
l’ instradamento intra AS
ABR:Appartengono sia ad
un area che alla backbone,
almeno uno per ogni area
I router OSPF della stessa area condividono un database
composto di record link state (LS).
4 tipi con header comune:
router, rete, sommario per rete ip, sommario per router di
confine, esterno
Link_State_ID: identificativo dell’LSA
scelto dall’Advertising Router, ma il
significato preciso può variare a
seconda di Type
Advertising Router: uno degli
indirizzi IP del router (quello
selezionato come OSPF_ROUTER_ID)
Sequence number: puo' variare tra
1-N e N-2, dove N = 231. Quando un
router invia il primo LSA, il numero di
sequenza sara' il numero negativo 1-N;
questo numero verra' regolarmente
incrementato per i successivi LSA.
Lenght: la totale lunghezza del
record, inclusi i 20 bytes dell'header
ROUTER LINK
ADVERTISEMENT

Riporta informazioni su tutti i router adiacenti e
le LAN cllegate
 Propagato solo all’ interno dell’ area
E: se il router è un Area Border Router
(External)
B: se il router è un AS Boundary Router
(Border)
NETWORK LINK ADVERTISEMNT

Generato dal Designed routered elenca tutti i
router presenti sulla LAN
Network Mask: Netmask
della rete di transito
Attached Router:
Indirizzo IP di tutti i router
che vi si affacciano sulla LAN
Link_State_ID
(dell’header LSA): è il
corrispondente indirizzo IP
dell’interfaccia del
Designated Router collegata
alla rete di transito
NETWORK SUMMARY LINK
ADVERTISEMENT
 Generato
da un area border router
(diversi rispetto ad ogni area con cui è
collegato)
 E’ usato dagli ABR per riassumere e
propagare informazioni su un’ area.
EXTERNAL LINK




Riportano le informazioni
relative a destinazioni
esterne al dominio
Sono generati dagli AS
Border Router e vengono
propagati a tutti i router
del dominio OSPF.
Comprendono una
destinazione per LSA
(come i Summary Links).
Campo LS Type = 5
I PROTOCOLLI IN OSPF
•
Hello Exchange
Flooding
•
•
•
•
•
•
Version: Indica la corrente versione di
OSPF
Type: il tipo di pacchetto OSPF
trasportato
Packet Lenght : numero di bytes del
pacchetto
Router_ID: indirizzo IP scelto per
identificare il router
Area_ID: numero che identifica
univocamente l’area all’interno del
dominio Un valore 0 identifica il
backbone.
Checksum: calcolato sull'intero
pacchetto
Authentication Type: Identifica
l'algoritmo di identificazione
0: No authentication
1: Simple authentication
2: Cryptographic authentication
IL PROTOCOLLO "HELLO”
Verifica l’ operatività dei link
 viene trasmesso tra nodi vicini e mai propagato

Network Mask: netmask associata all’interfaccia da cui
viene emesso il pacchetto
Hello Interval: comunica ogni quanti secondi viene
emesso un pacchetto di Hello
Options: vengono definiti solo gli ultimi 2 bit
E: (router è in grado di inviare e ricevere route
esterne) T(il router è in grado di gestire il routing TOS)
Priority: serve per l’elezione del Designed Router e
viene settato da management.
Dead_Interval: intervallo di tempo di validità dei
pacchetti di Hello ricevuti. DR, BDR: indirizzo del
Designated Router
Neighbor: lista di router_ID da cui è stato ricevuto il
pacchetto di Hello negli ultimi Dead_Interval secondi
IL link è dichiarato operativo se i pacchetti possono
scorrere in entrambe le direzioni ed entrambi i router
hanno lo stesso valore del bit E.
Il Protocollo Exchange

Quando due routers OSPF stabiliscono la
connessione su di un link punto a punto, devono
sincronizzare i propri database
 La sincronizzazione iniziale avviene tramite il
protocollo "exchange"; di seguito sara' il protocollo
flooding ad occuparsi di mantenere sincronizzati i
database.
 Il protocollo Exchange e' asimmetrico; il primo step
del protocollo consiste nel selezionare un "master"
e uno "slave" e solo di seguito i due routers si
scambieranno la descrizione dei propri database

Il router che vuole iniziare la procedura emette un
pacchetto vuoto "Database Description e l’ altro
router risponde emettendo un pacchetto DD di
"Acknowledgment“.
 Il primo router può quindi iniziare ad inviare le
descrizioni da lui possedute
IL PROTOCOLLO "FLOODING"





Il protocollo flooding viene utilizzato per diffondere (processo di forwarding) a tutta la rete il
nuovo stato di un link.
Questi aggiornamenti vengono inviati, attraverso il pacchetto di "Link State Update", nel
caso di:
un cambiamento di stato del link
allo scadere di un timer (normalmente 60 min)
Il pacchetto "Link State Update", che caratterizza il campo "Type" dell'header comune con
il valore 4
Gli LSA del pacchetto Link State Update vengono normalmente riconosciuti, attraverso
una conferma dell'avvenuta ricezione, con il pacchetto di Link State Acknowledgment,
che caratterizza il campo "Type" dell'header comune con il valore 5
BGP: border gateway protocol
protocollo di instradamento inter AS
 Comunicazione
solo tra router confinanti
(Pari BGP)
 Scambio di informazioni sui percorsi
 Indirizzamento verso reti
 AS identificati da un numero (ASN)
 Scambi di annunci
Ogni router di frontiera rappresenta le
destinazioni interne come se fossero
locali
Annuncio BGP
inviati da pari a pari con una connessione punto
punto
Contiene
Protocollo tcp porta 179
indirizzo di rete di destinazione
attributi
Le informazioni possono essere scambiate tra due AS solo se una sessione peering è
attiva
La sessione peering è una connessione TCP tra i due AS
attività del BGP


Ricezione di annunci sui percorsi da parte dei vicini
attaccati
Filtraggio: gli annunci possono essere filtrati sulla base di:




Una lista di prefissi validi
Una lista di numeri di AS
Selezione del percorso secondo la politica di
instradamento (accordi commerciali, questioni legali,
preferenze locali)
Invio di annunci sui percorsi ai vicini
I percorsi vengono immagazzinati nel RIB
(informazioni base di routing suddiviso come
segue:
 ADJ-RIB-IN : contiene tutti i percorsi appresi
da messaggi UPDATE, che vengono dati in
input al processo decisionale.
 LOC-RIB : contiene le informazioni di routing
locale, cioè all'interno dell'AS, che il BGP
speaker ha selezionato in base alla politica
locale che viene stabilita dall'amministratore.
 ADJ-RIB-OUT : contiene le informazioni di
routing che il BGP speaker locale ha
selezionato e che sono annunciate ai suoi
interlocutori (peers).
Intestazione messaggi BGP




Precede ogni messaggio BGP ed identifica il tipo di
messaggio
Marker (16 byte): scelto in accordo tra le due parti per
sincronizzare i messaggi. Questa funzione non è
fornita da TCP
Length (2 byte): lunghezza del messaggio tra 19 e
4096 byte
Type: tipo di messaggio BGP
Tipologie di messaggi BGP
 OPEN:
permette di stabilire un contatto
con un pari
 UPDATE: per annunciare un percorso
verso una data destinazione
 KEEPALIVE:per far conoscere ad un pari
che il sender è attivo
 NOTIFICATION: quando viene rilevato un
errore
OPEN




Utilizzato per aprire una connessione peer
Il campo Hold specifica il massimo numero di secondi tra due
messaggi successivi
Un router bgp è caratterizzato dall’asn e da un indentificatore
unico a 32 bit che deve usare per tutte le connessioni peering
Parametri opzionali: ad esempio per l’autenticazione
OPEN
 Il
router destinatario di un messaggio
OPEN risponde con un KEEPALIVE
 Connessione aperta quando entrambi i
router inviano un messaggio OPEN ed
un messaggio KEEPALIVE
UPDATE

Announcement = prefix + attributes values
 Annuncia nuove reti raggiungibili ed
eventualmente l’instradamento
 Annuncia reti precedentemente annunciate
non più raggiungibili
KEEPALIVE
 Verifica
periodicamente la connessione
TCP tra entità peer
 Più efficiente rispetto ad inviare
periodicamente messaggi di
instradamento
 Intervallo KEEPALIVE ogni 1/3 di HOLD
time, mai inferiore a 1 sec.
NOTIFICATION



Controllo o segnalazione errori
BGP invia un messaggio di notifica e
chiude la connessione TCP
Errori:





Errore nell’intestazione del messaggio
Errore nel messaggio OPEN
Errore nel messaggio UPDATE
Timer di attesa scaduto
Fine (connessione terminata)
Riassumendo il BGP…
Due routers BGP neighbors inizialmente si
scambieranno le intere routing tables, dopodichè
solo le modifiche attraverso messaggi UPDATE.
Dopo la connessione il primo messaggio ad
essere spedito è quello OPEN che l'interlocutore
confermerà con un messaggio KEEPALIVE. I
messaggi KEEPALIVE sono trasmessi
periodicamente per mantenere attiva la
connessione. Il messaggio NOTIFICATION
viene trasmesso quando si rileva un errore nella
trasmissione o per speciali condizioni.
PERCHE’ DUE TIPI DI
PROTOCOLLO ?

Politica
 Scala
 Prestazioni
R4
R5
R3
AS1
BGP
AS2
(RIP intra-AS
routing)
BGP
R1
R2
(OSPF
intra-AS
routing)
AS3
(OSPF intra-AS
routing)