Border Gateway Protocol

Un article de Wikipédia, l'encyclopédie libre.
Aller à : Navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir BGP.
Pile de protocoles
7 • Application
6 • Présentation
5 • Session
4 • Transport
3 • Réseau
2 • Liaison
1 • Physique
Modèle Internet
Modèle OSI

Border Gateway Protocol (BGP) est un protocole d'échange de route utilisé notamment sur le réseau Internet. Son objectif est d'échanger des informations d'accessibilité de réseaux (appelés préfixes) entre routeurs par le biais de sessions TCP (sur le port 179).

BGP est utilisé pour véhiculer des réseaux entre Autonomous Systems (AS) car il est le seul protocole à supporter de très grands volumes de données et à disposer de possibilités étendues de sélection.

Contrairement aux protocoles de routage interne, BGP n'utilise pas de métrique classique mais base les décisions de routage sur les chemins parcourus, les attributs des préfixes et un ensemble de règles de sélection définies par l'administrateur de l'AS. On le qualifie de protocole à vecteur de chemin (path vector protocol).

BGP supporte le routage sans classe et utilise l'agrégation de routes afin de limiter la taille de la table de routage. Depuis 1994, la version 4 du protocole est utilisée sur Internet, les précédentes étant considérées comme obsolètes. Ses spécifications sont décrites dans la RFC 4271 A Border Gateway Protocol 4 (BGP-4).

D'autres versions de BGP permettent l'échange de routes IPv6 (RFC 2545) et l'extension multi-protocole (MP-BGP, RFC 2858) qui permet l'utilisation de BGP dans un réseau MPLS.

Sommaire

[modifier] Fonctionnement

Liaisons eBGP et iBGP. La rupture du lien physique entre A et C n'interrompt pas la session iBGP entre ces routeurs si une adresse IP logique est utilisée.

Les connexions entre deux voisins BGP (neighbours ou peers) sont configurées manuellement entre deux routeurs. Ils communiquent alors entre eux via une session TCP sur le port 179 initiée par l'un des deux routeurs. BGP est le seul protocole de routage à utiliser TCP comme protocole de transport.

Il existe deux versions de BGP : Interior BGP (iBGP) et Exterior BGP (eBGP). iBGP est utilisé à l'intérieur d'un Autonomous System alors que eBGP est utilisé entre deux AS.

En général, les connexions eBGP sont établies sur des connexions point-à-point ou sur des réseaux locaux (un Internet Exchange Point par exemple), le TTL des paquets de la session BGP est alors fixé à 1. Si la liaison physique est rompue, la session eBGP l'est également, et tous les préfixes appris par celle-ci sont annoncés comme supprimés et retirés de la table de routage.

À l'inverse, les connexions iBGP sont établies entre des adresses logiques, non associées à une interface physique particulière. Ceci permet, en cas de rupture d'un lien physique, de conserver la session iBGP active si un lien alternatif existe et si un protocole de routage interne dynamique est employé (par exemple OSPF).

Une fois la connexion entre deux routeurs établie, ceux-ci s'échangent des informations sur les réseaux qu'ils connaissent et pour lesquels ils proposent du transit, ainsi qu'un certain nombre d'attributs associés à ces réseaux qui vont permettre d'éviter des boucles (comme AS Path) et une sélection fine de la meilleure route.

[modifier] Messages du protocole BGP

OPEN 
ce message est utilisé dès que la connexion TCP est établie entre les voisins BGP, il permet d'échanger des informations tels que les numéros d'AS respectifs et de négocier les capacités de chacun des pairs ;
KEEPALIVE 
maintien la session ouverte. Par défaut le message KEEPALIVE est envoyé toutes les 60 secondes, et trois messages manqués entraînent la fermeture de la session ;
UPDATE 
ce message permet l'annonce de nouvelles routes ou le retrait de routes ;
NOTIFICATION 
message de fin de session BGP suite à une erreur.

