Le routage sur Internet : RIP et OSPF

Présentation

Internet est par définition même l'interconnexion de multiples réseaux. Lorsque l'on utilise un navigateur web pour accéder à un contenu, celui ci peut être hébergé de l'autre côté de la planète. Notre requête va traverser un certain nombre d'équipements pour au final arriver sur le serveur que nous souhaitons atteindre. C'est le rôle de la couche IP de gérer ce voyage de données. Ce processus est appelé le routage des données.

Quelques définitions

• Un routeur est une machine qui possède au moins deux connexions à des réseaux distincts, et qui permet de faire transiter des paquets d'un réseau vers un autre.
• On distingue parfois les routeurs d'accès qui sont reliés aux clients et aux serveurs d'un réseau local et les routeurs internes qui sont connectés entre eux et font circuler des paquets dans le cœur du réseau.
• Les équipements possédent une table de routage, qui est une correspondance entre les réseaux de destination et les équipements et interface par lesquels faire transiter les datagrammes IP. Sur un client, la table de routage est en général très simple : elle se limite à indiquer le réseau local auquel on accède par la carte réseau, et la passerelle par défaut qui permet d'accéder à tous les autres réseaux. sur un routeur, la table de routage pourra être bien plus complexe.

L'algorithme de routage

Mais de quelle façon un paquet qui part de notre machine peut il trouver son chemin jusqu'à l'autre bout du monde ? Comment cette information est elle traitée ? Diffusée ? C'est le rôle du routage. Déterminer le chemin. Du point de vue de la machine, elle se sert de la table de routage en appliquant un algorithme assez simple :

• Si la destination est sur le réseau local, on envoie le datagramme sur l'interface réseau qui convient
• Si on a une route vers la destination dans la table de routage, on envoie le datagramme vers le routeur correspondant (qui est donc nécessairement un voisin)
• Sinon, on envoie le datagramme sur le routeur par défaut.
• S'il n'y a pas de route enregistré et pas de routeur par défaut, on retourne une erreur à l'émetteur du datagramme.

La question qui reste en suspend est donc la suivante : comment sont fabriquées ces tables de routage ?

Les protocoles de routage

Routage statique

Commençons par le cas le plus simple. Lorsque l'on est sur une machine implantée dans un réseau local, ou sur un routeur de sortie où il n'y a qu'une ou deux interfaces réseau, et un routeur par défaut disponible, la table de routage est définie à partir des informations obtenues au moment de l'installation de la machine. La table de routage est fixée initialement. On parle alors de routage statique.

Le routage statique est pratique pour des petits réseaux qui ne contiennent que quelques routeurs, mais il devient vite inutilisable dans un réseau de grande taille, géré par plusieurs acteurs et dont la topologie peut changer au fur et à mesure. En effet, un routage statique demande, lorsque l'on ajoute un routeur ou lorsqu'un routeur tombe en panne, à ce qu'une intervention humaine ait lieu pour modifier les tables de routage. Cela n'est pas gérable à grande échelle.

On délègue donc au retour le soin de construire eux même les tables de routage. En plus de se transmettre des paquets, les routeurs vont échanger des informations sur les routes à leur disposition et l'état des connexions. L'échange de ces informations suit un certain nombre de règle que l'on appelle un protocole de routage. Il y en a aujourd'hui principalement deux types :

• Le routage dit "à vecteur de distance" avec le protocole RIP
• Le routage à "état de lien" avec le protocole OSPF

La vidéo de Claude CHAUDET suivante introduit bien cette notion de routage dynamique par opposition au routage statique en rappelant les fondamentaux sur le routage interne (c'est à dire entre les routeurs qui constituent le cœur d'internet).

Le protocole RIP

Le protocole RIP ( Routing Information Protocol ) date de la fin des années 1980. Il a été l'un des premiers protocoles utilisé pour configurer automatiquement les routeurs sur internet. Il repose sur un principe assez simple qui assure sa robustesse. Périodiquement,(toutes les 30 secondes le plus souvent), chaque routeur échange avec ses voisins la table de routage qu'il possède. Chaque routeur ne communique qu'avec son voisin, mais la table de routage se construit au fur et à mesure. Les routeurs ne vont pas chercher l'information : c'est l'information qui vient à eux et se "répand" au fur et à mesure.

