INSTRADAMENTO IN INSTRADAMENTO IN
INTERNET INTERNET
Determinare il percorso che un Determinare il percorso che un
datagramma seguirà dall’origine datagramma seguirà dall’origine
alla destinazione
alla destinazione
I protocolli d’instradamento
I protocolli d’instradamento intra-AS intra-AS sono noti come
sono noti come protocolli gateway protocolli gateway interni (
interni (IGP IGP ) )
I protocolli intra-AS più comuni sono:
I protocolli intra-AS più comuni sono:
RIP RIP : routing information protocol : routing information protocol
OSPF OSPF : open shortest path first : open shortest path first
Il protocollo
Il protocollo inter-AS inter-AS più comune è: più comune è:
BGP BGP : border gateway protocol : border gateway protocol
ASAS (sistema autonomo): insieme di router sotto lo (sistema autonomo): insieme di router sotto lo stesso controllo amministrativo e tecnico, che stesso controllo amministrativo e tecnico, che eseguono lo stesso protocollo d’instradamento eseguono lo stesso protocollo d’instradamento
RIP RIP (Routing Information Protocol) (Routing Information Protocol)
E’ un protocollo a vettore distanza che E’ un protocollo a vettore distanza che
utilizza gli hop come metrica di costo (tutti utilizza gli hop come metrica di costo (tutti
i collegamenti hanno costo unitario) i collegamenti hanno costo unitario)
HOPHOP: numero di sottoreti attraversate lungo il percorso : numero di sottoreti attraversate lungo il percorso minimo dal router origine alla sottorete di
minimo dal router origine alla sottorete di
destinazione, includendo quest’ultima (max 15 hop) destinazione, includendo quest’ultima (max 15 hop)
ESEMPIO ESEMPIO
DD
CC
BB AA
uu vv
ww
xx yy zz
destinazione hop destinazione hop
u 1u 1
v 2v 2
w 2w 2
x 3x 3
y 3y 3
z 2z 2
Dal router A alle varie sottoreti:
Annunci RIP Annunci RIP
• In RIP, i router adiacenti si scambiano gli In RIP, i router adiacenti si scambiano gli
aggiornamenti d’instradamento ogni 30 secondi aggiornamenti d’instradamento ogni 30 secondi circa utilizzando un messaggio di risposta RIP, circa utilizzando un messaggio di risposta RIP, noto anche come
noto anche come annuncio RIP annuncio RIP . .
• Ogni messaggio contiene un elenco Ogni messaggio contiene un elenco
comprendente fino a 25 sottoreti di destinazione comprendente fino a 25 sottoreti di destinazione all’interno del sistema autonomo nonché la
all’interno del sistema autonomo nonché la
distanza del mittente rispetto a ciascuna di tali distanza del mittente rispetto a ciascuna di tali sottoreti.
sottoreti.
Ciascun router ha una Ciascun router ha una
TABELLA D’INSTRADAMENTO TABELLA D’INSTRADAMENTO
include il vettore distanza e la tabella d’inoltro include il vettore distanza e la tabella d’inoltro
Sottorete destin.
Sottorete destin. Router successivo Router successivo Numero di hop verso la dest.Numero di hop verso la dest.
ww AA 22
yy BB 22
zz BB 77
xx ---- 11
…….. ….…. ........
ww xx yy
zz
AA
CC
DD BB
Tabella d’instradamento nel router D.
Tabella d’instradamento nel router D.
D riceve da A l’annuncio che z passando per C e D riceve da A l’annuncio che z passando per C e
non per B compie un percorso più breve non per B compie un percorso più breve
Sottorete destin. Router successivo Numero di hop verso la dest.
Sottorete destin. Router successivo Numero di hop verso la dest.
ww AA 22
yy BB 22
zz B AB A 7 57 5
xx ---- 11
…….. ….…. ........
Tabella d’instradamento nel router D.
ww xx yy
zz
AA
CC
DD BB
Dest Next hop Dest Next hop w w - 1 - 1 x x - 1 - 1 zz C 4 C 4 …. …. … ... … ...
Notifica dal Notifica dal router A.
router A.
RIP: guasto sul collegamento e RIP: guasto sul collegamento e
recupero recupero
Se un router non riceve notizie dal suo vicino per Se un router non riceve notizie dal suo vicino per 180 sec, il nodo adiacente/il collegamento viene 180 sec, il nodo adiacente/il collegamento viene
considerato spento o guasto.
considerato spento o guasto.
– RIP modifica la tabella d’instradamento localeRIP modifica la tabella d’instradamento locale – Propaga l’informazione mandando annunci ai Propaga l’informazione mandando annunci ai
router vicini.
router vicini.
– I vicini inviano nuovi messaggi (se la loro tabella I vicini inviano nuovi messaggi (se la loro tabella d’instradamento è cambiata).
d’instradamento è cambiata).
– L’informazione che il collegamento è fallito si L’informazione che il collegamento è fallito si propaga rapidamente su tutta la rete.
propaga rapidamente su tutta la rete.
– L’utilizzo dell’inversione avvelenata evita i loopL’utilizzo dell’inversione avvelenata evita i loop
Inversione avvelenata Inversione avvelenata
Modifica dei costi:
Modifica dei costi:
• problema dell’instradamento ciclico! problema dell’instradamento ciclico!
• 44 iterazioni prima che l’algoritmo 44 iterazioni prima che l’algoritmo di stabilizzi
di stabilizzi xx zz
11 44
55
yy
6060
5050
Inversione avvelenata:
Inversione avvelenata:
Se Z instrada tramite Y per Se Z instrada tramite Y per giungere alla destinazione X, giungere alla destinazione X, allora Z avvertirà Y che la sua allora Z avvertirà Y che la sua distanza verso X è infinita (così distanza verso X è infinita (così Y non tenterà mai d’instradare Y non tenterà mai d’instradare verso X passando per Z)
verso X passando per Z)
Implementazione di RIP Implementazione di RIP
• Un processo chiamato routed esegue RIP, Un processo chiamato routed esegue RIP, ossia mantiene le informazioni
ossia mantiene le informazioni
d’instradamento (tabelle d’inoltro) e scambia d’instradamento (tabelle d’inoltro) e scambia
messaggi con i processi routed nei router messaggi con i processi routed nei router
vicini.
vicini.
• Poiché RIP viene implementato come un Poiché RIP viene implementato come un
processo a livello di applicazione, può inviare processo a livello di applicazione, può inviare
e ricevere messaggi su una socket standard e ricevere messaggi su una socket standard
e utilizzare un protocollo di trasporto standard e utilizzare un protocollo di trasporto standard
(UDP).
(UDP).
Implementazione di RIP Implementazione di RIP
fisico fisico
collegamento collegamento
rete tabelle (IP) rete tabelle (IP) d’inoltro
d’inoltro trasporto trasporto (UDP)(UDP)
instradato instradato
fisico fisico collegamento collegamento reterete (IP)(IP)
trasportotrasporto (UDP)(UDP) instradato
instradato
tabelle tabelle d’inoltro d’inoltro
OSPF OSPF (Open Shortest Path First) (Open Shortest Path First)
• ““open”: le specifiche del protocollo sono pubblicamente open”: le specifiche del protocollo sono pubblicamente disponibili (non avviene in IGRP di Cisco).
disponibili (non avviene in IGRP di Cisco).
• È un protocollo a stato del collegamento:È un protocollo a stato del collegamento:
– Invia messaggi OSFP all’intero sistema autonomo, utilizzando il Invia messaggi OSFP all’intero sistema autonomo, utilizzando il flooding (inondazione)
flooding (inondazione)
– Utilizza l’algoritmo di Dijkstra per la determinazione del percorso a Utilizza l’algoritmo di Dijkstra per la determinazione del percorso a costo minimo.
costo minimo.
• Con OSPF, ogni volta che si verifica un cambiamento nello Con OSPF, ogni volta che si verifica un cambiamento nello stato di un collegamento, il router manda informazioni
stato di un collegamento, il router manda informazioni d’instradamento a
d’instradamento a tuttitutti gli altri router nel sistema autonomo. gli altri router nel sistema autonomo.
Inoltre invia periodicamente lo stato dei collegamenti Inoltre invia periodicamente lo stato dei collegamenti
(almeno ogni 30 minuti), anche se questo non è cambiato.
(almeno ogni 30 minuti), anche se questo non è cambiato.
OSPF OSPF concepito per succedere a RIP concepito per succedere a RIP
Vantaggi
Vantaggi di OSPF (non in RIP): di OSPF (non in RIP):
• Sicurezza: gli scambi tra router sono autenticati: Sicurezza: gli scambi tra router sono autenticati:
solo quelli fidati possono prendere parte al solo quelli fidati possono prendere parte al
protocollo OSPF in un sistema autonomo, evitando protocollo OSPF in un sistema autonomo, evitando che malintenzionati immettano informazioni errate che malintenzionati immettano informazioni errate nelle tabelle dei router
nelle tabelle dei router
• Percorsi con lo stesso costoPercorsi con lo stesso costo: quando più percorsi : quando più percorsi verso una destinazione hanno lo stesso costo, verso una destinazione hanno lo stesso costo,
OSPF consente di usarli senza doverne scegliere OSPF consente di usarli senza doverne scegliere uno, come invece avveniva in RIP
uno, come invece avveniva in RIP
Altri vantaggi di OSPF:
Altri vantaggi di OSPF:
• Supporto integrato per l’instradamento Supporto integrato per l’instradamento unicast e multicast.
unicast e multicast.
– Per consentire l’instradamento multicast Per consentire l’instradamento multicast viene impiegato MOSPF (OSPF
viene impiegato MOSPF (OSPF multicast)
multicast) che utilizza il database di che utilizza il database di collegamenti OSPF.
collegamenti OSPF.
• Supporto alle gerarchie in un dominio Supporto alle gerarchie in un dominio d’instradamento.
d’instradamento.
OSPF OSPF strutturato gerarchicamente strutturato gerarchicamente
• Gerarchia su due livelli: area locale, dorsale.Gerarchia su due livelli: area locale, dorsale.
– Messaggi solo all’interno dell’areaMessaggi solo all’interno dell’area
– Ciascun nodo ha una sua area; conosce solo la direzione (shortest Ciascun nodo ha una sua area; conosce solo la direzione (shortest path) verso le reti nelle altre aree
path) verso le reti nelle altre aree
• Router interni: Router interni: si trovano in aree non dorsali ed effettuano si trovano in aree non dorsali ed effettuano soltanto instradamento interno al sistema autonomo.
soltanto instradamento interno al sistema autonomo.
• Router di confine d’area: Router di confine d’area: appartengono sia a un’area appartengono sia a un’area generica sia alla dorsale.
generica sia alla dorsale.
• Router di dorsale:Router di dorsale: effettuano l’instradamento all’interno effettuano l’instradamento all’interno della dorsale, ma non sono router di confine.
della dorsale, ma non sono router di confine.
• Router di confine:Router di confine: scambiano informazioni con i router di scambiano informazioni con i router di altri sistemi autonomi.
altri sistemi autonomi.
OSPF OSPF strutturato gerarchicamente strutturato gerarchicamente
BGP BGP (Border gateway protocol) (Border gateway protocol)
• BGP mette a disposizione di ciascun AS un BGP mette a disposizione di ciascun AS un modo per:
modo per:
1.1.ottenere informazioni sulla raggiungibilità delle ottenere informazioni sulla raggiungibilità delle sottoreti da parte di AS confinanti
sottoreti da parte di AS confinanti
2.2.propagare le informazioni di raggiungibilità a tutti i propagare le informazioni di raggiungibilità a tutti i router interni di un AS
router interni di un AS
3.3.determinare percorsi “buoni” verso le sottoreti sulla determinare percorsi “buoni” verso le sottoreti sulla base delle informazioni di raggiungibilità e delle
base delle informazioni di raggiungibilità e delle politiche dell’AS
politiche dell’AS
• BGP consente a ciascuna sottorete di BGP consente a ciascuna sottorete di
comunicare la propria esistenza al resto di comunicare la propria esistenza al resto di
Internet.
Internet.
Fondamenti di BGP Fondamenti di BGP
• In BGP coppie di router si scambiano In BGP coppie di router si scambiano informazioni d’instradamento su
informazioni d’instradamento su connessioni
connessioni TCP TCP semi-permanenti usando semi-permanenti usando la porta 179.
la porta 179.
• Generalmente c’è una connessione TCP Generalmente c’è una connessione TCP per ciascun collegamento che connette per ciascun collegamento che connette
direttamente due router in due diversi direttamente due router in due diversi
sistemi autonomi.
sistemi autonomi.
Esistono, però, anche connessioni TCP semi- Esistono, però, anche connessioni TCP semi- permanenti tra router interni ai sistemi autonomi
permanenti tra router interni ai sistemi autonomi
Fondamenti di BGP Fondamenti di BGP
• I router ai capi di una connessione TCP sono I router ai capi di una connessione TCP sono chiamati
chiamati peer BGP
peer BGP, e la connessione TCP con , e la connessione TCP con tutti i messaggi BGP che vi vengono inviati è tutti i messaggi BGP che vi vengono inviati è
detta
detta sessione BGP
sessione BGP. .
• Nel caso in cui questa convoglia due sistemi Nel caso in cui questa convoglia due sistemi autonomi viene detta sessione BGP esterna, autonomi viene detta sessione BGP esterna,
eBGP, mentre quella tra router dello stesso eBGP, mentre quella tra router dello stesso
sistema autonomo è chiamata sessione BGP sistema autonomo è chiamata sessione BGP
interna, iBGP.
interna, iBGP.
• Le linee di sessione BGP non sempre Le linee di sessione BGP non sempre corrispondono ai collegamenti fisici.
corrispondono ai collegamenti fisici.
• Collegamenti fisici Collegamenti fisici
• Linee di sessione BGP Linee di sessione BGP
3b
1d 3a
1c 2a
AS3
AS1 1a AS2
2c 2b
1b 3c
3b
1d 3a
1c 2a
AS3
AS1 1a AS2
2c 2b 1b
3c
Sessione eBGP Sessione iBGP
Annunciazione di
Annunciazione di prefissi prefissi
• In BGP, le destinazioni non sono host, ma In BGP, le destinazioni non sono host, ma piuttosto prefissi, che rappresentano una piuttosto prefissi, che rappresentano una
sottorete o una collezione di sottoreti.
sottorete o una collezione di sottoreti.
• Quando un sistema autonomo annuncia Quando un sistema autonomo annuncia un prefisso ad un altro, sta in realtà
un prefisso ad un altro, sta in realtà
promettendo che inoltrerà i datagrammi su promettendo che inoltrerà i datagrammi su
un percorso verso il prefisso cui sono un percorso verso il prefisso cui sono
destinati.
destinati.
Esempio prefissi Esempio prefissi
Ad AS2 sono connesse 138.16.64/24, 138.16.65/24, 138.16.66/24, Ad AS2 sono connesse 138.16.64/24, 138.16.65/24, 138.16.66/24, 138.16.67/24.138.16.67/24.
AS2 può aggregare i prefissi e usare BGP per annunciare il singolo AS2 può aggregare i prefissi e usare BGP per annunciare il singolo prefisso 138.16.64/22 ad AS1 prefisso 138.16.64/22 ad AS1
10001010.00010000.01000000 10001010.00010000.01000000
10001010.00010000.01000001 10001010.00010000.010000 10001010.00010000.01000001 10001010.00010000.0100000000 10001010.00010000.01000010
10001010.00010000.01000010 10001010.00010000.01000011 10001010.00010000.01000011
3b
1d 3a
1c 2a
AS3
AS1 1a AS2
2c 2b 1b
3c
Come BGP
Come BGP distribuisce distribuisce le le informazioni
informazioni
• In una sessione eBGP tra i gateway 3a e 1c, AS3 invia ad In una sessione eBGP tra i gateway 3a e 1c, AS3 invia ad AS1 la lista di prefissi raggiungibili.
AS1 la lista di prefissi raggiungibili.
• 1c utilizza le proprie sessioni iBGP per distribuire i prefissi agli 1c utilizza le proprie sessioni iBGP per distribuire i prefissi agli altri router del sistema autonomo.
altri router del sistema autonomo.
• Anche AS1 e AS2 si scambiano informazioni sulla Anche AS1 e AS2 si scambiano informazioni sulla
raggiungibilità dei prefissi attraverso i propri gateway 1b e 2a.
raggiungibilità dei prefissi attraverso i propri gateway 1b e 2a.
• Quando un router viene a conoscenza di un nuovo prefisso, lo Quando un router viene a conoscenza di un nuovo prefisso, lo memorizza in una nuova riga della propria tabella d’inoltro.
memorizza in una nuova riga della propria tabella d’inoltro.
3b
1d 3a
1c 2a
AS3
AS1 1a AS2
2c 2b 1b
3c
Attributi del percorso e rotte BGP Attributi del percorso e rotte BGP
• Quando un router annuncia un prefisso per una Quando un router annuncia un prefisso per una sessione BGP, include anche un certo numero di sessione BGP, include anche un certo numero di
attributi BGP attributi BGP..
– prefisso + attributi = “rotta”prefisso + attributi = “rotta”
• Due dei più importanti attributi sono:Due dei più importanti attributi sono:
– AS-PATH:AS-PATH: elenca i sistemi autonomi attraverso i quali è passato elenca i sistemi autonomi attraverso i quali è passato l’annuncio del prefisso: AS 67 AS 17
l’annuncio del prefisso: AS 67 AS 17
– NEXT-HOP:NEXT-HOP: quando si deve inoltrare un pacchetto tra due quando si deve inoltrare un pacchetto tra due
sistemi autonomi, questo potrebbe essere inviato su uno dei vari sistemi autonomi, questo potrebbe essere inviato su uno dei vari
collegamenti fisici che li connettono direttamente. Quindi se ci collegamenti fisici che li connettono direttamente. Quindi se ci
sono più collegamenti fisici tra i due sistemi, ne sceglie uno.
sono più collegamenti fisici tra i due sistemi, ne sceglie uno.
• Quando un router gateway riceve un annuncio di rotta, Quando un router gateway riceve un annuncio di rotta, utilizza le proprie
utilizza le proprie politiche d’importazionepolitiche d’importazione per decidere per decidere se accettare o filtrare la rotta nel caso ne conosca una se accettare o filtrare la rotta nel caso ne conosca una
migliore.
migliore.
Selezione dei percorsi
Selezione dei percorsi BGP BGP
• Un router può ricavare più di una rotta verso un Un router può ricavare più di una rotta verso un determinato prefisso, e deve quindi sceglierne determinato prefisso, e deve quindi sceglierne una.una.
• Regole di eliminazione:Regole di eliminazione:
1.1.Alle rotte viene assegnato come attributo un valore di Alle rotte viene assegnato come attributo un valore di preferenza locale, che potrebbe esser stato impostato preferenza locale, che potrebbe esser stato impostato direttamente o appreso dal router. Si tratta di una scelta direttamente o appreso dal router. Si tratta di una scelta che è lasciata all’amministratore di rete del sistema
che è lasciata all’amministratore di rete del sistema
autonomo. Si selezionano quindi le rotte con i più alti valori autonomo. Si selezionano quindi le rotte con i più alti valori di preferenza locale.
di preferenza locale.
2.2.Si seleziona la rotta con valore AS-PATH più breve.Si seleziona la rotta con valore AS-PATH più breve.
3.3.Si seleziona quella il cui router di NEXT-HOP è più vicino, Si seleziona quella il cui router di NEXT-HOP è più vicino, cioè quello che presenta il percorso con costo minore,
cioè quello che presenta il percorso con costo minore, determinato dall’algoritmo intra-AS (instradamento
determinato dall’algoritmo intra-AS (instradamento a a patata bollente)
patata bollente)..
4.4.Se rimane ancora più di una rotta, il router si basa sugli Se rimane ancora più di una rotta, il router si basa sugli identificatori BGP.
identificatori BGP.
Messaggi
Messaggi BGP BGP
• I messaggi BGP vengono scambiati attraverso TCP.I messaggi BGP vengono scambiati attraverso TCP.
• Messaggi BGP:Messaggi BGP:
– OPEN:OPEN: apre la connessione TCP e autentica il apre la connessione TCP e autentica il mittente
mittente
– UPDATE:UPDATE: annuncia il nuovo percorso (o cancella annuncia il nuovo percorso (o cancella quello vecchio)
quello vecchio)
– KEEPALIVEKEEPALIVE mantiene la connessione attiva in mantiene la connessione attiva in mancanza di UPDATE
mancanza di UPDATE
– NOTIFICATION:NOTIFICATION: riporta gli errori del precedente riporta gli errori del precedente messaggio; usato anche per chiudere il
messaggio; usato anche per chiudere il collegamento.
collegamento.
Politiche d’instradamento BGP Politiche d’instradamento BGP
A,B,C,x,w,y sono sistemi autonomi A,B,C,x,w,y sono sistemi autonomi
A,B,C sono reti di provider di dorsale.
A,B,C sono reti di provider di dorsale.
x,w,y sono reti stub x,w,y sono reti stub
x è una rete stub a più domicili in quanto è legato a due x è una rete stub a più domicili in quanto è legato a due
provider (B,C) provider (B,C)
x non vuole che il traffico da B a C passi attraverso di x non vuole che il traffico da B a C passi attraverso di luilui
... e così x non annuncerà a B la rotta verso C ... e così x non annuncerà a B la rotta verso C
Politiche d’instradamento BGP Politiche d’instradamento BGP
A annuncia a B del percorso AW.
A annuncia a B del percorso AW.
B annuncia a X del percorso BAW.
B annuncia a X del percorso BAW.
B deve annunciare a C del percorso BAW?
B deve annunciare a C del percorso BAW?
Certo che no! B non ha nessun “interesse” nella rotta Certo che no! B non ha nessun “interesse” nella rotta
CBAW poiché né W né C sono clienti di B CBAW poiché né W né C sono clienti di B
B vuole costringere C ad instradare verso W B vuole costringere C ad instradare verso W
attraverso A attraverso A
B vuole instradare
B vuole instradare solo solo da/verso i suoi clienti!da/verso i suoi clienti!
Differenza tra inter-AS e intra-AS Differenza tra inter-AS e intra-AS
Politiche:
Politiche:
• Inter-AS: il controllo amministrativo desidera avere Inter-AS: il controllo amministrativo desidera avere il controllo su come il traffico viene instradato e su il controllo su come il traffico viene instradato e su
chi instrada attraverso le sue reti.
chi instrada attraverso le sue reti.
• Intra-AS: unico controllo amministrativo, e di Intra-AS: unico controllo amministrativo, e di
conseguenza le questioni di politica hanno un ruolo conseguenza le questioni di politica hanno un ruolo
molto meno importante nello scegliere le rotte molto meno importante nello scegliere le rotte
interne al sistema interne al sistema
Prestazioni:
Prestazioni:
• Intra-AS: orientato alle prestazioniIntra-AS: orientato alle prestazioni
• Inter-AS: le politiche possono prevalere sulle Inter-AS: le politiche possono prevalere sulle prestazioni
prestazioni