[modifier] Machine à états finis de BGP

Diagramme d'automate fini de BGP

Le logiciel permettant de gérer les échanges de route doit implémenter un automate fini constitués de six états liés par treize événements. Les automates dialoguent entre eux par des messages (OPEN, KEEPALIVE, UPDATE, NOTIFICATION).

Les états sont :

  1. Idle
  2. Connect
  3. Active
  4. OpenSent
  5. OpenConfirm
  6. Established

Les événements :

  1. BGP Start
  2. BGP Stop
  3. BGP Transport connection open
  4. BGP Transport connection closed
  5. BGP Transport connection open failed
  6. BGP Transport fatal error
  7. ConnectRetry timer expired
  8. Hold Timer expired
  9. KeepAlive timer expired
  10. Receive OPEN message
  11. Receive KEEPALIVE message
  12. Receive UPDATE message
  13. Receive NOTIFICATION message

Les changements d'états et le comportement attendus sont les suivant :

Idle 
Dans cet état, le processus refuse les connexions et n'alloue aucune ressource. Quand l'événement de démarrage (manuel ou automatique) est reçu, le processus initie les ressources et une connexion avec les voisins configurés, et écoute les connexions entrantes sur le port TCP 179 et bascule dans l'état Connect. En cas d'erreur, la connexion est coupée et le processus retourne dans l'état Idle ;
Connect 
attend que la connexion TCP soit établie, puis envoie le message OPEN et bascule dans l'état OpenSent. En cas d'erreur, attend un délai prédéfini et continue à écouter sur le port 179 puis bascule dans l'état Active ;
Active 
Tente d'établir une connexion TCP avec le voisin. En cas de réussite, envoie le message OPEN et bascule dans l'état Connect, tout autre événement provoque le retour dans l'état Idle ;
OpenSent 
le message OPEN a été envoyé, attend le message OPEN en retour et s'il ne se produit pas d'erreur, envoie un KEEPALIVE et bascule dans OpenConfirm, dans les autres cas, envoie un message NOTIFICATION et retourne dans l'état Idle ;
OpenConfirm 
attend un message KEEPALIVE et bascule alors en Established, ou bien un message NOTIFICATION et retourne dans l'état Idle ;
Established 
la connexion BGP est établie, les messages UPDATE et KEEPALIVE peuvent être échangés, un message NOTIFICATION cause le retour dans l'état Idle.

[modifier] Attributs

Chaque préfixe dans BGP est associée à un certain nombre d'attributs. Ces attributs sont classés en quatre types différents :

Voici quelques attributs avec leurs types :

Attribut Type Description
Aggregator OT Identificateur et AS du routeur qui a réalisé l'agrégation
AS Path WM Liste ordonnée des systèmes autonomes traversés
Atomic Aggregate WD Liste des AS supprimés après une agrégation
Cluster ID ON Cluster d'origine
Community OT Marquage de route
Local Preference WD Métrique destinée aux routeurs internes en vue de préférer certaines routes externes
Multiple Exit Discriminator (MED) ON Métrique destinée aux routeurs externes en vue de préférer certaines routes internes
Next Hop WM Adresse IP du voisin eBGP
Origin WM Origine de la route (IGP, EGP ou Incomplete)
Originator ID ON Identificateur du route reflector
Weight O(N) Extension Cisco en vue de préférer localement certains voisins, n'est jamais transmise aux voisins

[modifier] Sélection de la meilleure route

Quand plusieurs routes sont possibles vers un même réseau (ce qui inclut le masque de réseau), BGP préfère une des routes selon les critères suivants. Seule la meilleure route sera utilisée et annoncée aux voisins.

