1.1 Introduction

Les systèmes sur un réseau peuvent généralement être divisés en deux types : les hôtes et les routeurs.
Un hôte possède généralement une seule interface réseau et peut être la source ou la destination finale d'un paquet.
Un routeur possède de multiples interfaces réseau et fait suivre les paquets d'une interface à une autre pour que le paquet atteigne sa destination.

Le routage est une tâche de la couche réseau (couche 3 du modèle OSI) qui permet de décider sur quelle interface du routeur un paquet doit être émis.
La couche réseau fonctionnant en mode non connecté, cette tâche doit être répétée pour chaque paquet entrant, d'où la nécessité d'une prise de décision rapide.
Une table maintenue par chaque routeur d'un réseau, la table de routage, permet d'établir une correspondance entre le réseau de destination (auquel appartient le destinataire du paquet), et l'adresse du prochain routeur (prochain saut) permettant d'atteindre la destination finale.

Cette table de routage peut être constituée de deux manières :

• De manière statique : chaque routeur possède un fichier lu au moment de son initialisation, et qui établit, de manière fixe, la correspondance réseau de destination - prochain saut.
  Cependant cette méthode se révèle fastidieuse dans le cas de gros réseaux, puisqu'il faut configurer manuellement et individuellement chaque routeur.
  De plus, les routeurs se révèlent incapables de s'adapter automatiquement à une modification de la topologie de réseau, et encore moins aux variations de l'état de congestion des liens.
  
  
• Les algorithmes de routage dynamiques ne nécessitent aucune configuration initiale de la table de routage : celle-ci est construite automatiquement en se basant sur des messages que s'échangent les routeurs.
  Dans la suite, nous ne nous intéresserons qu'à ce type d'algorithme de routage.

Il existe deux grandes familles d'algorithme de routage dynamiques :

• Le routage à vecteur de distance (Distance Vector)
• Le routage à états de lien (Link State)

1.2 Routage à vecteur de distance

Cet algorithme se base sur le principe que chaque routeur dispose d'une table de routage indiquant, pour chaque réseau de destination, l'interface locale permettant de l'atteindre et la meilleure distance qui lui est associée.
Cette distance est un coût estimé par chaque routeur à partir de messages envoyés par les routeurs voisins. Elle impose de fixer une métrique commune à chaque routeur, basée par exemple sur :

• Le nombre de saut, c'est à dire le nombre de réseaux intermédiaires que le paquet devra traverser avant d'atteindre sa destination finale. Dans ce cas, la distance entre routeurs voisins est une constante fixée à 1.
  
• Le nombre de paquets dans la file d'attente de l'interface choisie, ce qui permet d'avoir une idée de l'état de congestion d'un lien particulier.
  
• Le temps mis pour atteindre le prochain routeur. Ce délai est estimé grâce à l'émission de paquets comparables à des Ping ICMP.
  
• Le coût financier du lien.

Le coût total d'un chemin est alors calculé en sommant les coûts des sauts qui le composent, et ces coûts estimés sont régulièrement envoyés aux routeurs voisins afin qu'à leur tour ils mettent à jour leur table.
A l'initialisation, un routeur n'a qu'une connaissance très limitée du réseau : sa table de routage de contient que les réseaux auxquels il est directement connecté.
Il va ensuite envoyer le contenu de sa table de routage à ses voisins, qui pourront mettre à jour leur propre table en se basant sur les coûts indiqués par l'émetteur.
Pour avoir leur propre estimation du coût, il leur suffit de sommer le coût estimé par le routeur émetteur avec le coût pour atteindre ce dernier. La mise à jour effectuée, ils émettent à leur tour leur table, à destination de leurs autres voisins, …
Au fur et à mesure de la progression dans le réseau, chaque routeur finit par connaître l'existence des réseaux auxquels il n'est pas connecté, mais que ses voisins sont capables d'atteindre, en se basant eux mêmes sur d'autres routeurs, ...
Par exemple, supposons qu'un routeur K possède dans sa table de routage la destination X avec une distance d1. Il envoie cette information à son voisin J, qui possèdent dans sa table une entrée pour K avec une distance d2. En sommant ces distances, J sait maintenant qu'il peut atteindre X en passant par K avec un coût de d1 + d2. Si J possède une autre entrée indiquant qu'il peut atteindre X par un autre voisin (L), mais avec un coût supérieur (d3), il en déduit qu'il a trouvé un chemin plus court le menant à X, et par conséquent il met à jour sa table en remplaçant le triplet (X, L, d3) par (X, K, d1 + d2).
En envoyant régulièrement le contenu de la table de routage, et en effectuant une mise à jour des entrées uniquement lorsqu'un nouveau coût est inférieur à l'ancien, cet algorithme permet de découvrir la distance la plus courte pour atteindre un réseau.

