Aller au contenu
Encyclopédie informatique Édition 2026

Le routage et les routeurs

Partie 2 sur 3

Niveau de lecture :

4Routage statique et routage dynamique

Le fonctionnement d’un routeur dépend de la façon dont sa table de routage est construite :

  • si la table est saisie manuellement par l’administrateur, on parle de routage statique. C’est simple, prévisible et sans risque d’erreur de calcul, donc tout à fait viable pour de petits réseaux, ou pour les routes qui ne changent jamais, comme la route par défaut d’une box. Mais l’administrateur doit mettre la table à jour lui-même à chaque changement, et si un lien tombe en panne, le routeur continue d’y envoyer les paquets ;
  • si le routeur construit lui-même sa table en fonction des informations qu’il échange avec ses voisins, par l’intermédiaire de protocoles de routage, on parle de routage dynamique. Le protocole tient la table à jour automatiquement, pour qu’elle contienne à tout moment le meilleur chemin disponible, et contourne les pannes en quelques secondes.

Les protocoles de routage se répartissent en deux grandes familles d’algorithmes :

  • les protocoles à vecteur de distance (en anglais distance vector) : chaque routeur envoie régulièrement à ses voisins la liste des réseaux qu’il sait joindre et leur « distance », c’est-à-dire leur coût, en général le nombre de sauts. Chaque routeur ne connaît du réseau que ce que lui en disent ses voisins, comme un voyageur qui suivrait des panneaux indicateurs ;
  • les protocoles à état des liens (en anglais link state) : chaque routeur décrit à tous les autres ses propres liens et leur état. Chacun peut alors dresser une carte complète du réseau et y calculer lui-même les plus courts chemins vers toutes les destinations, à l’aide de l’algorithme de Dijkstra (section 5.3), comme un voyageur qui consulterait une carte routière.

5Les protocoles de routage interne

Internet est un ensemble de réseaux connectés, et tous les routeurs ne font pas le même travail. On distingue parfois des routeurs « noyaux », « externes » et « internes ». Cette description datait de l’ARPANET des années 1980, où un petit groupe de routeurs centraux, le « noyau », reliait tous les autres. Aujourd’hui, on raisonne en systèmes autonomes (en anglais Autonomous Systems, AS) : un système autonome est un ensemble de réseaux géré par une même organisation, qui choisit librement sa façon de router à l’intérieur. On distingue donc les protocoles qui fonctionnent à l’intérieur d’un système autonome, appelés IGP (Interior Gateway Protocols), et celui qui relie les systèmes autonomes entre eux, BGP (section 6).

5.1RIP

RIP signifie Routing Information Protocol, « protocole d’information de routage ». C’est un protocole à vecteur de distance, normalisé en 1988 : chaque routeur communique aux routeurs voisins la distance, en nombre de sauts, qui le sépare de chaque réseau connu. Lorsqu’un routeur reçoit un de ces messages, il augmente la distance de 1, retient pour chaque réseau le voisin qui en est le plus proche, et communique à son tour ses propres distances à ses voisins, toutes les 30 secondes. Les routeurs conservent ainsi, pour chaque réseau, le routeur suivant qui minimise le nombre de sauts.

RIP est simple, mais il a de sérieuses limites. Comme on le note souvent, il ne prend en compte que le nombre de sauts, sans considérer le débit des liaisons : il préfère deux sauts sur des liaisons lentes à trois sauts sur de la fibre. Il limite la taille d’un réseau à 15 sauts, la valeur 16 signifiant « injoignable ». Et il converge lentement : après une panne, les routeurs peuvent se renvoyer pendant de longues minutes une route disparue, en augmentant sa distance pas à pas, c’est le problème du comptage à l’infini (exercice 3). RIP n’est plus guère utilisé que dans de petits réseaux, et pour l’enseignement.

5.2OSPF et IS-IS

OSPF (Open Shortest Path First, « le plus court chemin d’abord, ouvert ») est un protocole à état des liens, normalisé en 1989 ; on l’appelle parfois par erreur protocole route-link au lieu de link state. Contrairement à RIP, il n’envoie pas aux routeurs voisins des distances, mais l’état et le coût des liaisons de chaque routeur, le coût reflétant en général le débit. Chaque routeur peut ainsi dresser une carte de l’état du réseau et choisir à tout moment la route la plus appropriée. Les routeurs n’échangent des informations que lorsque quelque chose change, et non toutes les 30 secondes : le trafic de contrôle est bien plus faible qu’avec RIP, et une panne est contournée en une seconde ou moins. Pour les grands réseaux, OSPF découpe le système autonome en zones, pour que chaque routeur n’ait à connaître en détail que la sienne.