Ordre Nom Description Préférence
1 Weight[1] Préférence administrative locale la plus élevée
2 Local Preference Préférence à l'intérieur d'un AS la plus élevée
3 Self-Originated Préférence des réseaux dont l'origine est ce routeur vrai > faux
4 AS Path Préférence du chemin avec les moins d'AS traversés le plus court
5 Origin Préférence du chemin en fonction de la façon dont ils sont connus par le routeur d'origine IGP > EGP > Incomplete
6 MED Préférence en fonction de la métrique annoncée par l'AS d'origine la plus faible
7 External Préférence des routes eBGP sur les routes iBGP eBGP > iBGP
8 IGP Cost Métrique du Next-Hop dans l'IGP la plus faible
9 eBGP Peering Préfère les routes les plus stables la plus ancienne
10 Router ID Départage en fonction de l'ID du routeur la plus faible

[modifier] Route reflectors et Confederations

Confederations et route reflectors

Dans iBGP, les routes ne sont pas transitives, c'est-à-dire qu'une route reçue via iBGP n'est pas transmise aux voisins iBGP, ce qui implique que tous les routeurs participant au routage BGP au sein d'un AS doivent établir des connexions entre eux (full mesh) ce qui peut poser des problèmes d'échelle, le nombre de connexions augmentant selon le carré du nombre de routeurs présents dans l'AS. Deux solutions sont disponibles pour passer outre cette limite : les route reflectors et les confederations.

route reflectors 
cette extension protocolaire permet de réduire le nombre de connexions nécessaires au sein d'un AS. Un seul routeur (ou deux routeurs pour la redondance) établit des sessions avec tous les autres routeurs de son groupe. Les autres routeurs (ses clients) n'ont besoin que de se connecter à lui.
confederations 
est utilisé dans les très grands réseaux ou l'AS est subdivisé en petits AS internes. Les confédérations peuvent être utilisées conjointement avec les routes reflectors. eBGP est utilisé entre les confédérations. Les confédérations sont masquées quand le préfixe est annoncé en dehors de l'AS principal.

Pour éviter les boucles possibles avec ces configuration, des attributs supplémentaires sont utilisés : Cluster_ID et Originator_ID.

Lorsqu'un réseau est ajouté à un AS, il doit être annoncé au maillage BGP : soit au route reflector lorsqu'il existe, soit à l'ensemble des routeurs BGP de l'AS. BGP ne se substitue cependant pas à un protocole de routage interne.

[modifier] AS sur 32 bits

Croissance du nombre d'AS sur Internet depuis 1997.

Le standard RFC 1771 (A Border Gateway Protocol 4 (BGP-4)) prévoyait le codage des numéros d'AS sur 16 bits, c'est-à-dire 64510 AS publics possibles en tenant compte du fait que les numéros 64512 à 65535 sont réservés pour des usages privés. En 2006, il restait environ 22000 AS libres et la croissance linéaire[2] laissait présager un épuisement complet des AS disponibles entre 2010 et 2013. La RFC 4893 a défini des AS codés sur 32 bits, représentés par la notation x.y (où x et y sont des entiers compris entre 0 et 65535), les AS 1.x et 65535.65535 étant réservés, ce qui porte le nombre d'AS disponibles à plus de quatre milliards. Pour permettre la traversée des groupes de routeurs qui ne gèrent pas ces nouveaux AS, le nouvel attribut OT AS4_PATH est employé.

L'assignation des AS sur 32 bits a débuté en 2007, et depuis 2009, le RIPE NCC distribue des AS 32 bits à la demande.

[modifier] Utilisation

BGP est principalement utilisé entre les opérateurs et fournisseurs d'accès à Internet pour l'échange de routes.

La plupart des utilisateurs finaux d'Internet n'ont qu'une seule connexion à un fournisseur d'accès à Internet. Dans ce cas, BGP est inutile car une route par défaut est suffisante. Cependant, une entreprise qui serait connectée de façon redondante à plusieurs FAI (multi-homing) pourrait obtenir un numéro de système autonome propre et établir des sessions BGP avec chacun des fournisseurs.

Outre Internet, des réseaux IP privés peuvent utiliser BGP, par exemple pour interconnecter des réseaux locaux utilisant OSPF.