Cependant certains défauts doivent être mis en évidence, et notamment le manque de réactivité lors du changement de topologie du réseau (panne d'un routeur par exemple), comme nous allons le voir lors de l'étude du protocole RIP.

1.3 Le protocole RIP

Le protocole RIP (Routing Information Protocol) se base sur un algorithme à vecteur de distance dont la métrique est le nombre de réseaux qu'un paquet doit traverser pour atteindre sa destination finale.
Sa mise au point étant assez ancienne, il a été prévu initialement pour être mis en place sur des réseaux dont le diamètre est inférieur ou égal à 15, une distance de 16 représentant un distance infinie (c'est à dire une impossibilité d'atteindre la destination).

Il reprend les principales caractéristiques décrites dans la section précédente :

• Chaque routeur possède une table de routage, dont les entrées indiquent la distance et le prochain saut pour atteindre un réseau.
  
• Cette table de routage est périodiquement envoyée à tous les voisins.
  
• Lorsqu'un routeur reçoit le contenu de la table d'un voisin, il calcule les nouvelles distances estimées et met à jour sa propre table dans deux cas : si le nouveau coût est inférieur à celui indiqué par la table locale, et que le prochain saut est différent ; ou si le prochain saut est identique, même si le nouveau coût est supérieur à l'ancien.

D'autres caractéristiques sont ajoutées pour résoudre les problèmes relatifs à l'algorithme utilisé :

• On considère qu'un routeur est tombé si on ne reçoit pas de nouvelles pendant plus de 180 secondes, et le coût pour l'atteindre est forcé à 16 (infini).
  
• Pour éviter les problèmes de boucle pouvant apparaître lors du changement de la topologie du réseau, on utilise la méthode de l'horizon éclaté : quand un routeur apprend d'un voisin une nouvelle route, la première table qu'il envoie à ce voisin correspond à sa table de routage mais avec une valeur infinie pour les routes nouvellement apprises.
  
• Pour accélérer la convergence de l'algorithme, si un routeur modifie sa table de routage, il n'attend pas l'expiration de son temporisateur pour envoyer le contenu de sa table : il l'émet immédiatement à tous ses voisins.

La simplicité et les performances de RIP font qu'il est encore largement utilisé aujourd'hui.

1.4 Routage par information d'état de lien

Contrairement à un algorithme à vecteur de distance, la distance pour atteindre une destination n'est pas calculée au fur et à mesure en sommant le coût estimé par le prochain saut et le coût pour atteindre ce prochain routeur.
Dans ce type d'algorithme, chaque routeur tient à jour une base de données décrivant la topologie entière du réseau, c'est à dire l'ensemble des routeurs, et leur interconnexion.
Pour calculer la distance qui le sépare d'une destination, chaque routeur construit un arbre dont il est la racine, et suit au fur et à mesure toutes les ramifications du réseau tant qu'il n'a pas atteint la destination finale.
Le calcul de cet arbre permet de connaître le chemin complet (c'est à dire tous les routeurs que le paquet devra traverser), cependant seule l'adresse du prochain saut est conservée par le routeur puisque de son point de vue, c'est la seule information utile.
Lorsqu'un lien change d'état, le routeur qui le détecte transmet cette information à tous ses voisins par un mécanisme d'inondation. Chaque routeur recevant cette information met à jour sa base de donnée, et s'il s'agit d'une information nouvelle (en d'autres termes, s'il n'a pas déjà reçu cette information), il réémet le message d'information à tous ses voisins. Ce mécanisme permet à tous les routeurs d'être informé rapidement de toute modification, tout en assurant que le message soit détruit dès que tous l'ont reçu.

Le principal problème de cet algorithme est le coût, en termes de capacité de calcul et de mémoire, demandé par l'élaboration de l'arbre. En effet, à chaque changement de topologie, chaque routeur doit à nouveau dérouler le même algorithme, et calculer le plus court chemin pour atteindre chaque destination présente dans sa base de données.
De plus, tout ce calcul paraît fastidieux quand on sait que seule l'adresse du prochain saut est conservée.
La capacité de calcul requise limite dont les dimensions des réseaux fonctionnant avec ce type d'algorithme.

1.5 Le protocole OSPF

Le protocole OSPF (Open Shortest Path First) introduit des notions de domaine et de zone dans le but de limiter la charge de calcul de chaque routeur.
C'est un protocole de routage intra-domaine (IGP - Interior Gateway Protocol), et il ne diffuse les informations qu'aux routeurs appartenant à un même système autonome (AS - Autonomous System).
Un système autonome est divisé en zones (Area) permettant un routage hiérarchique, chaque routeur n'ayant connaissance que des routeurs de sa propre zone et de la façon d'atteindre la zone centrale (zone 0).

OSPF utilise l'algorithme SPF (Shortest Path First), ou algorithme de Dijkstra pour calculer l'arbre et la meilleure route pour chaque destination.

Le protocole Hello permet à chaque routeur d'échanger des informations concernant l'état de leurs liens, et de vérifier que les liaisons sont opérationnelles.

Deux mécanismes sont utilisés pour détecter les changements d'état de lien :

• Les changements d'état d'interface. Ces changements sont détectés localement par le système d'exploitation du routeur.
  
• L'expiration du temporisateur pour un paquet Hello, indiquant qu'un voisin est inactif.

La détection d'un changement de topologie est suivie par l'inondation, sur toutes les interfaces, d'un paquet indiquant cette information. Chaque routeur met à jour sa base de donnée et recalcule le plus court chemin pour chaque destination.

Certaines caractéristiques d'OSPF lui permettent de prendre en compte la QOS :

• Il peut calculer une route différente pour chaque type de service.
  
• Il sait répartir le trafic sur des liaisons qui ont le même coût.
  
• Il permet de combiner plusieurs critères pour calculer une même route.

Juin 2003