Instradamento tra Sistemi
Autonomi -- BGP
Reti II
Stefano Leonardi
Thanks to:
Giuseppe Di Battista, Maurizio Patrignani, Maurizio Pizzonia:
Università di Roma Tre
Timothy G. Griffin
http://www.research.att.com/~griffin/interdomain.html
Instradamento tra Sistemi Autonomi --BGP -1
I Sistemi Autonomi
 Ogni organizzazione è composta da un insieme di
router e LAN sotto una singola amministrazione
 Un algoritmo di routing è prescelto per aggiornare
automaticamente le tabelle di instradamento
 Un AS definisce in maniere coerente le politiche di
instradamento all’interno della sua oganizzazione
Instradamento tra Sistemi Autonomi --BGP -2
L’interconnessione di Sistemi
Autonomi
 Quando più organizzazioni si uniscono per
formare una Inter-rete, occorre stabilire tra
loro punti di collegamento
 Le reti che vengono aggiunte sono dette punti
di demarcazione
Instradamento tra Sistemi Autonomi --BGP -3
L’instradamento tra Sistemi Autonomi
 Ogni tabella deve avere un’entry per ogni possibile
destinazione
 Questo deve valere sia per le destinazioni locali che
per quelle globali
Instradamento tra Sistemi Autonomi --BGP -4
Come aggiornare le tabelle di
Instradamento?
In generale vi sono tre opzioni:
1.
Eseguire un unico algoritmo di instradamento tra
organizzazioni adiacenti
2.
Aggiornare le tabelle di instradamento
manualmente aggiungendo percorsi statici
predefiniti
3.
Combinare un protocollo di instradamento intradomain con un protocollo di instradamento interdomain: Exterior gateway protocol
Instradamento tra Sistemi Autonomi --BGP -5
1. Unico algoritmo di Instradamento
 Molti Svantaggi:
 Ritardo di propagazione, ex: distance vector
 Rallentamento: messaggi di instradamento inviati
agli altri routers con l’elenco delle possibili
destinazioni
 Tutte le organizzazioni sono forzate ad usare lo
stesso algoritmo
 Un nuovo algoritmo di instradamento è di difficile
adozione
 Non considera le relazioni politiche e commerciali
tra sistemi autonomi
Instradamento tra Sistemi Autonomi --BGP -6
2. Percorsi statici
 Si nasconde la parte interna dell’AS
 Per ogni obiettivo esterno si identifica un router alla
frontiera del Sistema Autonomo di destinazione
 Informazione sul cammino da seguire per
raggiungere l’obiettivo
 Svantaggi:
 difficile da aggiornare e da correggere
 I malfunzionamenti non sono gestiti, non si ha backup
 Nessuna garanzia che tutti i router del percorso sono in
effetti disponibili per portare il traffico a destinazione
Instradamento tra Sistemi Autonomi --BGP -7
2. Percorsi statici
 L’instradamento può essere inefficente
 Nell’esempio R1 ed R2 sono parte dello stesso AS.
R3 invia ad R1 tutto il traffico diretto all’AS, anche
quello diretto alla LAN 2.
 L’instradamento non tiene conto delle reti che si
possono effettivamente raggiungere!
Instradamento tra Sistemi Autonomi --BGP -8
2. Percorsi statici
 L’algoritmo di instradamento diffonderà
all’interno dell’AS il traffico locale come il
traffico che segue i percorsi statici
Instradamento tra Sistemi Autonomi --BGP -9
Le reti nascoste
 Ogni AS ha una topologia complessa, formata da diverse Reti
Locali
 Non tutte le reti locali sono connesse ad un router di frontiera
dell’AS
 Occorre informare l’esterno delle Reti Locali raggiungibili
Instradamento tra Sistemi Autonomi --BGP -10
Un approccio diverso
 Occorre avere un flusso informativo in due
direzioni, sia dall’interno verso l’esterno che
dall’esterno verso l’interno
 L’AS si deve far carico di garantire la