[modifier] Problèmes

[modifier] Instabilités et damping

Illustration du damping BGP

BGP est sensible à l'oscillation rapide des routes, les annonces des routes inaccessibles devant être propagées à tous les voisins BGP, obligeant ceux-ci à recalculer leur table de routage. L'effet cumulé de ces annonces peut causer une surcharge et nuire à la stabilité du routage sur un réseau tel qu'Internet. Une route oscillante peut être causée par un lien ou une interface défectueuse (mauvaise configuration, panne) ou un routeur qui redémarre.

Une fonctionnalité nommée damping (ou parfois dampening, RFC 2349 BGP Route Flap Damping; damping signifie amortissement en anglais) vise à réduire les effets de l'oscillation de routes. À chaque oscillation d'une route, le damping va accroître une pénalité numérique associée à cette route. Cette pénalité va décroître exponentiellement avec le temps. Quand la pénalité dépasse un seuil prédéfini, la route sera marquée comme inaccessible et les mises à jour à son sujet ignorées, et ce jusqu'à ce qu'un seuil inférieur pour la pénalité soit atteint.

Le document RIPE-229[3] définit des paramètres recommandés pour le damping. Cependant, à la lumière de l'expérience avec cette configuration, la recommandation du groupe de travail routage du RIPE est arrivée à la conclusion que le damping n'était plus recommandé et que le document RIPE-229 devait être considéré comme obsolète[4].

[modifier] Vol d'adresse IP

Si un routeur annonce un préfixe pour lequel il n'assure pas réellement le transit, ce dernier peut devenir inaccessible depuis tout ou une partie d'Internet. L'effet sera encore plus prononcé si les préfixes annoncés sont plus spécifiques (c'est-à-dire si le masque réseau est plus long) que les préfixes légitimes, car les routes plus spécifiques sont toujours préférées.

Pour se prémunir de ce problème, les fournisseurs limitent les préfixes qu'ils acceptent de leurs voisins. Ces filtres sont alors mis à jour manuellement si le voisin vient à annoncer de nouvelles routes. Vu la complexité de la gestion de ces listes de filtrage, il est plus rare que les grands opérateurs filtrent les préfixes entre eux. Certains outils permettent cependant de bâtir ces filtres automatiquement en fonction du contenu de bases de données de routage (comme celle du RIPE). D'autres approches sont S-BGP[5] et soBGP[6].

En février 2008, le site YouTube a été inaccessible depuis n'importe quel point de la planète pendant environ 2 heures. Le gouvernement pakistanais avait annoncé ce jour là un blocage de YouTube au Pakistan[7],[8],[9], ordre qui a été exécuté par l'opérateur Pakistan Telecom.

Ainsi, Pakistan Telecom a annoncé à tous les routeurs des fournisseurs d'accès qu'il était la meilleure route à qui envoyer tout le trafic YouTube, qui a alors été coupé sur l'ensemble de la planète.

