Agenda
- Organizzazione globale di Internet
- Le basi di BGP
- BGP nelle reti di grandi dimensioni
- Inter-domain Traffic Engineering con BGP
Come instradare pacchetti IP in Internet?
Una mappa di Internet nel 2000
L’organizzazione di Internet
Internet è composta da oltre 10000 autonomous routing domains (AS)
- Un domain (dominio) è un insieme di router, link, host e LAN sotto lo stesso controllo amministrativo.
- Un domain può essere molto grande…
-
- AS568 SUMNET-AS DISO-UNRRA contiene 73154560 indirizzi IP
- Un domain può essere anche molto piccolo
-
- AS2111 IST-ARTUM TE contiene un singolo PC
- I domain sono interconnessi in vario modo.
- L’interconnessione tra tutti gli AS dovrebbe permettere a un pacchetto di andare ovunque.
- Un pacchetto solitamente attraversa più AS.
Tipologie di domain
Transit domain
Un transit domain permette a domain estreni di usare la propria infrastruttura per inviare pacchetti ad altri domini.
Esempi: UUNet, OpenTransit, GEANT, Internet2, BT, Telia…
Tipologie di domain
Stub domain
Uno stub domain non consente a domain esterni di utilizzare la sua infrastruttura per inviare pacchetti.
- Uno stub domain è connesso almeno a un transit domain
- Single-homed stub e Dual-homed stub
- Content-rich stub
- Grandi web-server:Yahoo, Google, …
- Access-rich stub domain
- ISP Internt provider accessibili da CATV, ADSL, …
Un Domain Transit: Easynet
Un Domain Transit: BT/IGnite
Un ampio Domain Transit: UUNet
Agenda
- Organizzazione globale di Internet
- Le basi di BGP
- BGP nelle reti di grandi dimensioni
- Inter-domain Traffic Engineering con BGP
L’architettura di un comune router IP
Routing in Internet
- Interior Gateway Protocol (IGP)
- Routing dei pacchetti IP all’interno di ogni dominio: soltanto la topologia all’interno del domain è nota.
- Exterior Gateway Protocol (EGP)
- Routing dei pacchetti IP tra i domain: ogni domain è considerato come un blackbox.
Interior Gateway Protocol
Routing Intra-domain
Obiettivo
- Permette ai router di trasmettere pacchetti IP fino alla destinazione attraverso il percorso migliore:
- Per migliore solitamente si intende il percorso più breve (in secondi o numero di hop).
- A volte per migliore si intende il percorso meno carico.
- Permettere l’indentificazione di percorsi alternativi in caso di problemi.
Comportamento
- Tutti i router si scambiano informazioni di routing:
- Ogni router ottine informazioni dal’intero domain.
- Il protocollo determina il costo di ogni link.
Tre tipi di IGP
- Routing Statico
- Utile solo i domain di dimensioni ridotte
- Routing Distance Vector
- Routing Information Protocol (RIP)
- Ancora ampiamente utilizzato in piccoli domain nonostante i sui limiti
- Routing Link State
- Open Shortest Path First (OSPF)
-
- Ampiamente utilizzato nelle reti di aziende
- Intermediate System – Intermediete System (IS-IS)
-
- Ampiamente utilizzato dagli ISP
Routing Distance Vector
Principi
- Configurazione dei router
- Costi associati con ogni link
- Ogni router invia periodicamente un vettore delle distanze contenente per ogni prefisso conosciuto:
- La distanza tra se stesso e la destinazione
-
- Il vettore delle distanze deriva dalle tabelle di routing.
- Ogni router riceve i vettori delle distanze dai vicini e costruisce le tabelle di routing.
Questioni relative al Distance Vector
- Come trattare le rotture dei link?
- I router dovrebbero inviare i loro vettori delle distanze quando rilevano una rottura su uno dei loro link.
- Come evitare il problema del count-to-infinity?
- Utilizzare una rete “a stella” non ridondante.
- Limitare la massima distanza tra due router.
-
- Il router A non informa il router B dei percorsi per i quali invia pacchetti attraverso B.
- Split horizon con Poison Reverse.
Routing Link State
Principi
- Ogni router costruisce pacchetti link state contenente la sua topologia locale.
- I pacchetti link state sono creati a intervalli regolari e quando la topologia cambia.
- I pacchetti link state sono inviati in maniera affidabile a tutti i nodi del domain.
- Ogni nodo conosce l’intera topologia del domain.
- I nodi costruiscono le tabelle di routing attraverso l’algoritmo di Dijkstra.
IP Forwarding
Solitamente
- Le tabelle di forwarding contengono, per ogni prefisso:
- Il percorso migliore (interfaccia di uscita) per raggiungere il prefisso.
Qualche volta
- Le tabelle di forwarding contengono, per ogni prefisso:
- N percorsi di costo equivalente per raggiungere il prefisso.
- Un meccanismo di bilanciamento del carico è utilizzato per l’uso degli N percorsi.
Algoritmo di bilanciamento del carico
Soluzione semplice
- Round-Robin o varianti per distribuire i pacchetti sulla base delle caratteristiche degli stessi.
- Vantaggi:
- Facile da implementare con un numero ridotto di percorsi.
- Il traffico è assegnato ai percorsi in base al tipo di pacchetto.
-
- Ogni pacchetto trasporterà la stessa quantità di traffico.
- Svantaggi:
- Due pacchetti appartenenti alla stessa connessione TCP possono essere inviati su percorsi differenti e dunque è necessario riordinarli.
-
- Le performance del TCP possono esserne affette.
Agenda
- Organizzazione globale di Internet
- Le basi di BGP
- Il Border Gateway Protocol
- Come scegliere dei percorsi rispetto ad altri
- BGP nelle reti di grandi dimensioni
- Inter-domain Traffic Engineering con BGP
Routing di Inter-domain
Obiettivi
Permettere la trasmissione di pacchetti IP lungo il percorso migliore fino alla destinazione lungo diversi transit domain, tenendo conto delle politiche di routing di ogni domain senza conoscere dettagli relativamente alla topologia.
- Da un punto di vista di inter-domain, il percorso migliore è quello più economico.
- Ogni dominio è libero di specificare le proprie politiche di routing, i domini ai quali è consentito il transito, un servizio di transito e il metodo usato per selezionare il percorso migliore per raggiungere una destinazione.
Domain vs Autonomous System
- Il BGP è utilizzato prevalentemente in Autonomous System (AS)
- Un AS è definito come <un insieme di router gestiti da una singola amministrazione … che ha un quadro completo delle destinazioni raggiungibili>.
- Ogni AS è identificato da un singolo numero.
- In pratica
- Un domain spesso equivale ad un AS.
- Un domain può essere composto da differenti AS.
- Molti domini non hanno un numero di AS.
Autonomous System
Ad ogni AS in Internet è stato assegnato un numero di 16 bit dall’Regional Internet Registers.
Tipi di link inter-domain
Esistono due tipi di link inter-domain
- Link privati
- Solitamente una linea “in fitto” tra due router appartenenti a due domain connessi.
- Connessione mediante un punto di interconnessione pubblica
- Solitamente uno Switch Ethernet a Gigabit che interconnette router appartenenti a domain differenti.
Punto di interconnessione pubblica
Politiche di Routing
In teoria il BGP permette ad ogni dominio di definire le proprie politiche di routing.
Nella pratica, però, ci sono due soluzioni comuni.
- Connessione customer–provider
- L’utente C acquista la connettività dal provider P.
- Connessione shared-cost
- I domain X e Y si accordano per scambiare pacchetti utilizzando un link diretto o attraverso un punto di interconnessione.
Connessione Customer-Provider
Principio
- Il Customer invia al provider le proprie rotte e quelle dei propri Customer.
- I Provider invieranno queste alle altre reti in Internet.
- I Provider inviano ai Customer tutte le rotte note.
- I Customer potranno raggiungere ciunque nella rete.
Connessione Customer-Provider
Connessione Shared-cost
Principio
- L’entità X invia a Y le sue rotte e quelle dei suoi customer.
- Y utilizza il link condiviso per raggiungere X.
- Il provider di X non può utilizzare il link condiviso.
- L’entità X invia a Y le sue rotte e quelle dei suoi customer.
- Y utilizza il link condiviso per raggiungere X.
- Il provider di X non può utilizzare il link condiviso.
Politiche di Routing
Un Domain specifica le sue politiche di routing definendo per ogni BGP router due set di filtri per ogni sistema.
- Filtri Import
- Specifica quali rotte possono essere accettate dal router tra tutte quelle ricevute.
- Filtri Export
- Specifica quali rotte possone essere fornite dal router.
- I filtri possono essere definiti in RPSL.
Routing Policy Specification Language (RFc 2622).
Politiche di Routing: un semplice esempio RPSL
Agenda
- Organizzazione globale di Internet
- Le basi di BGP
- Il Border Gateway Protocol
- Come scegliere dei percorsi rispetto ad altri
- BGP nelle reti di grandi dimensioni
- Inter-domain Traffic Engineering con BGP
Il Border Gateway Protocol
Principio
- Path Vector Protocol:
- Il router BGP fornisce la rotta migliore per ogni destinazione.
- Con aggiornamento incrementale:
- Invia aggiornamenti soltanto quando c’è un cabiamento.
Le “origini” delle informazioni delle rotte di BGP
Da dove vengono le informazione sulle rotte dei router BGP?
- Apprendono da altri router BGP.
- Il router BGP propaga solo le rotte ricevute.
- Configurazione statica.
- Il router BGP è configurato per informare soltanto alcuni router.
- Svantaggio: richiede una configurazione manuale.
- Vantaggio: un insieme stabile di router da informare.
- Apprendono attraverso un Interior Gateway Protocol.
- Le informazioni sono ricevute come aggregato.
- Vantaggio: seguono la stato della rete.
- Svantaggio: instabile se l’IGP è instabile.
Politiche e BGP
Due meccanismi per supportare le politiche in BGP
- Ogni domain sceglie le sue rotte sulla base delle informazioni apprese dagli altri router.
- Il percorso migliore non è necessariamente il più breve come in IGP.
- Solo le informazioni sulle rotte migliori per ogni destinazione sono scambiate.
- Ogni domain determina le informazioni di quali rotte posso essere scambiate.
- Un AS non necessariamente informa tutti i suoi vicini sulle rotte di cui è a conoscenza.
Modello computazionale per un Router BGP
Informazioni base per il Routing BGP
- Contiene tutte le rotte consentite apprese dagli altri Peer + le rotte interne.
- Il processo di decisione BGP seleziona la rotta migliore per ogni destinazione.
BGP: principi di funzionamento
Principi
BGP si basa su scambio incrementale di vettori di percorsi.
Scambio incrementale di vettori di percorsi
BGP: principi di funzionamento
Modello semplificato di BGP
2 tipi di vettori di percorso BGP:
- UPDATE
- Usato per annunciare una rotta.
-
- Indirizzo di destinazione.
-
- Percorso Inter-domain usato per raggiungere la destinazione.
-
- Il next-hop (prossimo salto).
- WITHDRAW
- Usato per indicare che una precedente rotta non è più in uso.
- WITHDRAW contiene l’indirizzo della destinazione irraggiungibile.
Eventi durante una sessione BGP
- Aggiungere una nuova rotta a RIB
- Una nuova rotta è aggiunta ad un router locale
-
- Rotta statica attraverso configurazione
-
- Rotta dinamica appresa attraverso IGP
- Rimuovere una rotta da RIB
- Rimozione di una rotta interna
-
- Rotta statica rimossa dalla configurazione del router
-
- Rotta Inter-domain dichiarata irrangiungibile da IGP
- Ricezione di un messaggio WITHDRAW
- Perdita di sessione BGP
- Tutte i router apprendono dai peer la sua rimozione da RIB
I messaggi BGP
Messaggio a lunghezza variabile con header fisso
Il messaggio OPEN
Sessione BGP tra due peer BGP
Stabilire una sessione BGP
Solitamente una sessione BGP può essere stabilita soltanto tra due peer configurati manualmente. Ogni nodo deve essere configurato con indiirzzo IP e numero dell’AS del peer remoto.
Il messaggio UPDATE
Un unico tipo di messaggio per inviare sia notifiche di rotte IP che revoca di rotte.
I messaggi KEEPALIVE e NOTIFICATION
Il messaggio KEEPALIVE
- Contiene soltanto l’header di default.
- Ogni HoldTime/3 secondi il router invia un messaggio KEEPALIVE se non sono stati inviati recentemente altri messaggi.
Il messaggio NOTIFICATION
- Indica problemi nel processare messaggi BGP.
- Example errors :
-
- Unsupported Version, Unsupported Optional Parameter, …
-
- Malformed Attribute List, …
- 5: Finite State Machine Error
BGP e IP: un primo esempio
Cosa succede se il link AS10-AS20 si guasta?
BGP e IP: un primo esempio
- Se link AS10-AS20 si guasta, AS20 non considererà più il persorso appreso da AS10.
- L’AS20 rimuoverà il percorso dalla sua tabella di routing e selezionerà il percorso appreso da AS40.
- Questo forzerà l’AS20 a inviare il seguente UPDATE a AS30.
BGP e IP: un secondo esempio
I maggiori campi dell’UPDATE
- NextHop: indirizzo IP del prossimo router per raggiungere la destinazione
- ASPath
In questo esempio vogliamo considerare i messaggi BGP relativi ai seguenti indirizzi: 194.100.0.0/24, 194.100.1.0/24 and 194.100.2.0/23.
BGP e IP: un secondo esempio
BGP e IP: un secondo esempio
Prossima lezione
Routing Inter-dominio con BGP4 – Parte II
- Organizzazione di Internet
- Principi fondamentali di BGP
- Politiche di routing
- Il Border Gateway Protocol
- Come scegliere dei router piuttosto che altri
- BGP in large networks
- Ingegneria del traffico intra-dominio con BGP