consistenza degli instradamenti interni
 Occorre annunciare all’esterno quali reti
interne sono raggiungibili
 Occorre assegnare le responsabilità per la
diffusione delle informazioni riguardo
l’instradamento
Instradamento tra Sistemi Autonomi --BGP -11
3. Exterior gateway protocol
 Protocollo per lo scambio delle informazioni sull’instradamento
tra Sistemi Autonomi
 BGP – Border Gateway Protocol
 Due AS che si scambiano informazioni di instradamento
designano due router che stabiliscono una sessione di peering
 Router che partecipano a BGP sono detti Router di Confine o
Gateway
Instradamento tra Sistemi Autonomi --BGP -12
3. Exterior Gateway Protocol
Approccio:
 Nascondi la parte interna degli AS
 Mantieni solo le zone di demarcazione e i router di frontiera
degli AS
Instradamento tra Sistemi Autonomi --BGP -13
3. Exterior Gateway Protocol
 Ogni router di frontiera rappresenta le
destinazioni interne come se fossero locali
Instradamento tra Sistemi Autonomi --BGP -14
3. Exterior Gateway Protocol
 Semplifica il grafo considerando le informazioni sulla
raggiungibilità sia interna che esterna all’AS
 Il grafo è gestito attraverso sessioni peering TCP
Instradamento tra Sistemi Autonomi --BGP -15
3. Exterior Gateway Protocol
 Risolvi il problema dell’instradamento nel grafo cosi’
 Definisci anche percorsi prestabiliti sulla base di
considerazioni politiche
Instradamento tra Sistemi Autonomi --BGP -16
BGP v4 – Border Gateway Protocol
BGP matiene aggiornate le tabelle di
instradamento e propaga le informazione
sull’instradamento
BGP considera la disponibilità delle
organizzazioni a cooperare nel processo di
instradamento (accordi commerciali,
questioni legali, preferenze locali)
Instradamento tra Sistemi Autonomi --BGP -17
Caratteristiche di BGP i
 Fornisce comunicazione tra AS
 Coordinamento tra speaker di uno stesso AS -



diffusione di informazioni coerenti
Diffusione dell’informazioni di raggiungibilità
all’interno dell’AS e attraverso l’AS, e apprende tali
informazioni da altri AS
Next hop routing – simile a distance vector routing
Utilizza TCP per le sessioni di peering
Invia messaggi Keep-alive per informare dello stato
della connessione anche se nessun messaggio è
inviato
Instradamento tra Sistemi Autonomi --BGP -18
Caratteristiche di BGP ii
 Informazioni sull’instradamento, router che
saranno attraversati fino a destinazione
 Aggiornamenti incrementali per risparmiare
banda
 Supporto CIDR – invio della maschera
insieme all’indirizzo
 Aggregazione delle informazioni di
instradamento per destinazione correlate
 Consente al destinatario di autenticare i
messaggi
Instradamento tra Sistemi Autonomi --BGP -19
Numerazione degli AS
 BGP richiede un numero identificatico per
ogni AS (Autonomous System Number, asn)
trac 1 and 65,535
 numeri maggiori di 64,511 sono detti “privati”
 Un asn può essere ottenuto da
 asn globale – all’autorità internet regionale: ripe,
arin, apnic
 asn privato – all’isp
Instradamento tra Sistemi Autonomi --BGP -20
Funzionalità BGP
1. Apertura connessione tra peers
2. Annuncio informazioni sulla raggiungibilità
3. Verifica corretto funzionamento
Quattro tipi di messaggio BGP
Instradamento tra Sistemi Autonomi --BGP -21
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
Instradamento tra Sistemi Autonomi --BGP -22
Peering tra due AS
Le informazioni possono essere scambiate tra
due AS solo se una sessione peering è attiva
La sessione peering è una connessione TCP
tra i due AS
Instradamento tra Sistemi Autonomi --BGP -23
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
Instradamento tra Sistemi Autonomi --BGP -24
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
Instradamento tra Sistemi Autonomi --BGP -25
Annunci BGP
 BGP permette ad un AS di offrire connettività
