Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Giorgio Ventre » 5.Routing Inter-dominio con BGP4 – Parte I


Agenda

  • Organizzazione globale di Internet
    • Esempi di Domini
    • Intra-domain routing
  • 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

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…

Transit domain

Transit domain


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, …
Stub domain

Stub domain


Un Domain Stub: Belnet

Belnet

Belnet


Un Domain Stub: GARR

GARR

GARR


Un Domain Transit: Easynet

Easynet

Easynet


Un Domain Transit: GEANT

GEANT

GEANT


Un Domain Transit: BT/IGnite

BT/IGnite

BT/IGnite


Un ampio Domain Transit: UUNet

UUNet

UUNet


Agenda

  • Organizzazione globale di Internet
    • Esempi di Domini
    • Intra-domain routing
  • Le basi di BGP
  • BGP nelle reti di grandi dimensioni
  • Inter-domain Traffic Engineering con BGP

L’architettura di un comune router IP

Router IP

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

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:
    • Prefisso IP
    • 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.
Routing Distance Vector

Routing Distance Vector


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.
      • Per RIP ∞=16!
    • Split horizon
      • 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.
Routing Link State

Routing Link State


IP Forwarding

Solitamente

  • Le tabelle di forwarding contengono, per ogni prefisso:
    • Il prefisso.
    • Il percorso migliore (interfaccia di uscita) per raggiungere il prefisso.

Qualche volta

  • Le tabelle di forwarding contengono, per ogni prefisso:
    • Il 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
    • Politiche di Routing
    • 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.
Link privati

Link privati

Punto di interconnessione pubblica

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 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.
Connessione Shared-cost

Connessione Shared-cost


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

Esempio RPSL

Esempio RPSL


Agenda

  • Organizzazione globale di Internet
  • Le basi di BGP
    • Politiche di Routing
    • 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.
Border Gateway Protocol

Border Gateway Protocol


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.
Modello computazionale

Modello computazionale


BGP: principi di funzionamento

Principi

BGP si basa su scambio incrementale di vettori di percorsi.

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.
    • UPDATE contiene:
      • 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

Messaggio a lunghezza variabile con header fisso


Il messaggio OPEN

Sessione BGP tra due peer BGP

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.

Sessione BGP

Sessione BGP


Il messaggio UPDATE

Un unico tipo di messaggio per inviare sia notifiche di rotte IP che revoca di rotte.

Messaggio UPDATE

Messaggio UPDATE


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 :
    • 2: OPEN Message Error
      • Unsupported Version, Unsupported Optional Parameter, …
    • 3: UPDATE Message Error
      • Malformed Attribute List, …
    • 4: Hold Timer Expired
    • 5: Finite State Machine Error
    • 6 : Cease
Example errors

Example errors


BGP e IP: un primo esempio

Cosa succede se il link AS10-AS20 si guasta?

Update iniziali

Update iniziali


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.
UPDATE

UPDATE


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.

Schema dell’esempio

Schema dell'esempio


BGP e IP: un secondo esempio

Schema dell’esempio

Schema dell'esempio


BGP e IP: un secondo esempio

Schema dell’esempio

Schema dell'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

I materiali di supporto della lezione

Cisco Network Management System: Best Practices White Paper

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion