Publié le 10 février 2026 06:47:00. Une nouvelle méthode pour optimiser les calculs de routage sur les réseaux, potentiellement plus rapide que l’algorithme de Dijkstra utilisé depuis des décennies, suscite l’intérêt des experts, bien que son impact réel sur les systèmes existants reste à évaluer.
- Un nouvel algorithme promet d’améliorer la recherche des chemins les plus courts dans les réseaux.
- Cette approche vise à dépasser les limites de l’algorithme de Dijkstra, une référence depuis 1959.
- L’implémentation pratique de cette avancée théorique dans les routeurs commerciaux n’est pas encore assurée.
Des chercheurs ont récemment présenté une nouvelle approche pour déterminer les itinéraires les plus efficaces dans les réseaux informatiques. Cette méthode, détaillée dans une publication scientifique, ambitionne de surpasser l’algorithme de Dijkstra, une pierre angulaire de la théorie du routage depuis sa création en 1959 par Edsger W. Dijkstra. L’algorithme de Dijkstra est à la base de nombreux protocoles de routage, notamment OSPF (Open Shortest Path First), l’un des protocoles de routage à état de liens les plus utilisés.
Les spécifications d’OSPF, particulièrement détaillées, recommandent explicitement l’utilisation de l’algorithme de Dijkstra. Les implémentations actuelles, bien qu’ayant bénéficié d’améliorations progressives au fil des ans, restent fondamentalement fidèles à cette approche. La nouvelle méthode proposée ne se contente pas d’une optimisation incrémentale, mais représente une rupture significative.
Selon les auteurs, l’algorithme de Dijkstra, nécessitant une opération de tri, est limité par la performance de cet algorithme de tri. La nouvelle approche, quant à elle, prétend « briser la barrière du tri », évitant ainsi ce goulot d’étranglement et offrant potentiellement de meilleures performances. La complexité temporelle de Dijkstra est de l’ordre de (n log n + m) pour un réseau de n nœuds (routeurs) et m liens. La nouvelle approche revendique une complexité de (m log2/3 n), ce qui pourrait être plus avantageux pour des réseaux de grande taille. Cependant, comme le soulignent les experts, l’importance de cette différence théorique dépend de l’échelle réelle des réseaux considérés.
« La question que je souhaite aborder ici est la suivante : est-ce important ? », s’interroge Larry Peterson, co-auteur de Réseaux informatiques : une approche systémique. Il rappelle que l’évolutivité est un objectif louable, mais que des solutions moins évolutives peuvent s’avérer suffisantes dans la pratique. Il cite l’exemple des commutateurs de paquets des années 1990, où une capacité de 16 ports s’est avérée largement suffisante, même si des conceptions plus évolutives étaient possibles.
Au-delà de la complexité algorithmique, d’autres facteurs influencent la performance des protocoles de routage. La rapidité de détection des pannes, par exemple, est cruciale. Des technologies comme BFD (Bidirectional Forwarding Detection), qui permet une détection rapide des pannes de liens indépendamment du protocole de routage, ont considérablement amélioré la convergence des réseaux. L’optimisation de l’ensemble du processus, de la détection des pannes à la mise à jour des tables de routage, est essentielle.
Un autre point soulevé est la simplicité et la lisibilité du code. Dijkstra lui-même soulignait dans une interview de 2001 :
« La publication est toujours lisible, elle est en fait plutôt sympa. L’une des raisons pour lesquelles il est si joli est que je l’ai conçu sans crayon ni papier. J’ai appris plus tard que l’un des avantages de concevoir sans crayon ni papier est que vous êtes presque obligé d’éviter toutes les complexités évitables. »
Edsger W. Dijkstra
En d’autres termes, privilégier la simplicité, comme le recommande le principe KISS (Keep It Simple, Stupid). Larry Peterson et Bruce Davie estiment qu’il serait plus judicieux de diriger un ingénieur vers la spécification OSPF que de lui demander de maîtriser une approche hybride Bellman-Ford/Dijkstra, même si celle-ci pouvait potentiellement réduire de quelques millisecondes le temps de calcul du chemin le plus court.
La nouvelle approche pourrait trouver des applications intéressantes dans des domaines tels que la cartographie à grande échelle, mais il est peu probable que l’algorithme de Dijkstra soit remplacé de sitôt dans les routeurs de production. L’algorithme hybride pourrait être idéal pour les grandes applications de cartographie. Mais je ne pense pas que l’algorithme de Dijkstra soit remplacé de si tôt dans les routeurs de production.
Larry Peterson et Bruce Davie sont les auteurs de Réseaux informatiques : une approche systémique et de la série de livres connexe Approche systémique. Leur contenu est open source et disponible gratuitement sur GitHub. Vous pouvez les retrouver sur Mastodon, leur newsletter ici et leurs anciens articles sur Le Registre ici.