Dijkstra — Tables de routage OSPF (5 routeurs)

Contexte

Matière : _Reseaux · Type : exercice corrigé · Source : séance du 11/09 Cours associé : 2026-09-11 — OSPF et algorithme à état de lien (LSP, LSDB, les 3 étapes) Prérequis : 2026-09-04 — Routage et modèles OSI-TCP-IP (table de routage, notation /xx)

Explorer interactif — plus bas dans la page

La section Explorer interactif permet de cliquer chaque route pour voir son chemin s’allumer sur la topologie, avec le détail du calcul dist + interface. Les tables de cette fiche ont été vérifiées par deux implémentations indépendantes (Python + JS) — 55 lignes concordantes. Déroulé en tableau étape par étape : Dijkstra pas à pas — Tableaux de calcul 5 routeurs.

---

🗺️ Topologie

Liens de transit (WAN)

Réseau	Entre	Coût
10.2.0.0/16	R1 ↔ R2	20
10.3.0.0/16	R1 ↔ R3	5
10.4.0.0/16	R1 ↔ R4	20
10.7.0.0/16	R3 ↔ R4	10
10.9.0.0/16	R2 ↔ R5	10
10.10.0.0/16	R4 ↔ R5	10

Réseaux terminaux (LAN)

Réseau	Attaché à	Coût
10.1.0.0/16	R1 (Fa0/0)	2
10.5.0.0/16	R2	2
10.6.0.0/16	R3	2
10.8.0.0/16	R4	2
10.11.0.0/16	R5	2

---

🧮 La règle de calcul

Formule fondamentale

$\text{couˆt}(\text{reˊseau})=\text{dist}(\text{routeur}\to \text{voisin attacheˊ})+\text{couˆt de l’interface vers ce reˊseau}$

Le coût affiché sur le schéma est celui de l’interface sortante, pas celui du lien pris globalement. Un réseau de transit compte donc deux fois dans le total : une fois pour y arriver, une fois pour l’interface qui le dessert.

L'erreur classique

S’arrêter à la distance jusqu’au routeur sans ajouter le coût de l’interface. Exemple : R1 → 10.9.0.0 n’est pas 20 (= dist R1→R2) mais 30 (= 20 + interface R2 à 10).

---

📐 Matrice des distances routeur ↔ routeur

Résultat de Dijkstra appliqué depuis chaque nœud (distances symétriques ici).

	R1	R2	R3	R4	R5
R1	0	20	5	15	25
R2	20	0	25	20	10
R3	5	25	0	10	20
R4	15	20	10	0	10
R5	25	10	20	10	0

Les deux raccourcis contre-intuitifs

• R1 → R4 = 15 via R3 (5+10), pas 20 en direct. Le lien direct est battu par le détour.
• R1 → R5 = 25 via R3→R4 (5+10+10), pas 30 via R2 (20+10). Moins de sauts ≠ moins cher.
• R2 → R4 = 20 via R5 (10+10), pas 35 via R1→R3.

---

🌲 Déroulé Dijkstra depuis R1 (SPF tree)

Étape	Nœud retenu	File d’attente mise à jour
Init	R1 (0, —)	R2(20,R1) · R3(5,R1) · R4(20,R1)
1	R3 (5, R1)	R2(20,R1) · R4(15,R3) ← 5+10 < 20
2	R4 (15, R3)	R2(20,R1) · R5(25,R4) ← 15+10
3	R2 (20, R1)	R5(25,R4) — via R2 : 30 > 25, pas de MAJ
4	R5 (25, R4)	file vide → terminé

Arbre SPF résultant : R1 → R3 → R4 → R5 et R1 → R2

---

📋 Tables de routage

Légende : DC = directement connecté · Préd. = prédécesseur dans l’arbre SPF

R1

Réseau	Coût	Préd.	Next-hop
10.1.0.0	2	—	DC (Fa0/0)
10.3.0.0	5	—	DC (S0/0/1)
10.6.0.0	7	R3	R3
10.7.0.0	15	R3	R3
10.8.0.0	17	R4	R3
10.2.0.0	20	—	DC (S0/0/0)
10.4.0.0	20	—	DC (S0/1/0)
10.5.0.0	22	R2	R2
10.10.0.0	25	R4	R3
10.11.0.0	27	R5	R3
10.9.0.0	30	R2	R2

R2

Réseau	Coût	Préd.	Next-hop
10.5.0.0	2	—	DC
10.9.0.0	10	—	DC
10.11.0.0	12	R5	R5
10.2.0.0	20	—	DC
10.10.0.0	20	R5	R5
10.1.0.0	22	R1	R1
10.8.0.0	22	R4	R5
10.3.0.0	25	R1	R1
10.6.0.0	27	R3	R1
10.7.0.0	30	R4	R5
10.4.0.0	40	R1 / R4	R1 ou R5 (ECMP)

Load balancing sur 10.4.0.0

Via R5 : 10+10+20 = 40 · Via R1 : 20+20 = 40. Égalité parfaite → OSPF installe les deux routes (Equal-Cost Multi-Path).

R3

Réseau	Coût	Préd.	Next-hop
10.6.0.0	2	—	DC
10.3.0.0	5	—	DC
10.1.0.0	7	R1	R1
10.7.0.0	10	—	DC
10.8.0.0	12	R4	R4
10.10.0.0	20	R4	R4
10.11.0.0	22	R5	R4
10.2.0.0	25	R1	R1
10.4.0.0	25	R1	R1
10.5.0.0	27	R2	R1
10.9.0.0	30	R5	R4

