Cours — Calixte

2026-09-11 — OSPF et algorithme à état de lien

Properties1
tagscours, reseaux, ospf, etat-de-lien, lsp, dijkstra, spf, couche3

6 min de lecture

2026-09-11 — OSPF et algorithme à état de lien

Contexte

Matière : _Reseaux · Type : cours · Source : notes brutes du 11/09 Précédent : 2026-09-11 — Routage dynamique et familles de protocoles Application : Dijkstra — Tables de routage OSPF 5 routeurs — tables complètes des 5 routeurs

🎯 Objectifs de la séance

  • Suivre les trois étapes par lesquelles un protocole à état de lien construit ses tables.
  • Savoir écrire le LSP d’un routeur à partir d’une topologie.
  • Comprendre le principe d’initialisation et d’itération de Dijkstra.

Partie 1 — La topologie de référence

Cinq routeurs, onze réseaux. Les nombres portés sur le schéma sont les coûts des interfaces sortantes.

OSPF utilise Dijkstra

OSPF → Dijkstra. Le protocole est le cadre (échange d’informations, format des messages) ; Dijkstra est l’algorithme qui calcule effectivement les chemins à partir de ces informations.

Partie 2 — Les trois étapes

Étape 1 — Connaissance locale

Chaque routeur prend connaissance des réseaux directement connectés et de leur coût.

Le routeur ne regarde que ses propres interfaces. Il ne sait encore rien du reste du réseau.

Le résultat de cette étape est le LSP du routeur.

LSP — Link-State Packet

Paquet décrivant l’état des liens d’un routeur : la liste de ses réseaux directement connectés, chacun avec son coût. C’est la contribution du routeur à la carte collective.

Les LSP de la topologie

Chaque ligne se lit : réseau → lien concerné → coût de l'interface.

R1

RéseauLienCoût
10.1LAN 12
10.2R1–R220
10.3R1–R35
10.4R1–R420

R2

RéseauLienCoût
10.5LAN 22
10.2R2–R120
10.9R2–R510

R3

RéseauLienCoût
10.6LAN 32
10.3R3–R15
10.7R3–R410

R4

RéseauLienCoût
10.8LAN 42
10.10R4–R510
10.7R4–R310
10.4R4–R120

R5

RéseauLienCoût
10.11LAN 52
10.9R5–R210
10.10R5–R410

Vérification rapide d'un LSP

Le nombre de lignes = le nombre d’interfaces actives du routeur. R1 en a 4 (un LAN + trois liaisons série), R2 et R3 en ont 3, R4 en a 4, R5 en a 3.

Un lien de transit apparaît dans deux LSP, une fois de chaque côté — avec le coût de l’interface de ce côté-là. Ici les coûts sont symétriques (10.7 vaut 10 chez R3 comme chez R4), mais rien ne l’impose.

Étape 2 — Diffusion

Broadcast du LSP aux routeurs. Après la diffusion des LSP, chaque routeur possède la base de données des LSP — une base contenant tous les LSP de tous les routeurs.

LSDB — Link-State Database

La collection de tous les LSP reçus. Une fois la diffusion terminée, tous les routeurs ont une LSDB identique : c’est la carte complète du réseau, la même pour chacun.

C’est ce qui distingue l’état de lien du vecteur de distance : chaque routeur détient la topologie entière, il ne dépend plus de ce que ses voisins lui racontent.

Étape 3 — Calcul indépendant

À partir de la BDD des LSP, chaque routeur applique l’algorithme de Dijkstra indépendamment des autres. Chaque routeur trouve les meilleurs chemins pour aller vers les autres réseaux.

Même carte, arbres différents

Les routeurs partagent la même LSDB mais calculent des arbres différents : chacun se place à la racine. L’arbre SPF de R1 n’a rien à voir avec celui de R5, alors que les données de départ sont identiques.

LSDB identique partout
        │
   ┌────┼────┬────┬────┐
   ▼    ▼    ▼    ▼    ▼
  R1   R2   R3   R4   R5     ← chacun se met à la racine
   │    │    │    │    │
  SPF  SPF  SPF  SPF  SPF    ← arbres différents
   │    │    │    │    │
  table table table table table

Partie 3 — Initialisation de Dijkstra

Le principe donné en cours, en trois règles :

Les trois règles

  1. Initialisation — si les nœuds sont adjacents, on met le coût avec le prédécesseur ; sinon le coût est ∞.
  2. Sélection — on prend le coût minimal et on l’ajoute à N (l’ensemble des nœuds traités).
  3. Mise à jour — on regarde si le nœud où l’on vient d’arriver a des réseaux adjacents, et on réévalue les coûts.

On répète 2 et 3 jusqu’à ce que tous les nœuds soient dans N.

Exemple d’initialisation depuis R1

NœudCoût initialPrédécesseurPourquoi
R220R1adjacent via 10.2
R35R1adjacent via 10.3
R420R1adjacent via 10.4
R5∞—non adjacent à R1

Première itération : le minimum est R3 (5), il entre dans N. On réévalue alors ses voisins — et R4 tombe à 15 via R3 (5+10), ce qui bat les 20 du lien direct.

Le coût final n'est pas le coût du nœud

Dijkstra donne la distance jusqu’aux routeurs. Pour obtenir le coût d’un réseau, il faut encore ajouter le coût de l’interface qui le dessert : C’est l’erreur la plus fréquente sur cet exercice — détaillée dans Dijkstra — Tables de routage OSPF 5 routeurs.

Partie 4 — Résultat

Les cinq tables complètes, l’explorer interactif et le détail des pièges sont dans la fiche dédiée :

➜ Dijkstra — Tables de routage OSPF 5 routeurs

Les 55 routes des 5 routeurs, avec coût, prédécesseur et next-hop. Contient un widget interactif : cliquer une route allume son chemin sur la topologie.

Aperçu du résultat depuis R1 :

RéseauCoûtPréd.Next-hop
10.12—DC
10.35—DC
10.67R3R3
10.715R3R3
10.817R4R3
10.220—DC
10.420—DC
10.522R2R2
10.1025R4R3
10.1127R5R3
10.930R2R2

📌 Ajouts hors notes

❓ Points flous

  • À quelle fréquence les LSP sont-ils rediffusés — périodiquement, ou seulement sur changement de topologie ? → Seulement au démarrage du processus et à chaque changement de topologie, avec numéro de séquence et ancienneté (support PDF, voir Chapitre 3 — Routage dynamique (support de cours)).
  • Comment OSPF calcule-t-il le coût d’interface par défaut (10⁸ / bande passante ?) et quelle valeur pour une liaison série ?
  • La notion d’aire OSPF est-elle au programme ?

🔗 Voir aussi

Vue Graphique

Liens retour