Document Actions
OSPF 4. L'algorithme du chemin le plus court
by
francois
—
last modified
2006-10-11 20:40
François Goffinet
L'algorithme du chemin le plus court est celui qui est utilisé par OSPF pour déterminer le meilleur chemin vers un réseau de destination.
Avec cet algorithme, le meilleur chemin est celui qui a le coût le
moins cher, le plus faible. Il a été découvert par E. W. Dijkstra
(1930-2002), un mathématicien néerlandais (http://www.cs.utexas.edu/users/EWD/)
. Il a été publié en 1959 et son utilisation dépasse largement le monde des réseaux.
L'algorithme considère un réseau de noeuds connectés par des liens point à point. Chaque lien a un coût. Chaque noeud a un nom et possède une base de donnée complète de tous les liens et a donc ainsi une connaissance complète de la topologie physique. Tous les routeurs de la base de donnée d'état de lien sont identiques.
L'algorithme du chemin le plus court va alors calculer une topologie sans boucle en utilisant le noeud en question comme point de départ et en examinant à son tour les informations des ses noeuds contigus.
On trouvera plus d'information sur l'algorithme de Dijkstra sous ce lien http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra.
L'algorithme considère un réseau de noeuds connectés par des liens point à point. Chaque lien a un coût. Chaque noeud a un nom et possède une base de donnée complète de tous les liens et a donc ainsi une connaissance complète de la topologie physique. Tous les routeurs de la base de donnée d'état de lien sont identiques.
L'algorithme du chemin le plus court va alors calculer une topologie sans boucle en utilisant le noeud en question comme point de départ et en examinant à son tour les informations des ses noeuds contigus.
On trouvera plus d'information sur l'algorithme de Dijkstra sous ce lien http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra.