Protocolli e architetture di instradamento/Border Gateway Protocol

Il Border Gateway Protocol (BGP) è il protocollo di instradamento inter-dominio comunemente utilizzato in Internet.

Panoramica

• usa l'algoritmo Path Vector (PV) per registrare la sequenza degli AS lungo il percorso senza il rischio di routing loop: #Algoritmo Path Vector;
• i router possono aggregare le informazioni di instradamento ricevute prima di propagarle: #Aggregazione delle rotte;
• non scopre automaticamente l'esistenza di nuovi router vicini, ma le peering session vanno configurate a mano: #Peering session;
• scambia gli aggiornamenti di instradamento usando connessioni TCP affidabili: #TCP;
• è un protocollo estensibile grazie al formato Type-Length-Value (TLV) degli attributi: #Attributi di percorso;
• supporta le politiche di instradamento: #Processo di decisione.

Informazioni di instradamento

Il BGP scambia informazioni di instradamento inter-dominio sulle rotte esterne, che sono nella forma indirizzo di rete/lunghezza del prefisso (invece della netmask).

Algoritmo Path Vector

Siccome le politiche di instradamento sono definite in base ai percorsi, il BGP non può basarsi sull'algoritmo DV perché non è sufficiente sapere i loro costi. Il BGP ha scelto di adottare l'algoritmo Path Vector (PV): ogni AS costituisce un singolo nodo, identificato da un numero di 2 (o 4) byte, e l'informazione aggiuntiva è la lista degli AS attraversati.

L'algoritmo PV è più stabile poiché è facile rilevare dei cicli:

• se un router riceve un PV che contiene già il suo numero di AS, scarta il PV senza propagarlo, poiché si sta incorrendo in un routing loop;
• se no, il router inserisce il proprio numero di AS nel PV e quindi lo propaga ai suoi vicini.

Il BGP non supporta una esplicita metrica di costo: il costo associato a ogni rotta è semplicemente pari al numero di AS attraversati inclusi nella lista → la rotta a minor costo può non essere quella effettivamente ottimale:

• gli AS possono avere requisiti diversi, quindi possono adottare metriche diverse l'uno dall'altro (ad es. larghezza di banda, ritardo di trasmissione) → è difficile calcolare costi coerenti per tutti gli AS;
• il costo annunciato può non corrispondere alla reale topologia della rete perché un ISP può voler nascondere a un concorrente le informazioni reali sulla propria rete per ragioni economiche: B4. Instradamento inter-dominio: peering e transito in Internet#Requisiti amministrativi.

Aggregazione delle rotte

Quando un router di frontiera propaga le informazioni sulle rotte ricevute, può essere configurato manualmente per includere delle rotte aggregate nei messaggi di annuncio per ridurne le dimensioni: due rotte possono essere aggregate in una rotta con la parte comune del prefisso di rete.

Tuttavia non tutte le rotte che sono state condensate in una rotta aggregata possono avere la stessa sequenza di AS attraversati, ma ci può essere una rotta più specifica che segue un altro percorso:

• rotta sovrapposta: insieme alla rotta aggregata viene annunciata anche la rotta specifica, con la sua lista diversa di AS attraversati → le informazioni sono complete, e l'algoritmo "longest prefix matching" selezionerà la rotta più specifica nella tabella di instradamento;
• rotta not precise: viene annunciata solamente la rotta aggregata → le informazioni sono approssimative, perché la lista degli AS attraversati non corrisponde al percorso realmente seguito per tutti gli indirizzi di destinazione in quell'address range.

Peering session

Due router di frontiera che si scambiano dei messaggi BGP vengono chiamati peer, e la sessione basata sul TCP è chiamata peering session.

Una differenza chiave in confronto agli altri protocolli di instradamento è il fatto che i peer non si sono in grado di scoprirsi a vicenda automaticamente: è necessaria la configurazione manuale da parte dell'amministratore di rete, perché i peer potrebbero non essere connessi tramite un link diretto ma tra di essi potrebbero esistere altri router, per i quali gli aggiornamenti BGP sono dei normali pacchetti di dati da inoltrare a destinazione.

TCP

La trasmissione delle informazioni di instradamento è affidabile perché due peer stabiliscono una peering session instaurando una connessione TCP attraverso cui scambiare tutti i messaggi BGP:

• vengono riutilizzati dei componenti esistenti anziché ridefinire ancora un altro meccanismo specifico del protocollo;
• il BGP non deve avere a che fare direttamente con ritrasmissioni, messaggi persi, ecc.

L'utilizzo del TCP come protocollo di trasporto evita l'invio periodico degli aggiornamenti: un aggiornamento è inviato soltanto quando necessario, includendo solo le rotte che sono cambiate, e l'invio viene ripetuto solo se il messaggio è andato perso → viene ridotta la banda consumata per inviare le rotte.