Les tables de routages contiennent les informations suivantes :

• Le réseau de destination
• La passerelle pour y accédere
• La distance de ce réseau (qui est le nombre de sauts)

Lorsqu'un routeur reçoit de son voisin les tables de routage, il les analyse et applique l'algorithme suivant :

• si une destination transmise par le voisin est inconnue, alors elle est ajoutée à la table du routage en ajoutant 1 à la distance transmise par le voisin. C'est le voisin qui a transmis cette nouvelle route qui est indiqué comme passerelle (c'est vers lui que l'on enverra le paquet à destination de ce réseau).
• Si une destination transmise par le voisin est déjà connue, on distingue pmusieurs cas. :
  • Si le passage par cette route est plus avantageux, la table de routage est mise à jour.
  • Si le passage par cette route est du même coût ou plus élevé sans provenir du routeur actuel, il est ignoré
  • Si le passage par cette route est d'un coût plus élevé et provient du routeur actuellement dans la table de routage, c'est qu'il y a eu une modification sur la structure du réseau et la table de routage doit être mise à jour.

La mise en œuvre de ce protocole est très bien décrite dans ce cours de Claude CHAUDET (Institut Mines Télécom)

Le protocole RIP fonctionne bien, mais il présente un certain nombre d'inconvénients. Outre le caractère "verbeux" de ce protocole où les informations doivent être transmises et analysées toutes les 30 secondes, il n'y a aucune garantie sur la qualité de service. En effet, seul le nombre de sauts est analysé et il n'y a aucune prise en compte de la bande passante des différentes liaisons. Par ailleurs, dans le protocole RIP, on limite le nombre de sauts à 15, pour éviter les boucles et les parcours trop longs. Cela limite la taille du réseau qui peut être géré de cette façon.

Le protocole OSPF

Pour pallier ces insuffisance, le protocole OSPF (Open Shortest Path First) a été élaboré. Le protocole RIP est dit à vecteur de distance. Le protocole OSPF va prendre en compte la qualité des liaisons et on parle de protocole à état de lien.

Le protocole OSPF propose une approche tout à fait différente : au lieu de s'intéresser au nombre de sauts, on va chercher à optimiser le débit des liaisons empruntées. Pour cela, chaque routeur va devoir connaître l'intégralité du réseau avec le débit associé à chaque lien afin d'appliquer un algorithme de recherche de chemin optimal.

On peut faire un parallèle entre le fonctionnement d'OSPF et celui de nos logiciels de guidage par GPS. En effet, dans ce type de logiciels :

• l'ensemble de la carte de France et de ses routes est connue du logiciel
• le type de chaque route est renseigné ainsi que la vitesse autorisée sur la route
• le calcul d'itinéraire va permettre le calcul d'un chemin permettant par exemple d'emprunter les routes sur lesquelles la vitesse est la plus importante (temps le plus court).

Cette vidéo de Claude CHAUDET (Institut Mines-Télécom) expose le principe du routage à état de lien, comme OSPF.

Nous n'entrerons pas dans le détail technique de l'algorithme de Djikstra lié au protocole OSPF. Ce qu'il faut retenir, c'est que l'on affecte un "coût" ou un poids à chaque liaison, inversement proportionnel au débit, et que le protocole va déterminer le chemin le moins couteux pour aller d'un point à un autre du réseau.

Le protocole BGP

Comme nous l'avons vu précedemment, pour des raisons différentes, les protocoles de routage RIP et OSPF qui ont été développé dans les années 80 au moment de la construction d'internet, ne permettent pas de gérer des réseaux qui contiendrait des dizaines de millier voire des millions de routeur. Mais au fur et à mesure que l'internet grandissait, une autre problématique a vu le jour avec une multiplication des acteurs et des opérateurs de réseau.

Les réseaux des grands opérateurs sont des zones autonomes de service. Au sein de ces zones, le routage est géré au moyen des protocoles RIP ou OSPF.

La liaison entre les différentes zones de service est gérée au moyen du protocole BGP ( Border Gateway Protocol ) qui prend en compte des caractéristiques physiques mais qui permet aussi de gérer différents types d'accords commerciaux. Il limite la taille des tables de routage, permet la décentralisation du routage sur internet, et il masque la topologie interne des Autonomous System. L'étude de ce protocole est en dehors du programme d'informatique du lycée.