On a longtemps vu OSPF « commencer à remplacer » RIP : c’est chose faite depuis longtemps, OSPF étant le protocole interne le plus répandu dans les entreprises. Les grands opérateurs utilisent souvent un protocole cousin, IS-IS (Intermediate System to Intermediate System), venu des normes de l’ISO (l’Organisation internationale de normalisation), qui fonctionne sur le même principe.

5.3L’algorithme de DijkstraApprofondir

Pour calculer ses routes, chaque routeur OSPF applique à sa carte du réseau l’algorithme imaginé en 1956 par l’informaticien néerlandais Edsger Dijkstra. Le principe : partir de soi-même, à distance 0, et étendre pas à pas l’ensemble des nœuds dont on connaît la distance minimale définitive. À chaque étape, on choisit, parmi les nœuds pas encore traités, celui dont la distance provisoire est la plus faible ; sa distance devient définitive ; puis on met à jour les distances provisoires de ses voisins, si le passage par lui les améliore. Quand tous les nœuds sont traités, on obtient l’arbre des plus courts chemins, dont on déduit pour chaque destination le premier saut à emprunter (figure 2 et exercice 4).

2 5 1 5 2 1 3 6 A B C D E F Chiffres : coût de chaque lien. Traits épais : l’arbre des plus courts chemins calculé par le routeur A (exercice 4).
Figure 2. Un réseau et l’arbre des plus courts chemins calculé par le routeur A. Le chemin le plus court vers F ne passe pas par le lien direct B-D, mais par C, E et D.

Les protocoles à vecteur de distance, eux, appliquent de façon répartie un autre algorithme classique, celui de Bellman et Ford : chaque routeur améliore ses distances à partir de celles de ses voisins, sans jamais avoir de vue d’ensemble.

Pour s’exercer

Exercice 3 : RIP et le comptage à l’infini

Trois routeurs sont en ligne : A — B — C, et le réseau N est relié à C. Avec RIP, quelles distances vers N connaissent A et B ? Le lien entre C et N tombe en panne ; B annonce encore sa distance à C avant d’apprendre la panne. Que se passe-t-il ?

Voir la réponse

C est à distance 1 de N (le réseau lui est relié), B à distance 2, A à distance 3. Après la panne, C ne peut plus joindre N ; mais s’il reçoit de B l’annonce « N à distance 2 », il croit pouvoir passer par B, et s’inscrit à distance 3. B, recevant cela de C, passe à 4 ; C passe à 5 ; et ainsi de suite, chaque échange augmentant la distance de 1, pendant que les paquets pour N tournent entre B et C. La progression ne s’arrête qu’à 16, la valeur « injoignable » de RIP : à raison d’un échange toutes les 30 secondes, cela peut prendre plusieurs minutes. Des astuces comme l’« horizon partagé », qui interdit de réannoncer une route au voisin qui l’a fournie, réduisent le problème sans le supprimer.

Exercice 4 : appliquer l’algorithme de Dijkstra

Sur le réseau de la figure 2, calculez depuis A la distance minimale vers chaque routeur, puis le premier saut que A doit utiliser pour joindre F.

Voir la réponse

Départ : A = 0. Voisins de A : B = 2, C = 5. On fixe B (2) ; par B, C passe à 2 + 1 = 3 et D vaut 2 + 5 = 7. On fixe C (3) ; par C, E vaut 3 + 2 = 5. On fixe E (5) ; par E, D passe à 5 + 1 = 6 et F vaut 5 + 6 = 11. On fixe D (6) ; par D, F passe à 6 + 3 = 9. On fixe F (9). Distances finales : B 2, C 3, E 5, D 6, F 9. Le plus court chemin vers F est A → B → C → E → D → F : le premier saut est B. Le lien direct B-D (coût 5) n’est pas utilisé, car passer par C et E ne coûte que 4.

Exercice 5 : la durée de vie et traceroute

Un ordinateur envoie un paquet avec une durée de vie (TTL) de 64. Il traverse 13 routeurs avant d’atteindre le serveur. Quelle est la durée de vie du paquet à l’arrivée ? Comment la commande traceroute (ou tracert sous Windows) exploite-t-elle ce mécanisme ?

Voir la réponse

Chaque routeur diminue la durée de vie de 1 : le paquet arrive avec 64 − 13 = 51. La commande traceroute envoie d’abord des paquets de durée de vie 1 : le premier routeur les détruit et renvoie un message d’erreur ICMP « durée de vie expirée », qui révèle son adresse. Elle recommence avec 2, puis 3, et ainsi de suite : chaque routeur du chemin se dévoile à son tour, avec le temps d’aller-retour mesuré jusqu’à lui (voir ICMP et les outils de diagnostic).