Résumé sur le routage à vecteur de distance

Par Francois Goffinet

Les algorithmes à vecteur de distance entrent dans la catégorie des algorithmes d'optimisation qui nécessitent plus de bande passante que de puissance en processus. Cette caractéristique fait en sorte que le routage converge plus lentement mais aussi qu'il est plus simple à implémenter. On citera RIP et IGRP comme protocoles de routage utilisant l'algorithme. Les protocoles à vecteur de distance sont particulèrement sensibles aux boucles de routage. Diverses solutions sont proposées pour pallier à cette faiblesse.

1. Concepts de base

Les algorithmes de routage à vecteur de distance (Bellman-Ford) transmettent d'un routeur à l'autre des copies périodiques d'une table de routage. Ces mises à jour régulières entre les routeurs permettent de communiquer les modifications de topologie. Chaque routeur reçoit une table de routage des routeurs voisins auxquels il est directement connecté.

L'algorithme cumule les distances afin de tenir à jour la base de données contenant les informations de topologie du réseau. Toutefois, les algorithmes de routage à vecteur de distance ne permettent pas à un routeur de connaître la topologie exacte d'un interréseau.

1.1. Découverte d'un réseau à vecteur de distance

Chaque entrée de la table de routage pour chaque réseau correspond à un vecteur de distance cumulé, qui indique la distance au réseau dans une direction donnée. Chaque réseau directement connecté à un routeur à une valeur de 0 et ainsi de suite.

1.2. Mise à jour des tables de routage

 Les mises à jour s'effectuent de routeurs en routeurs.

 Les mises à jour s'effectuent périodiquement.

 Les mises à jour consistent en des envois des tables entières.

 Les mises à jour sont envoyées à l'adresse de diffusion (broadcast) 255.255.255.255

2. Le problème des boucles de routage (routing loops) et mesure infinie (counting to infinity).

Une boucle de routage est une route diffusée pour des paquets qui n'atteignent jamais leur destination : ils passent de façon répétée par la même série de nœuds de réseau. Ce phénomène est dû à une convergence lente des informations de routage. Un routeur éloigné fait croire à des routeurs bien informés d'une route modifiée qu'il dispose d'une nouvelle route (à coût plus élévé) vers ce réseau.

Une métrique de mesure infinie est le résultat d'une boucle de routage qui engage les routeurs à incrémenter à l'infini la métrique de mesure.

3. Solutions

 Définir un nombre maximum de sauts

 Route poisoning : lorsqu'une route vers un réseau tombe, le réseau est immédiatement averti d'une métrique de distance infinie (le maximum de sauts +1), plus aucune incrémentation n'est possible.

 Split horizon : puisque toutes les interfaces d'un routeur sont censées envoyer des mises à jour de routage, le mécanisme Split horizon empêche à un routeur d'envoyer des informations (de métrique plus élevée) à travers l'interface de laquelle il a recu l'information.

 Compteur de retenue (Holddown Timer) : Après avoir retenu qu'une route vers un réseau est tombée, le routeur attend une certaine période de temps avant de valider n'importe quelle autre information de routage à propos de ce réseau.

Si l'information d'une route tombée redevenant accessible est apprise du même voisin en dedans les délais, la route est réinscrite dans la table de routage. Si l'information d'une route de nouveau accessible provient d'un autre voisin avec une meilleure métrique, la route est réinscrite dans la table de routage et le compteur est arrêté (il n'y'a plus d'attente).

 Triggered Update : Une mise à jour est envoyée immédiatement avant l'expiration du compteur (délai) lorsque une route est tombée. Utilisée avec la mesure de métrique infinie , cette solution assure que tous les routeurs ont la connaissance des routes tombées avant que n'importe quel compteur expire.

 Split Horizon avec Poison Reverse : le protocole de routage avertit de toutes les routes sortant d'une interface,à part celles qui ont été apprises d'une mise à jour plus récente venant dans cette interface sont marquée d'une métrique de distance infinie.

Note perso : Les solutions énumérées sont à connaitre par coeur ,avant de les mettre en pratique . Ce sont des techniques fondamentales ,on l'aura compris . "No pain,No Gain" so be the winners guys !