CHAPITRE 1
Algorithmes de routage

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 :

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

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 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 :

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

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 :

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 :

Introduction
CHAPITRE 2 - QRouting

Juin 2003