Ce type d'incident est également désigné sous les noms d'IP hijacking (détournement d'adresse IP) et de black hole (trou noir).

[modifier] Croissance de la table de routage

Croissance de la table de routage, de 1989 à 2009

Un des problèmes auquel BGP doit faire face sur Internet est la croissance de la table de routage des routeurs de la default-free zone, c'est-à-dire ceux qui disposent d'une table de routage complète et n'utilisent pas de route par défaut. Avec le temps, les routeurs plus anciens n'ont plus les ressources mémoire ou CPU nécessaires au maintien d'une table complète. D'autre part, la taille de la table nuit à la vitesse de convergence, le CPU étant particulièrement sollicité lors de changements importants (établissement de nouvelles connexions ou changements importants de topologie).

Jusqu'à 2001, la croissance a été exponentielle, menaçant le fonctionnement d'Internet. À cette date, des efforts ont été entrepris pour réduire les préfixes en les agrégeant. Ceci a permis une croissance linéaire pendant plusieurs années. Cependant la croissance exponentielle a repris à partir de 2004 environ sous la pression du nombre croissant de réseaux finaux qui disposent de plusieurs connexions redondantes.

En 2010, le nombre de préfixes diffusés sur Internet est d'environ 330 000[10].

[modifier] Équilibrage de la charge et asymétrie

BGP ne dispose pas d'un système d'équilibrage de la charge entre plusieurs liens et ne tient pas compte de la congestion éventuelle des liens : si un AS est connecté à plusieurs fournisseurs de transit vers Internet, il se peut que certains soient congestionnés tandis que d'autres sont peu utilisés. De façon générale, les AS prennent des décisions de routage de façon indépendante, un AS a donc peu d'influence sur les décisions prises par un autre AS et ne dispose pas de contrôle fin de l'équilibrage du trafic entrant.

Diverses techniques existent cependant pour tenter de rééquilibrer la charge entre ces liens :

Pour les mêmes raisons, le trafic peut être asymétrique, ce qui est fréquent entre les grands opérateurs qui suivent la politique dite de la patate chaude (en), qui consiste à router un paquet destiné à un réseau externe vers l'interconnexion la plus proche, évitant ainsi la traversée de sa propre dorsale.

[modifier] Looking glass

Il existe un certain nombre de routeurs sur Internet qui permettent la consultation de la table de routage globale via une interface web. Voici un exemple de consultation[11] :

> show ip bgp 91.198.174.2
BGP routing table entry for 91.198.174.0/24, version 151383419
Paths: (2 available, best #1, table Default-IP-Routing-Table)
 Advertised to non peer-group peers:
 82.115.128.225 
 TDC [3292] WIKIMEDIA-EU [43821]
   82.115.128.18 from 82.115.128.18 (62.95.30.10)
     Origin IGP, localpref 100, valid, external, best
     Community:  215745616 215746418
 IPO-EU [12552] PORT80-GLOBALTRANSIT [16150] WIKIMEDIA-EU [43821]
   82.115.128.26 from 82.115.128.26 (62.109.44.1)
     Origin IGP, localpref 100, valid, external

Dans cet exemple, l'adresse IP 91.198.174.2 fait partie du préfixe le plus spécifique 91.198.174.0/24. Deux routes sont disponibles, la première a traversé deux AS (43821, son AS d'origine, puis 3292) et la seconde trois (43821, 16150 et 12552), le Local Pref étant égal, la première route, plus courte en termes de nombre d'AS traversés, est préférée.

Les noms associés aux AS sont ajoutés par l'interface en consultant une base de données de routage publique.

[modifier] Implémentation libre de BGP

[modifier] Références

  1. ↑ Cisco uniquement
  2. ↑ 32-bit ASN Henk Uiterwaal, RIPE-53, 2006
  3. ↑ RIPE-229 RIPE Routing-WG Recommendations for Coordinated Route-flap Damping Parameters, octobre 2001
  4. ↑ RIPE Routing Working Group Recommendations on Route-flap Damping, mai 2006
  5. ↑ Securing the Border Gateway Protocol The Internet Protocol Journal - Volume 6, Number 3
  6. ↑ Securing BGP Through Secure Origin BGP id
  7. ↑ Crashdump.fr, « Protocole BGP, l’Internet en danger ? », 29 août 2008
  8. ↑ Pakistan lifts the ban on YouTube, 26 février 2008, BBC News
  9. ↑ YouTube Hijacking: A RIPE NCC RIS case study, RIPE NCC
  10. ↑ BGP Routing Table Analysis Reports
  11. ↑ http://lg.intron.net/

[modifier] Liens externes

Les principales RFC concernées sont les suivantes :

Ce document provient de « http://fr.wikipedia.org/wiki/Border_Gateway_Protocol ».
Outils personnels
Espaces de noms
Variantes
Actions
Navigation
Contribuer
Imprimer / exporter
Boîte à outils
Autres langues