ad un altro AS
 Offrire connettività significa promettere il
recapito ad una specifica destinazione
Instradamento tra Sistemi Autonomi --BGP -26
UPDATE
 Announcement = prefix + attributes values
 Annuncia nuove reti raggiungibili ed eventualmente
l’instradamento
 Annuncia reti precedentemente annunciate non più
raggiungibili
Instradamento tra Sistemi Autonomi --BGP -27
Prefissi di Rete Compressi
 Specifica solo i bytes ,corrispondenti al
prefisso
 1 – 4 byte: maschere fino a 8,16,24 bit
 Ex: 220.123
220.16.128
Instradamento tra Sistemi Autonomi --BGP -28
Filtro degli annunci
 Gli annunci sono inviati e/o accettati solo se
alcune condizioni sono verificate
 Gli annunci possono essere filtrati sulla base
di:
 Una lista di prefissi validi
 Una lista di numeri di AS
Instradamento tra Sistemi Autonomi --BGP -29
Path attributes
 BGP specifica più di un salto successivo verso la
destinazione
 Gli attributi possono indicare:
 Sistemi autonomi attraversati verso la destinazione
 Provenienza delle informazioni sull’instradamento: locali
(igp) o apprese da altri sistemi autonomi (egp)
 Attributi sono comuni a tutte le destinazioni
annunciate
 Destinazioni con attributi diversi devono essere
annunciate con messaggi diversi
 Permette di individuare cicli sugli instradamenti
e provenienza dei messaggi
Instradamento tra Sistemi Autonomi --BGP -30
Path attributes
 Codice tipo:
1. Origine informazione instradamento
2. Elenco sistemi autonomi sul percorso
3. Salto successivo
4. Discriminazione tra più punti di uscita SA
5. Preferenza all’interno del SA
6. Indicazione di percorsi riuniti
7. ID del SA che ha riunito i percorsi
Instradamento tra Sistemi Autonomi --BGP -31
Instradamento BGP
 Speaker BGP annuncia informazioni corrette
dal punto di vista del mittente esterno, ma
non necessariamente corrette dal proprio
punto di vista
 Nella figura (prox slide) R2 è lo speaker BGP
annuncia il raggiungimento di
 Rete 1 attraverso R1
 Rete 3 e Rete 4 attraverso R3
 Rete 2 attraverso R2
 Le informazioni non sono quindi relative
all’instradamento di R2
Instradamento tra Sistemi Autonomi --BGP -32
Instradamento BGP
Instradamento tra Sistemi Autonomi --BGP -33
Attributes are Used to Select
Best Routes
192.0.2.0/24
pick me!
192.0.2.0/24
pick me!
192.0.2.0/24
pick me!
192.0.2.0/24
pick me!
Given multiple
routes to the same
prefix, a BGP speaker
must pick at most
one best route
(Note: it could reject
them
all!)
Instradamento tra Sistemi Autonomi --BGP -34
BGP Route Processing
Open ended programming.
Constrained only by vendor configuration language
Receive Apply Policy =
filter routes &
BGP
Updates tweak attributes
Apply Import
Policies
Based on
Attribute
Values
Best
Routes
Best Route
Selection
Best Route
Table
Apply Policy =
filter routes &
tweak attributes
Transmit
BGP
Updates
Apply Export
Policies
Install forwarding
Entries for best
Routes.
IP Forwarding Table
-35
ASPATH Attribute
AS 1129
135.207.0.0/16
AS Path = 1755 1239 7018 6341
135.207.0.0/16
AS Path = 1239 7018 6341
AS 1239
Sprint
AS 1755
135.207.0.0/16
AS Path = 1129 1755 1239 7018 6341
Ebone
AS 12654
AS 6341
AT&T Research
RIPE NCC
RIS project
135.207.0.0/16
AS Path = 7018 6341
AS7018
135.207.0.0/16
AS Path = 6341
Global Access
135.207.0.0/16
AS Path = 3549 7018 6341
AT&T
135.207.0.0/16
AS Path = 7018 6341
AS 3549
Global Crossing
135.207.0.0/16
Prefix Originated
-38
Shorter Doesn’t Always Mean
Shorter
In fairness:
could you do
this “right” and
still scale?
Mr. BGP says that
path 4 1 is better
than path 3 2 1
Duh!
AS 4
AS 3
Exporting internal
state would
dramatically
increase global
instability and
amount of routing
state
AS 2
AS 1
Instradamento tra Sistemi Autonomi --BGP -39
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.
Instradamento tra Sistemi Autonomi --BGP -40
NOTIFICATION
 Controllo o segnalazione errori
 BGP invia un messaggio di notifica e chiude