Siccome gli annunci non sono periodici, le rotte non scadono mai → è necessario informare esplicitamente che una rotta precedentemente annunciata è diventata non raggiungibile, per ritirare le rotte quando non sono più valide (analogamente al route poisoning dell'algoritmo DV).

Tuttavia il TCP toglie all'applicazione il controllo sulle tempistiche, perché i pacchetti di controllo possono essere ritardati dai meccanismi stessi del TCP: in caso di congestione il TCP riduce il bit rate di trasmissione impedendo la loro trasmissione puntuale → è possibile configurare la qualità del servizio sui router interni all'AS in modo da dare priorità ai pacchetti BGP, considerando che sono pacchetti di servizio per permettere il funzionamento della rete.

Il TCP non fornisce l'informazione se il peer remoto è ancora raggiungibile → è richiesto un meccanismo esplicito di keepalive gestito dal BGP stesso. Anche i messaggi di keepalive si affidano ai meccanismi del TCP → la reattività alla scomparsa di un peer o al guasto di un link è limitata, ma è ancora accettabile considerando che questi eventi sono rari (ad es. i link tra router di frontiera sono fortemente ridondati).

I-BGP e E-BGP

Quando due router di frontiera instaurano tra di loro una peering session, ognuno comunica, tramite un messaggio di OPEN, il suo numero di AS all'altro party per determinare il tipo di sotto-protocollo:

• Exterior BGP (E-BGP): i peer sono router di frontiera appartenenti a due AS differenti, solitamente connessi con un link diretto;
• Interior BGP (I-BGP): i peer sono router di frontiera appartenenti allo stesso AS, solitamente connessi attraverso una serie di router interni.

L'elaborazione dei messaggi BGP e le rotte annunciate nelle peering session possono essere diverse a seconda di a quali AS appartengono i peer:

• E-BGP: quando un router di frontiera propaga un PV a un peer E-BGP, antepone il numero dell'AS corrente a ogni lista di AS attraversati:
  • rotte esterne: sono propagate agli altri peer E-BGP, tranne i peer il cui AS è sul percorso migliore verso quelle destinazioni;
  • rotte interne: sono propagate agli altri peer E-BGP;
• I-BGP: quando un router di frontiera propaga un PV a un peer I-BGP, trasmette la lista così com'è perché il numero dell'AS rimane invariato:
  • rotte esterne: sono propagate agli altri peer I-BGP secondo varie modalità;
  • rotte interne: non sono mai propagate agli altri peer I-BGP, ma ogni router di frontiera le apprende da un processo di ridistribuzione indipendente.

Le sessioni I-BGP sono utilizzate per scambiare le rotte esterne:

• indipendentemente dalle rotte scambiate dal protocollo interior: la connessione diretta tra i peer evita di disturbare il protocollo IGP quando la variazione di una rotta esterna non richiede il ricalcolo delle rotte interne → nessun transitorio, meno elaborazione;
• indipendentemente dal protocollo interior: se i router di frontiera quando apprendono le rotte esterne dall'E-BGP si limitassero a ridistribuirle al protocollo IGP, lasciando che quest'ultimo le ridistribuisca naturalmente agli altri router di frontiera, verrebbero perse alcune informazioni importanti di cui il BGP ha bisogno → servono dei messaggi BGP appositi, chiamati UPDATE, che includono queste informazioni nei loro attributi.

Sincronizzazione IGP-BGP

Esempio di sincronizzazione IGP-BGP.

I router BGP in un AS di transito apprendono le destinazioni esterne da altri router BGP attraverso l'I-BGP, ma l'instradamento dei pacchetti attraverso l'AS (verso il router BGP egress) si affida ai router interni, le cui tabelle di instradamento sono riempite dal protocollo IGP e non dal BGP → solo dopo che sono state annunciate anche dal protocollo IGP, le destinazioni esterne possono essere annunciate a router di frontiera di altri AS.

Nell'esempio nella figura a lato, il router R4 apprende la destinazione D tramite E-BGP e la annuncia al router R3 tramite I-BGP, ma R3 non può a sua volta annunciarla al router R5 tramite E-BGP finché la destinazione non è stata ridistribuita dal protocollo IGP a R3, altrimenti se R5 provasse a inviare un pacchetto verso D, R3 lo inoltrerebbe all'interno dell'AS dove i router interni lo scarterebbero.

Potrebbe andare bene disabilitare la sincronizzazione quando:

• l'AS non è di transito;
• tutti i router dell'AS utilizzano il BGP.

Routing loop

Esempio di routing loop.

La mancanza delle informazioni sui router di frontiera attraversati quando essi appartengono allo stesso AS può essere causa di routing loop: un router di frontiera non può più fare affidamento sulla lista degli AS attraversati per rilevare i percorsi che passano due volte per lo stesso router di frontiera.

Nell'esempio nella figura a lato, si determina un ciclo negli annunci:

1. il router R4 apprende la rotta esterna verso la destinazione D;
2. R4 propaga D al peer R3;
3. R3 propaga D al peer R2;
4. R2 propaga D al peer R4, che è il router che ha inizialmente appreso e annunciato D.

Si crea così una situazione simile a quella che scatenava i count to infinity nell'algoritmo Distance Vector: R4 non può stabilire se R2 sa raggiungere D passando attraverso R4 stesso oppure se esiste un percorso realmente alternativo → se si verifica un guasto sul link tra R4 e il router di frontiera dell'AS in cui si trova D, R4 crede che D sia ancora raggiungibile attraverso R2.

Le rotte esterne possono essere annunciate ai peer I-BGP secondo varie modalità: maglia completa, route reflector, AS confederation.

Maglia completa

Esempio di maglia completa.

Ogni router di frontiera ha una peering session I-BGP con ogni altro router di frontiera del suo AS.

Quando un router di frontiera apprende una rotta esterna dall'E-BGP, la propaga a tutti gli altri, che a loro volta la propagano a tutti, e così via.

In presenza di più di 2 router di frontiera, si possono creare dei routing loop dovuti a cicli negli annunci, come nella figura a lato.

Questa soluzione non è flessibile perché tutte le peering session vanno configurate a mano, anche se le peering session non cambiano molto nel tempo poiché i router di frontiera sono piuttosto fissi e resistenti ai guasti.

Route reflector

Esempio di route reflector.

Uno dei router di frontiera viene eletto route reflector (RR), e tutti gli altri router di frontiera instaurano delle peering session solamente con esso senza creare dei percorsi chiusi.

Quando un router di frontiera apprende una rotta esterna dall'E-BGP, la propaga solo al RR, il quale è responsabile di propagare a sua volta la rotta agli altri router di frontiera evitando i routing loop.

Il route reflector costituisce un singolo punto di guasto.

AS confederation

Esempio di AS confederation.

I router di frontiera hanno una maglia completa di peering session I-BGP (come nella prima modalità), ma l'AS è suddiviso in mini-AS, ognuno con un numero di AS privato, e quando un router di frontiera propaga il PV antepone nella lista il suo numero di AS privato.

Quando arriva un annuncio, il router di frontiera può guardare se nella lista è già presente il proprio numero di AS privato, in modo da scartare il pacchetto se viene rilevato un routing loop.

Attributi di percorso

Le informazioni BGP sulle rotte annunciate (ad es. la lista degli AS attraversati) sono contenute in attributi di percorso all'interno dei pacchetti di UPDATE.

Tutti gli attributi sono codificati nel formato Type-Length-Value (TLV) → il BGP è un protocollo estensibile: gli RFC di estensione possono definire dei nuovi attributi senza rompere la compatibilità con il mondo esistente e, se il router non supporta quell'attributo (codice di tipo non riconosciuto), può ignorarlo e saltare al successivo (grazie all'informazione sulla lunghezza).