R4

Réseau	Coût	Préd.	Next-hop
10.8.0.0	2	—	DC
10.7.0.0	10	—	DC
10.10.0.0	10	—	DC
10.6.0.0	12	R3	R3
10.11.0.0	12	R5	R5
10.3.0.0	15	R3	R3
10.1.0.0	17	R1	R3
10.4.0.0	20	—	DC
10.9.0.0	20	R5	R5
10.5.0.0	22	R2	R5
10.2.0.0	35	R1	R3

R5

Réseau	Coût	Préd.	Next-hop
10.11.0.0	2	—	DC
10.9.0.0	10	—	DC
10.10.0.0	10	—	DC
10.5.0.0	12	R2	R2
10.8.0.0	12	R4	R4
10.7.0.0	20	R4	R4
10.6.0.0	22	R3	R4
10.3.0.0	25	R3	R4
10.1.0.0	27	R1	R4
10.2.0.0	30	R2	R2
10.4.0.0	30	R4	R4

---

🖱️ Explorer interactif

Comment s'en servir

Clique une ligne de la table : le chemin s’allume hop par hop sur le schéma, tout le reste s’estompe. Le calcul apparaît sous la topologie — dist + interface = coût — avec le candidat perdant barré quand il y en a un. Change de routeur source en haut : table, arbre SPF et ordre de sélection Dijkstra se recalculent. Navigable au clavier : Tab pour entrer dans la table, ↑ ↓ pour parcourir les routes.

// —— Exécuté par Obsidian uniquement ——
// Sur le site, Quartz rend ce bloc en code et le masque par CSS ; c'est
// le HTML inline plus bas qui prend le relais.
const f = app.metadataCache.getFirstLinkpathDest("spf-explorer.js", dv.current().file.path);
if (!f) {
  dv.paragraph("⚠️ `spf-explorer.js` introuvable — vérifie `02 - Schemas/`.");
} else {
  const code = await app.vault.read(f);
  const host = this.container.createDiv({ attr: { id: "spf-app-obs" } });
  new Function(code).call(window);
  window.SPFExplorer.mount(host);
 
  // Masque la version destinée au site (div vide + blocs de code bruts).
  // Obsidian rend les blocs progressivement : on remonte au conteneur de
  // la note et on ré-applique via MutationObserver.
  const MARK = /spf-app\s*\{|var IFACE\s*=|id="spf-app"/;
 
  const scope = () =>
    this.container.closest(".markdown-preview-view, .markdown-rendered, .markdown-source-view") ||
    this.container.parentElement ||
    document;
 
  const hide = () => {
    const root = scope();
    if (!root || !root.querySelectorAll) return;
    // la div vide destinée à Quartz
    root.querySelectorAll("#spf-app").forEach(e => {
      const box = e.closest("p, div.el-div, div.el-pre") || e;
      box.style.display = "none";
    });
    // les blocs <style> / <script> affichés en code brut
    root.querySelectorAll("pre").forEach(p => {
      if (MARK.test(p.textContent)) {
        const box = p.closest("div.el-pre, figure") || p;
        box.style.display = "none";
      }
    });
    // Obsidian peut aussi rendre le HTML brut en texte dans un <p>
    root.querySelectorAll("p").forEach(p => {
      if (p.querySelector("#spf-app") || (p.textContent.trim().startsWith("<style") && MARK.test(p.textContent))) {
        p.style.display = "none";
      }
    });
  };
 
  hide();
  const obs = new MutationObserver(hide);
  obs.observe(scope(), { childList: true, subtree: true });
  setTimeout(() => obs.disconnect(), 5000);
}

---

🎯 Pièges relevés sur cet exercice

Trois erreurs commises, toutes de la même famille

Routeur	Réseau	Erreur	Correct	Cause
R1	10.9.0.0	20	30	coût interface (10) oublié
R3	10.9.0.0	25	30	interface oubliée + mauvais chemin (via R1 au lieu de R4)
R5	10.2.0.0	20	30	coût interface (20) oublié

Dans les trois cas : distance au routeur donnée à la place de distance + interface.

Méthode de vérification rapide

1. Calculer d’abord la matrice routeur↔routeur complète (Dijkstra une fois par nœud).
2. Pour chaque réseau, lister tous les routeurs qui y sont attachés.
3. Pour chacun : dist(moi → ce routeur) + coût interface, puis garder le minimum.
4. Si égalité entre deux chemins → ECMP, on installe les deux.

---

❓ Points flous

• Comment OSPF calcule-t-il réellement le coût d’interface par défaut (10^8 / bande passante) et quelle valeur pour une série à 1,544 Mbps ?
• Comportement exact de l’ECMP : round-robin par paquet ou par flux (CEF) ?

---

🔗 Voir aussi

• _Reseaux
• Dijkstra pas à pas — Tableaux de calcul 5 routeurs — déroulé complet en tableau, étape par étape, pour les 5 routeurs
• 2026-09-11 — OSPF et algorithme à état de lien — le cours dont cet exercice est l’application
• 2026-09-11 — Routage dynamique et familles de protocoles — métrique, AD, load balancing
• 2026-09-04 — Routage et modèles OSI-TCP-IP
• VLSM — Découpage en sous-réseaux
• SPF Explorer — même outil en page autonome (artifact privé, hors vault)