la connessione TCP
 Errori:
1.
2.
3.
4.
5.
6.
Errore nell’intestazione del messaggio
Errore nel messaggio OPEN
Errore nel messaggio UPDATE
Timer di attesa scaduto
Errore nella macchina a stati finiti
Fine (connessione terminata)
Instradamento tra Sistemi Autonomi --BGP -41
Limiti di BGP
 BGP non può discriminare tra due percorsi sulla base





della distanza o della congestione
L’informazione di raggiungibilità fornita da due AS è
indistinguibile
BGP sceglie uno dei due percorsi possibili non sulla
base di una metrica di costo
BGP permette di suddividere il carico attraverso la
rete ma non in modo dinamico
Occorre configurare manualmente quale reti sono
annunciate da quali routers esterni
Tutti i sistemi autonomi devo concordare su uno
schema coerente per annunciare la raggiungibilità
Instradamento tra Sistemi Autonomi --BGP -42
Instradamento con arbitraggio
 Occorre un sistema per garantire la coerenza sulle





informazioni di instradamento
Database autenticato e replicato che contiene le
informazioni sulla raggiungibilità
Autenticazione permette di annunciare la
raggiungibilità di una rete solo al SA che la possiede
NAP sono i router di interconnessione tra ISP
I NAP hanno un Router Server che mantiene il data
base BGP ma non sono necessariamente speaker
BGP
Gli speaker BGP mantengono aperto un
collegamento verso il Router Server
Instradamento tra Sistemi Autonomi --BGP -43
Uno scenario BGP complesso
Instradamento tra Sistemi Autonomi --BGP -44
Classificazione delle Reti
 Stub network:
un collegamento ad un singolo isp
 Multi-homed stub network:
due o più collegamenti allo stesso isp
backup o divisione del carico
 Multi-homed network:
due o più collegamenti a isp differenti
backup o divisione del carico
Instradamento tra Sistemi Autonomi --BGP -45
Stub network
Instradamento tra Sistemi Autonomi --BGP -46
Stub network, architettura
 Un router della rete è scelto
come gateway di default è
connesso ad un singolo router
dell’isp con una o più
connessioni
 Una singola sessione di
peering in cui as200 annuncia
la sua raggiungibilità e
accetta l’instradamento di
default sul router
Instradamento tra Sistemi Autonomi --BGP -47
Instradamento statico per stub
network
 Un instradamento statico di
default è sufficiente per i pacchetti
in uscita per essere inviati su
internet attraverso la connessione
all’isp
 Un instradamento statico è anche
sufficiente per i pacchetti in
ingresso per raggiungere la rete
attraverso la connessione all’isp
 Non vi è alcun bisogno di BGP
Instradamento tra Sistemi Autonomi --BGP -48
Multi-homed stub networks
Instradamento tra Sistemi Autonomi --BGP -49
Multi-homed stub networks
 Due collegamenti allo stesso
isp
 Due routers della rete