Un attributo BGP può essere:

• well-known: deve essere compreso da tutte le implementazioni, e non può mai essere saltato:
  • mandatory: deve essere presente in tutti i messaggi;
  • discretionary: può non essere presente in tutti i messaggi;
• optional: può non essere compreso da tutte le implementazioni, e può essere saltato se non supportato:
  • transitive: se il router non supporta l'attributo, deve propagarlo comunque impostando il flag P;
  • non-transitive: se il router non supporta l'attributo, non deve propagarlo.

Ogni attributo ha il seguente formato TLV:

Formato Type-Length-Value (TLV) di un attributo BGP.

1	2	3	4	8	16	24/32
O	T	P	E	0	Type	Length	Value

dove i campi sono:

• flag Optional (O) (1 bit): specifica se l'attributo è optional o well-known;
• flag Transitive (T) (1 bit): specifica se l'attributo è transitive o non-transitive;
• flag Partial (P) (1 bit): specifica se almeno un router lungo il percorso ha incontrato un attributo optional transitive che non supportava;
• flag Extended Length (E) (1 bit): specifica se il campo "Length" è codificato con uno o due byte;
• campo Type (1 byte): contiene il codice di tipo che identifica l'attributo → un router può determinare se supporta quell'attributo senza dover analizzare il suo valore;
• campo Length (1 o 2 byte): contiene la lunghezza del valore dell'attributo → un router può saltare un attributo non supportato e passare al successivo avanzando del numero di byte indicato da questo campo;
• campo Value (lunghezza variabile): contiene il valore dell'attributo.

