Algorithme de sélection de la meilleure route BGP4

Le protocole de routage dynamique BGP bénéficie d’un algorithme bien défini pour sélectionner la meilleure route dans le cas où plusieurs voisins (neighbors) d’un peer BGP annoncent une même route. Le but de ce billet n’est pas de décrire dans son intégralité l’algorithme de sélection, mais simplement d’aborder les grandes lignes et d’en assimiler quelques notions importantes. En effet, pour obtenir une documentation complète sur le sujet, je vous recommande le lien suivant sur le site de cisco qui sera certainement plus précis que je ne peux l’être !

Dans les grandes lignes, voici ce qu’il se passe donc lors du déroulement de l’algorithme de sélection du meilleur chemin :

1. Si le chemin spécifie un prochain saut qui est inaccessible, la mise à jour de routage est rejetée
2. Le chemin qui possède le poids administratif le plus élevé sera alors préféré
3. Si les poids sont égaux, le chemin possédant une locale preference la plus élevée sera choisie. L’attribut « local preference » permet de définir un point de sortie bien précis au sein d’un même AS.
4. Dans le cas où les attributs « local preference » sont égaux, le chemin qui est initié par le processus BGP local du routeur sera sélectionné
5. Si aucune route n’a pour origine le routeur en question, celle possédant l’AS Path le plus petit sera alors pris. L’AS Path n’est ni plus ni moins que la liste ordonnée des AS traversés lors du cheminement d’un paquet.
6. Si la taille de l’AS Path est identique pour tous les chemins, le chemin ayant l’origine la plus « courte » sera alors désigné. L’origine peut être de trois types : IGP, EGP ou INCOMPLETE. Pour mémoire, l’IGP concerne les protocoles de routage internes à un AS, l’EGP par définition externe et INCOMPLETE toute autre source d’apprentissage des routes.
7. Si les origines des routes sont identiques, l’attribut Multi-Exit Discriminator est utilisé (ou MED). Cet attribut est diffusé dans les updates BGP et ne représente ni plus ni moins qu’une suggestion faite par un routeur à son peer situé dans un autre AS pour indiquer une métrique précise.
8. Si ces attributs MED sont égaux, les routes à destination de peers externes seront préférées plutôt que les internes (préférence eBGP sur iBGP)
9. Si les routes sont toutes du même type, le chemin vers le voisin ayant la métrique la plus faible dans l’IGP sera choisi
10. Si les métriques des routes vers les voisins IGP les plus proches sont identiques, la route la plus stable (ie la plus ancienne) sera sélectionnée
11. Enfin, le choix définitif de la meilleure route sera fait en fonction du  Router ID le plus faible des neighbors.

En conséquence, il est possible de jouer sur l’algorithme de sélection du meilleure chemin afin de maitriser au mieux le transit des flux et bénéficier de la meilleure route (en fonction des différents critères). Typiquement, dans beaucoup de cas, on paramétrera par exemple la locale preference sur deux routeurs d’un même AS (dans le cas de deux liens de débits différents, on affectera ainsi une valeur de « locale preference » plus importante au lien le plus rapide et inversemment. Cela permet donc, d’une manière relativement simple et dans des cas basiques, de gérer la sortie des flux depuis son AS.

Il existe principalement deux façons de déclarer la local preference sur les routeurs Cisco :

• Via la commande bgp default local-preference XX dans le mode de configuration du routeur BGP (router ID_PROCESS_BGP). Cette commande est donc prise en compte pour toutes les mises à jour envoyées depuis le routeur concerné à ses peers BGP du même AS
• L’utilisation de route-map permet de définir les annonces qu’il est nécessaire de tagguer au niveau de la local preference ainsi que la valeur souhaitée.

Dans le cas des flux entrants, il sera intéressant de jouer sur le paramétre d’AS-path. Pour cela, il existe une technique appelée « AS-Path prepend », qui consiste à rajouter n fois son numéro d’AS au sein de l’AS-path, permettant ainsi implicitement de le faire grandir de manière artificielle et de faire choisir d’autres routes que celle-ci pour le trafic entrant. Cette opération s’effectue au sein de la route-map via la commande set as-path prepend AS_NUM AS_NUM AS_NUM.

J’espère que ce billet aura donc permis d’appréhender certaines notions et d’en déduire le fonctionnement de manière un peu plus détaillée. Celui-ci n’est volontairement pas explicite au niveau des commandes carle lien suivant sur le site de Cisco permet d’en approfondir les subtilités. De plus, le but original du billet était purement et simplement d’aborder certains concepts mis en oeuvre dans BGP.