customer sono di solito
coinvolti
Instradamento tra Sistemi Autonomi --BGP -50
Instradamento
 Un pacchetto diretto ad
Internet può attraversare uno
dei due link
 Un pacchetto proveniente da
Internet può atraversare uno
dei due link
 Un pacchetto in transito può
attraversare entrambi i link
Instradamento tra Sistemi Autonomi --BGP -51
Politiche desiderate - Backup
 Eliminare traffico in transito
 Traffico in ingresso:
 Utilizzare link 1
 Utilizzare link 2 in caso di fault su link
1
 Traffico in uscita:
 Utilizzare link 1
 Utililizzare link2 in caso di fault su link
1
Instradamento tra Sistemi Autonomi --BGP -52
Alternative a BGP
 Usare un igp:
 Pacchetti usano link 1 o link 2 a
seconda dello shortest path verso c1
 Non è possibile escludere pacchetti
in transito quando link 1 e link 2 sono
sul cammino minimo tra sorgente e
destinazione
 Usare cammini statici:
 I routers dell’isp e la rete devono
essere configurati manualmente in
modo coerente.
 Non è possibile gestire un
meccanismo di backup automatico
Instradamento tra Sistemi Autonomi --BGP -53
La strategia usata da BGP
 Annuncio /16 aggregato su
ogni arco:
 Link primario invia un
announcement standard
 Il link di backup aumenta il
costo sugli annunci in uscita e
riduce la preferenza sugli
annunci in ingresso
 Quando occorre un fault su
un link, l’annuncio del /16
aggregato sull’altro link
assicura la connettività
Instradamento tra Sistemi Autonomi --BGP -54
Metric
Instradamento tra Sistemi Autonomi --BGP -55
Local Preference
Instradamento tra Sistemi Autonomi --BGP -56
Shedding Inbound Traffic with ASPATH
Padding Hack
AS 1
provider
192.0.2.0/24
ASPATH = 2 2 2
192.0.2.0/24
ASPATH = 2
primary
backup
customer
AS 2
192.0.2.0/24
Padding will (usually)
force inbound
traffic from AS 1
to take primary link
-57
Hot Potato Routing: Go for the Closest Egress
Point
192.44.78.0/24
egress 2
egress 1
15
56
IGP distances
This Router has two BGP routes to 192.44.78.0/24.
Hot potato: get traffic off of your network as
Soon as possible. Go for egress 1!
-58
Multi-homed network
 Due link a due providers differenti
 In genere, due routers sono
coinvolti in modo tale da evitare
singoli punti di rottura
Instradamento tra Sistemi Autonomi --BGP -61
Instradamento
 Un pacchetto in uscita può
essere inviato attraverso uno
dei due link per raggiungere
Internet
 Un pacchetto in ingresso può
usare uno dei due link per
raggiungere la rete
 Un pacchetto internet può
attraversare il link 1 ed il link 2
 Un pacchetto interno può
attraversare entrambi i link
Instradamento tra Sistemi Autonomi --BGP -62
Partizione del carico
 Elimina il traffico in transito
 Traffico in uscita:
 Metà degli host interni usano
link 1,
 l’altra metà usa link 2
 Traffico in ingresso:
 usa link 1 per raggiungere
metà degli host interni
 Usa link 2 per l’altra metà
Instradamento tra Sistemi Autonomi --BGP -63
Uso di BGP per il partizionamento
 Annuncia /19 aggregato su ogni link
 split /19 e annuncia due /20, uno per ogni link:
 Partizionamento del traffico approssimato sul traffico in
ingresso
 Assume uguale capacità ed anche distribuzione del traffico
sul blocco di indirizzi
 Modifica lo split finchè un partizionamento perfetto è
ottenuto
 Accetta l’instradamento di default upstream:
 Partizionamento del traffico con instradamento verso l’uscita
più vicina (igp)
 Una buona approssimazione poiché molto del traffico è
