Routage : Dijkstra, Bellman-Ford, OSPF et BGP
Le réseau comme graphe pondéré, l'algorithme de Dijkstra avec démonstration de correction, OSPF, l'équation de Bellman-Ford et les vecteurs de distance, le comptage à l'infini, systèmes autonomes et BGP, RPKI.
https://www.electronics-engineering.com/fr/routage-dijkstra-bellman-ford-ospf-bgp/
Un routeur doit savoir, pour chaque destination, à quel voisin passer un paquet. Personne n’écrit les tables à la main : les routeurs les calculent eux-mêmes, en échangeant des informations par des protocoles de routage. Derrière eux, il y a deux algorithmes classiques sur les graphes. Dans cette leçon, nous regardons l’algorithme de Dijkstra avec la démonstration de sa correction, les protocoles à état de liens comme OSPF, l’algorithme de Bellman-Ford et les protocoles à vecteurs de distance avec le problème du comptage à l’infini, et BGP, qui tient ensemble les réseaux d’Internet.
Le réseau comme graphe
Le réseau se représente comme un graphe : les routeurs sont les nœuds, les liaisons les arêtes, chacune avec un coût positif choisi par l’administrateur (souvent inversement proportionnel au débit de la liaison). Le meilleur chemin entre deux nœuds est celui de coût total minimal.
L’algorithme de Dijkstra
Dans les protocoles à état de liens, chaque routeur diffuse à tous les autres la liste de ses voisins et de leurs coûts. À la fin, chaque routeur connaît tout le graphe et calcule lui-même les plus courts chemins vers toutes les destinations avec l’algorithme de Dijkstra (1959) :
- le nœud source a une distance 0, tous les autres une distance infinie ; aucun nœud n’est « définitif » ;
- parmi les nœuds non définitifs, on choisit celui de distance provisoire minimale et on le rend définitif ;
- pour chacun de ses voisins
, on vérifie si passer par lui raccourcit le trajet : si
, on met à jour
et l’on note que le prédécesseur de
est
; - on revient à l’étape 2 jusqu’à ce que tous les nœuds soient définitifs.

Théorème. Si tous les coûts sont non négatifs, quand un nœud est rendu définitif, sa distance provisoire est la plus courte distance depuis la source.
Démonstration. Par l’absurde, soit
le premier nœud rendu définitif avec une distance
supérieure à la vraie plus courte distance
. On considère un plus court chemin de la source à
. Il part d’un nœud définitif (la source) et finit en
, pas encore définitif : le long du chemin il y a donc un premier nœud non définitif
, précédé d’un nœud définitif
. Quand
a été rendu définitif, sa distance était correcte (
est la première erreur), et l’étape 3 a fixé
, c’est-à-dire
. Comme les coûts sont non négatifs,
,
se trouvant sur un plus court chemin vers
. Donc
: l’algorithme aurait dû choisir
avant
, contrairement à l’hypothèse. ∎
Avec des coûts négatifs, l’argument échoue, mais dans les réseaux les coûts sont toujours positifs. Les prédécesseurs forment l’arbre des plus courts chemins : le routeur en tire, pour chaque destination, le premier saut à utiliser. OSPF (Open Shortest Path First), le protocole à état de liens le plus répandu dans les réseaux d’entreprise et d’opérateur, fait exactement cela, et recalcule l’arbre en quelques millisecondes quand une liaison change d’état.
Bellman-Ford et vecteurs de distance
L’alternative n’exige pas de connaître tout le graphe. Chaque routeur
ne connaît que les coûts vers ses voisins et les vecteurs de distance que les voisins lui envoient périodiquement, et applique l’équation de Bellman-Ford :
![]()
c’est-à-dire : ma distance à
est la meilleure de « coût pour atteindre le voisin plus la distance que le voisin déclare ». En répétant les échanges, les estimations convergent vers les vraies distances. C’est le principe de RIP, l’un des plus anciens protocoles, simple mais lent.
Comptage à l’infini. Les mauvaises nouvelles voyagent mal. Prenons trois routeurs en ligne, A, B et C, avec des coûts de 1. A est à une distance 2 de C par B. Si la liaison B-C tombe, B cherche une alternative et trouve que A déclare une distance 2 vers C : il pense alors pouvoir passer par A avec un coût 3, sans savoir que le chemin de A passe par B lui-même. A reçoit le nouveau vecteur de B et relève sa propre estimation à 4, B à 5, et ainsi de suite : les distances croissent d’un à chaque échange, tandis que les paquets pour C rebondissent entre A et B. RIP limite les dégâts en fixant l’infini à 16 sauts ; des techniques comme l’horizon partagé avec retour empoisonné (A déclare à B une distance infinie vers les destinations qu’il atteint par B) corrigent les cas simples mais pas tous.
BGP et Internet
Internet est fait d’environ 75 000 systèmes autonomes (AS) : des réseaux d’opérateurs, d’universités, d’entreprises, chacun avec sa propre politique. À l’intérieur d’un AS, on utilise OSPF ou un protocole semblable ; entre AS différents, on utilise BGP (Border Gateway Protocol). BGP est un protocole à vecteur de chemins : une annonce ne porte pas seulement une distance mais la liste des AS à traverser pour atteindre un préfixe. Cela élimine les boucles (un AS écarte les annonces qui le contiennent déjà) et permet des politiques : un opérateur peut préférer un chemin plus long mais moins cher, ou refuser d’acheminer du trafic entre deux concurrents.
BGP repose sur la confiance dans les annonces, et là réside sa faiblesse : un AS qui annonce, par erreur ou par malveillance, un préfixe qui n’est pas le sien peut attirer du trafic destiné à quelqu’un d’autre. De tels épisodes ont rendu des services mondiaux injoignables pendant des heures. La contre-mesure en cours de déploiement est la RPKI, qui signe cryptographiquement quels AS sont autorisés à annoncer quels préfixes.






Ciao, sono l'autore di «Instradamento: Dijkstra, Bellman-Ford, OSPF e BGP». Domande, dubbi, segnalazioni di errori o richieste di approfondimento sono benvenuti: scriveteli qui sotto e vi rispondo io. Potete anche votare la pagina con le stelle all'inizio dell'articolo.Hi, I am the author of “Routing: Dijkstra, Bellman-Ford, OSPF and BGP”. Questions, doubts, error reports and requests for more detail are all welcome: write them below and I will answer. You can also rate the page with the stars at the top of the article.