Cours — Calixte

Dijkstra pas à pas — Tableaux de calcul 5 routeurs

Properties1
tagscours, reseaux, ospf, dijkstra, routage, spf, exercice

8 min de lecture

Dijkstra pas à pas — Tableaux de calcul (5 routeurs)

Contexte

Matière : _Reseaux · Type : exercice corrigé, méthode du tableau Fiche associée : Dijkstra — Tables de routage OSPF 5 routeurs (topologie, matrice des distances, explorer interactif) Cours : 2026-09-11 — OSPF et algorithme à état de lien

🗺️ Rappel de la topologie

Coûts des interfaces sortantes par routeur :

RouteurRéseaux attachés (coût de l’interface)
R1.1 (2) · .2 (20) · .3 (5) · .4 (20)
R2.2 (20) · .5 (2) · .9 (10)
R3.3 (5) · .6 (2) · .7 (10)
R4.4 (20) · .7 (10) · .8 (2) · .10 (10)
R5.9 (10) · .10 (10) · .11 (2)

.n désigne le réseau 10.n.0.0/16.

🧮 Méthode du tableau

Comment se lit un tableau

  • Colonnes : les 11 réseaux.
  • Lignes : la première est le routeur de départ, chaque ligne suivante porte le nom du réseau qu’on vient de retenir.
  • Case coût.Rx : meilleur coût connu pour joindre ce réseau, et Rx le routeur qui émet sur ce réseau (le dernier saut).
  • **[coût.Rx]** : le minimum de la ligne, c’est le réseau retenu à cette étape. Il devient – sur toutes les lignes suivantes.
  • ∞ : réseau pas encore découvert.

À chaque étape

  1. Prendre le réseau retenu (coût c).
  2. Regarder les routeurs attachés à ce réseau. Pour chaque routeur pas encore atteint : il est atteint au coût c.
  3. Pour chacun de ses autres réseaux : c + coût de l'interface.
    • Plus petit que la valeur actuelle → on remplace (✓).
    • Plus grand → on garde l’ancienne (✗).
    • Égal → on garde les deux émetteurs : ECMP.
  4. Recopier la ligne, encadrer le nouveau minimum. En cas d’égalité, prendre le plus petit numéro de réseau.

Erreur classique

Retenir une valeur qui n’est pas le minimum de la ligne. Exemple sur R2 : retenir .8 = 22 alors que .2 = 20 est encore en lice. Le résultat final reste souvent juste, mais le déroulé est faux et c’est ce qui est noté.

R1

Retenu.1.2.3.4.5.6.7.8.9.10.11
R1[2.R1]20.R15.R120.R1∞∞∞∞∞∞∞
.1–20.R1[5.R1]20.R1∞∞∞∞∞∞∞
.3–20.R1–20.R1∞[7.R3]15.R3∞∞∞∞
.6–20.R1–20.R1∞–[15.R3]∞∞∞∞
.7–20.R1–20.R1∞––[17.R4]∞25.R4∞
.8–[20.R1]–20.R1∞–––∞25.R4∞
.2–––[20.R1]22.R2–––30.R225.R4∞
.4––––[22.R2]–––30.R225.R4∞
.5––––––––30.R2[25.R4]∞
.10––––––––30.R2–[27.R5]
.11––––––––[30.R2]––

Table de routage R1

RéseauCoûtÉmis parNext-hop
10.1.0.02R1DC
10.3.0.05R1DC
10.6.0.07R3R3
10.7.0.015R3R3
10.8.0.017R4R3
10.2.0.020R1DC
10.4.0.020R1DC
10.5.0.022R2R2
10.10.0.025R4R3
10.11.0.027R5R3
10.9.0.030R2R2

R2

Retenu.1.2.3.4.5.6.7.8.9.10.11
R2∞20.R2∞∞[2.R2]∞∞∞10.R2∞∞
.5∞20.R2∞∞–∞∞∞[10.R2]∞∞
.9∞20.R2∞∞–∞∞∞–20.R5[12.R5]
.11∞[20.R2]∞∞–∞∞∞–20.R5–
.222.R1–25.R140.R1–∞∞∞–[20.R5]–
.10[22.R1]–25.R140.R1/R4–∞30.R422.R4–––
.1––25.R140.R1/R4–∞30.R4[22.R4]–––
.8––[25.R1]40.R1/R4–∞30.R4––––
.3–––40.R1/R4–[27.R3]30.R4––––
.6–––40.R1/R4––[30.R4]––––
.7–––[40.R1/R4]–––––––

Table de routage R2