diretto verso la rete
Instradamento tra Sistemi Autonomi --BGP -64
Padding May Not Shut Off All Traffic
AS 1
AS 3
provider
provider
192.0.2.0/24
ASPATH = 2
192.0.2.0/24
ASPATH = 2 2 2 2 2 2 2 2 2 2 2 2 2 2
primary
backup
customer
AS 2
192.0.2.0/24
AS 3 will send
traffic on “backup”
link because it prefers
customer routes and local
preference is considered
before ASPATH length!
Padding in this way is often
used as a form of load
balancing
-65
COMMUNITY Attribute to the
Rescue!
AS 1
AS 3
provider
provider
AS 3: normal
customer local
pref is 100,
peer local pref is 90
192.0.2.0/24
ASPATH = 2
COMMUNITY = 3:70
192.0.2.0/24
ASPATH = 2
primary
backup
customer
AS 2
192.0.2.0/24
Customer import policy at AS 3:
If 3:90 in COMMUNITY then
set local preference to 90
If 3:80 in COMMUNITY then
set local preference to 80
If 3:70 in COMMUNITY then
set local preference to 70
-66
Customer Provider Relationships
Instradamento tra Sistemi Autonomi --BGP -67
The AS Graph
The subgraph showing all ASes that have more than 100 neighbors in full
Instradamento tra Sistemi Autonomi --BGP -68
graph of 11,158 nodes. July 6, 2001. Point of view: AT&T route-server
AS Graph vs Internet Topology
BGP was designed to
throw away information!
The AS graph
may look like this.
Reality may be closer to this…
Instradamento tra Sistemi Autonomi --BGP -69
Growth of BGP Routes
Percentage of IPv4
space advertised
Source: Geoff Huston, http://bgp.potaroo.net, Nov. 3, 2002
Instradamento tra Sistemi Autonomi --BGP -70
Customers and Providers
provider
provider
customer
IP traffic
customer
Customer pays provider for access to the Internet
Instradamento tra Sistemi Autonomi --BGP -71
The Peering Relationship
peer
provider
peer
customer
Peers provide transit between
their respective customers
Peers do not provide transit
between peers
traffic
allowed
traffic NOT
allowed
Peers (often) do not exchange $$$
Instradamento tra Sistemi Autonomi --BGP -72
Peering Provides Shortcuts
Peering also allows connectivity between
the customers of “Tier 1” providers.
peer
provider
peer
customer
Instradamento tra Sistemi Autonomi --BGP -73
Detecting the Type of Relationships
between Autonomous Systems
Instradamento tra Sistemi Autonomi --BGP -74
Problem history
 the problem is introduced by Lixin Gao (“On
Inferring Autonomous System Relationships
in the Internet”, IEEE Trans. Networking,
2001)
 relationships are classified into three
categories: customer-provider, peer-peer, and
sibling-sibling
 BGP routing tables are used as input
 heuristics are verified with information coming
from other sources
Instradamento tra Sistemi Autonomi --BGP -75
Valid and invali AS-paths
Instradamento tra Sistemi Autonomi --BGP -76
A real life ToR problem instance
Instradamento tra Sistemi Autonomi --BGP -77
A real life ToR problem instance
Instradamento tra Sistemi Autonomi --BGP -78
Building the corresponding AS graph
Instradamento tra Sistemi Autonomi --BGP -79
An orientation for the AS graph
Instradamento tra Sistemi Autonomi --BGP -80
Example of orientable AS graph
Instradamento tra Sistemi Autonomi --BGP -81
an orientation leaving all valid paths
Instradamento tra Sistemi Autonomi --BGP -82
example of not orientable AS graph
Instradamento tra Sistemi Autonomi --BGP -83
Complexity of the problem
 The problem of determining a valid
orientation is NP-hard.
 Efficient heuristics that provide an orientation
that is consistent with most of the BGP routes
 Algorithms tested on large BGP repositories.
Instradamento tra Sistemi Autonomi --BGP -84