Protocoles de routage RIP et OSPF

Introduction

Vous avez vu au cours précédent qu'un routeur consulte sa table de routage pour décider du prochain saut. Reste une question : d'où viennent les lignes de cette table ? Sur un petit réseau, l'administrateur peut les écrire à la main. Sur Internet, qui regroupe des centaines de milliers de routeurs, c'est impossible. Les routeurs dialoguent entre eux via un protocole de routage qui leur permet de découvrir le réseau et de calculer les meilleures routes. Le programme officiel ([TC03]) en retient deux représentants : RIP et OSPF. Ils incarnent deux philosophies très différentes, et le lien avec les algorithmes sur graphes que vous étudiez en parallèle (chapitre [TE]) y devient explicite.

Le réseau vu comme un graphe

Avant de comparer les protocoles, posez le bon modèle. Un réseau de routeurs se décrit comme un graphe :

• les sommets sont les routeurs ;
• les arêtes sont les liens directs entre routeurs ;
• chaque arête porte une valeur — soit 1 si l'on compte les sauts, soit un coût $c(u, v)$ qui modélise un délai ou une bande passante inverse.

Trouver la meilleure route entre deux routeurs revient à trouver un plus court chemin dans ce graphe. C'est exactement le problème que résolvent les algorithmes vus en algorithmique terminale.

RIP — Routing Information Protocol

RIP est le protocole historique, simple à concevoir, limité à l'échelle. Sa métrique est le nombre de sauts : chaque arête coûte $1$. C'est la logique du voyage en avion qu'on évalue au nombre d'escales : on prend la route avec le moins d'escales, sans considération de durée ou de tarif. Vite calculé, mais grossier — un vol direct de 12 heures « bat » un trajet à deux escales de 4 heures.

• Chaque routeur diffuse régulièrement à ses voisins directs un résumé de sa propre table : « pour le réseau $X$, je suis à $h$ sauts ».
• À la réception, chaque voisin met à jour sa table : « pour aller à $X$ par ce voisin, il faut $h + 1$ sauts ».
• La métrique est plafonnée à 15 — au-delà, le réseau est considéré comme inaccessible. RIP n'est donc utilisable que sur des réseaux modestes.

L'algorithme sous-jacent — chaque routeur ne connaît que ses voisins et échange des distances au fil du temps — est une variante distribuée d'un classique des algorithmes sur graphes, Bellman-Ford (mis à jour itérative des distances par relaxation locale). Vous n'avez pas à le connaître en détail au niveau Terminale, juste à retenir l'idée : chacun met à jour ses estimations à partir de celles de ses voisins.

OSPF — Open Shortest Path First

OSPF est plus moderne, conçu pour des réseaux de grande taille. Sa métrique est un coût numérique : chaque lien porte une valeur qui reflète sa qualité (typiquement inversement proportionnelle à la bande passante). Si RIP comptait les escales, OSPF compare le prix total des billets : chaque tronçon a un coût, et l'on cherche le trajet le moins cher dans son ensemble — quitte à passer par plus d'escales.

• Chaque routeur inonde le réseau (au sens : diffuse de proche en proche à tous ses voisins, qui répercutent à leurs voisins) d'un message décrivant ses propres liens et leurs coûts.
• Chaque routeur reconstruit ainsi une carte complète du réseau — le graphe pondéré entier.
• Il applique alors localement l'algorithme de Dijkstra pour calculer le plus court chemin vers chaque destination.

C'est le lien direct avec votre chapitre d'algorithmique : OSPF est une application industrielle de Dijkstra. Lisez le code et la preuve d'invariant de Dijkstra en [TE], vous tenez l'essentiel d'OSPF.

Un exemple de calcul OSPF

Considérez quatre routeurs $A, B, C, D$ et les coûts donnés :

Depuis $A$, les plus courts chemins calculés par Dijkstra sont :

La table de routage de $A$ retient ces chemins. À noter : la route directe $A \to C$ (coût $5$) est écartée au profit du détour $A \to B \to C$ (coût $3$). Une route plus longue en nombre de sauts peut être préférée si son coût total est moindre — c'est précisément ce que RIP ne sait pas faire.

RIP vs OSPF en un tableau

Pour aller plus loin

Les deux protocoles décrits sont des IGP (Interior Gateway Protocols) : ils opèrent à l'intérieur d'un même domaine administratif (un campus, une entreprise, un FAI). Entre opérateurs, c'est BGP qui prend le relais, sur une logique encore différente — hors programme NSI, mais bonne curiosité.