Algorithmes de routage dynamique

Les routeurs dans un groupe de routeurs échangent suffisamment d'informations sur le réseau pour que chaque routeur puisse créer une table décrivant la manière d'envoyer des datagrammes adressés à un segment particulier. Que communiquent exactement les routeurs ? Comment un routeur construit-il sa table de routage ? Comme vous l'avez probablement compris maintenant, le comportement d'un routeur dépend entièrement de la table de routage. Plusieurs protocoles de routage sont actuellement utilisés. Beaucoup de ces protocoles de routage sont conçus autour de l'une des deux méthodes de routage suivantes : le routage à vecteur de distance et le routage à état de liens.

Ces méthodes sont mieux comprises comme des approches différentes de la tâche de communication et de collecte d'informations de routage. Les sections suivantes traitent du routage à vecteur de distance et à état de lien. Il existe deux protocoles de routage qui utilisent ces méthodes : Routing Information Protocol (RIP, un protocole de routage à vecteur de distance) et l'Open Shortest Path First (OSPF, un protocole de routage à état de liens).

Le routage à vecteur de distance (également appelé routage Bellman-Ford) est une méthode de routage simple et efficace utilisée par de nombreux protocoles de routage. Le routage à vecteur de distance domine l'industrie du routage, et il est encore assez courant, bien que récemment des méthodes de routage plus sophistiquées (telles que le routage à état de liens) aient gagné en popularité.

Le routage à vecteur de distance est conçu pour minimiser la communication requise entre les routeurs et pour minimiser la quantité de données qui doivent résider dans la table de routage. La philosophie derrière le routage à vecteur de distance est qu'un routeur n'a pas besoin de connaître le chemin complet vers chaque segment de réseau - il doit seulement savoir dans quelle direction envoyer un datagramme adressé au segment (d'où le terme vecteur). La distance entre les segments du réseau est mesurée par le nombre de routeurs qu'un datagramme doit traverser pour passer d'un segment à l'autre. Les routeurs utilisant un algorithme à vecteur de distance tentent d'optimiser le chemin en minimisant le nombre de routeurs qu'un datagramme doit traverser. Ce paramètre de distance est appelé nombre de sauts.

Le routage à vecteur de distance fonctionne comme suit :

1. Lorsque le routeur A s'initialise, il détecte les segments auxquels il est directement rattaché et place ces segments dans sa table de routage. Le nombre de sauts vers chacun de ces segments directement attachés est de 0 (zéro), car un datagramme n'a pas besoin de passer par des routeurs pour aller de ce routeur au segment.
2. À un certain intervalle périodique, le routeur reçoit un rapport de chaque routeur voisin. Le rapport énumère tous les segments de réseau que les routeurs voisins connaissent et le nombre de sauts vers chacun de ces segments.
3. Lorsque le routeur A reçoit le rapport des routeurs voisins, il intègre les nouvelles informations de routage dans sa propre table de routage comme suit :
   • Si le routeur B (l'un des routeurs voisins) connaît un segment de réseau que le routeur A n'a pas actuellement dans sa table de routage, le routeur A ajoute le segment à sa table de routage. La route pour le nouveau segment est le routeur B, ce qui signifie que si le routeur A reçoit un datagramme adressé au nouveau segment, il transmet ce datagramme au routeur B. Le nombre de sauts pour le nouveau segment est quel que soit le routeur B répertorié comme le nombre de sauts plus 1 , car le routeur A est un saut plus loin du segment que le routeur B.
   • Si le routeur B répertorie un segment qui est déjà dans la table de routage du routeur A, le routeur A ajoute 1 au nombre de sauts reçu de B et compare le nombre de sauts révisé à la valeur stockée dans sa propre table de routage. Si le chemin via B est plus efficace (moins de sauts) que le routeur A connaît déjà, le routeur A révise sa table de routage pour répertorier le routeur B comme route pour les datagrammes adressés à ce segment.
   • Si le nombre de sauts révisé pour le chemin vers le segment via le routeur B (le nombre de sauts reçu de B plus 1) est supérieur au nombre de sauts actuellement répertorié dans la table de routage du routeur A, la route via B n'est pas utilisée. Le routeur A continue d'utiliser la route déjà stockée dans sa table de routage.

À chaque cycle de mise à jour de la table de routage, les routeurs reçoivent une image plus complète du réseau. Les informations sur les routes se diffusent lentement sur le réseau. En supposant que rien ne change sur le réseau, les routeurs finiront par apprendre le chemin le plus efficace vers chaque segment.

Le routage à vecteur de distance est une approche valable si vous supposez que l'efficacité d'un chemin coïncide avec le nombre de routeurs qu'un datagramme doit traverser. Cette hypothèse est un bon point de départ, mais dans certains cas, c'est une simplification excessive. Une route via une liaison lente prend plus de temps qu'une route via une liaison à grande vitesse, même si le nombre de sauts est le même. De plus, le routage à vecteur de distance ne s'adapte pas bien aux grands groupes de routeurs.

Chaque routeur doit maintenir une entrée de table de routage pour chaque destination, et les entrées de table sont simplement des valeurs de vecteur et de nombre de sauts. Le routeur ne peut pas économiser ses efforts par une meilleure connaissance de la structure du réseau. De plus, des tables complètes de valeurs de distance et de nombre de sauts doivent passer entre les routeurs même si la plupart des informations ne sont pas nécessaires. Le routage à état de liens est désormais la principale alternative au routage à vecteur de distance.

La philosophie derrière le routage à état de liens est que chaque routeur tente de construire sa propre carte interne de la topologie du réseau. Chaque routeur envoie périodiquement des messages d'état au réseau. Ces messages d'état répertorient les autres routeurs du réseau auxquels le routeur est directement connecté ainsi que l'état de lien (si le lien est actuellement opérationnel). Les routeurs utilisent les messages d'état reçus d'autres routeurs pour créer une carte de la topologie du réseau. Lorsqu'un routeur doit transmettre un datagramme, il choisit le meilleur chemin vers la destination en fonction des conditions existantes.

Les protocoles à états de liens nécessitent plus de temps de traitement sur chaque routeur, mais la consommation de bande passante est réduite car chaque routeur n'est pas tenu de propager une table de routage complète. En outre, il est plus facile de suivre les problèmes sur le réseau car le message d'état d'un routeur donné se propage sans changement sur le réseau. (La méthode du vecteur de distance, en revanche, incrémente le nombre de sauts à chaque fois que les informations de routage passent à un routeur différent).