RéseauCoûtÉmis parNext-hop
10.5.0.02R2DC
10.9.0.010R2DC
10.11.0.012R5R5
10.2.0.020R2DC
10.10.0.020R5R5
10.1.0.022R1R1
10.8.0.022R4R5
10.3.0.025R1R1
10.6.0.027R3R1
10.7.0.030R4R5
10.4.0.040R1/R4R1 / R5

R3

Retenu.1.2.3.4.5.6.7.8.9.10.11
R3∞∞5.R3∞∞[2.R3]10.R3∞∞∞∞
.6∞∞[5.R3]∞∞–10.R3∞∞∞∞
.3[7.R1]25.R1–25.R1∞–10.R3∞∞∞∞
.1–25.R1–25.R1∞–[10.R3]∞∞∞∞
.7–25.R1–25.R1∞––[12.R4]∞20.R4∞
.8–25.R1–25.R1∞–––∞[20.R4]∞
.10–25.R1–25.R1∞–––30.R5–[22.R5]
.11–[25.R1]–25.R1∞–––30.R5––
.2–––[25.R1]27.R2–––30.R5––
.4––––[27.R2]–––30.R5––
.5––––––––[30.R5]––

Table de routage R3

RéseauCoûtÉmis parNext-hop
10.6.0.02R3DC
10.3.0.05R3DC
10.1.0.07R1R1
10.7.0.010R3DC
10.8.0.012R4R4
10.10.0.020R4R4
10.11.0.022R5R4
10.2.0.025R1R1
10.4.0.025R1R1
10.5.0.027R2R1
10.9.0.030R5R4

R4

Retenu.1.2.3.4.5.6.7.8.9.10.11
R4∞∞∞20.R4∞∞10.R4[2.R4]∞10.R4∞
.8∞∞∞20.R4∞∞[10.R4]–∞10.R4∞
.7∞∞15.R320.R4∞12.R3––∞[10.R4]∞
.10∞∞15.R320.R4∞[12.R3]––20.R5–12.R5
.6∞∞15.R320.R4∞–––20.R5–[12.R5]
.11∞∞[15.R3]20.R4∞–––20.R5––
.3[17.R1]35.R1–20.R4∞–––20.R5––
.1–35.R1–[20.R4]∞–––20.R5––
.4–35.R1––∞–––[20.R5]––
.9–35.R1––[22.R2]––––––
.5–[35.R1]–––––––––

Table de routage R4

RéseauCoûtÉmis parNext-hop
10.8.0.02R4DC
10.7.0.010R4DC
10.10.0.010R4DC
10.6.0.012R3R3
10.11.0.012R5R5
10.3.0.015R3R3
10.1.0.017R1R3
10.4.0.020R4DC
10.9.0.020R5R5
10.5.0.022R2R5
10.2.0.035R1R3

R5

Retenu.1.2.3.4.5.6.7.8.9.10.11
R5∞∞∞∞∞∞∞∞10.R510.R5[2.R5]
.11∞∞∞∞∞∞∞∞[10.R5]10.R5–
.9∞30.R2∞∞12.R2∞∞∞–[10.R5]–
.10∞30.R2∞30.R4[12.R2]∞20.R412.R4–––
.5∞30.R2∞30.R4–∞20.R4[12.R4]–––
.8∞30.R2∞30.R4–∞[20.R4]––––
.7∞30.R225.R330.R4–[22.R3]–––––
.6∞30.R2[25.R3]30.R4–––––––
.3[27.R1]30.R2–30.R4–––––––
.1–[30.R2]–30.R4–––––––
.2–––[30.R4]–––––––

Table de routage R5

RéseauCoûtÉmis parNext-hop
10.11.0.02R5DC
10.9.0.010R5DC
10.10.0.010R5DC
10.5.0.012R2R2
10.8.0.012R4R4
10.7.0.020R4R4
10.6.0.022R3R4
10.3.0.025R3R4
10.1.0.027R1R4
10.2.0.030R2R2
10.4.0.030R4R4

🎯 Points à retenir

Ce que les tableaux montrent

  • Le lien direct n’est pas toujours le meilleur : depuis R1, .8 passe par R3 (17) et pas par le lien direct R1–R4 (20 + 2 = 22).
  • ECMP sur R2 vers .4 : par R1 (20 + 20) et par R5→R4 (10 + 10 + 20), les deux font 40. OSPF installe les deux routes.
  • Un réseau de transit se paie deux fois : une fois pour y arriver, une fois pour l’interface qui en sort. R1 vers .9 = 20 (jusqu’à R2) + 10 = 30.
  • Les réseaux LAN ne font découvrir aucun routeur : leur ligne est une simple recopie (« aucun nouveau routeur »).

🔗 Voir aussi

Vue Graphique

Liens retour