Attributi well-known

• attributo ORIGIN (tipo 1, mandatory): definisce l'origine dell'informazione di percorso:
  • IGP: la rotta è stata specificata manualmente come una rotta statica (comando bgp network);
  • EGP: la rotta è stata appresa dal protocollo EGP;
  • INCOMPLETE: la rotta è stata appresa da un protocollo IGP tramite un processo di ridistribuzione (comando bgp redistribute);
• attributo AS_PATH (tipo 2, mandatory): contiene la lista degli AS attraversati suddivisa in segmenti di percorso:
  • AS_SEQUENCE: i numeri di AS nel segmento di percorso sono in ordine di attraversamento, e se il primo segmento nel pacchetto è in ordine un nuovo numero di AS va aggiunto all'inizio di quel segmento;
  • AS_SET: i numeri di AS nel segmento di percorso non sono in ordine di attraversamento, e se il primo segmento nel pacchetto non è in ordine va aggiunto prima di quel segmento un nuovo segmento in ordine in cui va inserito il nuovo numero di AS;
• attributo NEXT_HOP (tipo 3, mandatory): ottimizza l'instradamento quando più router appartengono alla stessa LAN ma a due AS diversi, e quindi il traffico da un AS all'altro passerebbe sempre dal router di frontiera → il router di frontiera può annunciare di mandare il traffico direttamente al router next hop nell'altro AS:

Il router di frontiera B insegna al router di frontiera A di usare il router C come next hop per la destinazione D.

• attributo LOCAL_PREF (tipo 5, discretionary): nell'I-BGP quando la destinazione esterna è raggiungibile tramite due router di frontiera egress, viene preferita la rotta con LOCAL_PREF più alto;
• attributo ATOMIC_AGGREGATE (tipo 6, discretionary): indica che la rotta annunciata è una rotta aggregata not precise.

Attributi optional

• attributo MULTI_EXIT_DISC (MED) (tipo 4, non-transitive): nell'E-BGP quando due AS sono connessi tramite più link, viene preferito il link con MED più basso e i link con MED più alti sono considerati link di backup;
• attributo AGGREGATOR (tipo 7, transitive): contiene il numero di AS e l'indirizzo IP del router che ha generato la rotta not precise;
• attributo COMMUNITIES (tipo 8, transitive): indica a quale gruppo di peer questa rotta deve essere annunciata (ad es. all'intera Internet, solo nell'AS corrente, a nessuno);
• attributo MP_UNREACH_NLRI (tipo 15, non-transitive): informa che una rotta precedentemente annunciata è diventata non raggiungibile (le rotte non scadono mai).

Processo di decisione

Il processo di decisione seleziona le rotte dalle Adj-RIB-In in input e le scrive nella Loc-RIB e nelle Adj-RIB-Out in output.

Il processo di decisione in esecuzione su ogni router di frontiera è responsabile di:

• selezionare quali rotte sono annunciate agli altri peer BGP;
• selezionare quali rotte sono usate localmente dal router di frontiera;
• aggregare le rotte per ridurre le informazioni.

Le basi di dati con cui il BGP ha a che fare sono:

• Routing Information Base (RIB): consiste di tre parti distinte:
  • Adjacent RIB Incoming (Adj-RIB-In): contiene tutte le rotte apprese dagli annunci ricevuti da un certo peer;
  • Local RIB (Loc-RIB): contiene le rotte selezionate dal processo di decisione con il loro grado di preferenza;
  • Adjacent RIB Outgoing (Adj-RIB-Out): contiene le rotte che verranno propagate negli annunci a un certo peer;
• Policy Information Base (PIB): contiene le politiche di instradamento definite per configurazione manuale;
• tabella di instradamento: contiene le rotte utilizzate dal processo di inoltro dei pacchetti.

Possono essere imposte delle politiche di instradamento molto complesse per influenzare il processo di decisione:

1. viene applicata a ogni rotta nelle Adj-RIB-In una certa funzione che, applicando le politiche definite sugli attributi, restituisce il grado di preferenza per quella rotta.
   Le politiche sono definite solo in base agli attributi della rotta corrente: il calcolo del grado di preferenza non è mai influenzato dall'esistenza, dalla non esistenza o dagli attributi di altre rotte;
2. per ogni destinazione, la rotta con il grado di preferenza maggiore viene selezionata e viene inserita nella Loc-RIB;
3. altre politiche determinano quali rotte vengono selezionate dalla Loc-RIB per essere inserite nelle Adj-RIB-Out.