Chapitre 3 — Routage dynamique (support de cours)
Contexte
Matière : _Reseaux · Type : fiche de révision du chapitre complet · Source : support PDF « Chapitre 3 - Routage Dynamique » + notes de séance Séances : 2026-09-11 — Routage dynamique et familles de protocoles · 2026-09-11 — OSPF et algorithme à état de lien Exercices : Dijkstra — Tables de routage OSPF 5 routeurs · Dijkstra pas à pas — Tableaux de calcul 5 routeurs · TP : 2026-10-05 — TP3 Routage statique et OSPF Réviser : Révisions — Routage dynamique et OSPF · Quiz — Routage dynamique et OSPF · Résumé rendu : Résumé chapitre 3 — Routage dynamique
Cette fiche reprend tout le support de cours, dans l’ordre des diapos. Les fiches de séance détaillent l’exemple à 5 routeurs ; ici on couvre aussi ce que le PDF ajoute (Hello, numéros de séquence, notation formelle de Dijkstra, exemples de métrique et d’AD).
1. Statique ou dynamique
| Routage statique | Routage dynamique | |
|---|---|---|
| Configuration | à la main, route par route | automatique, les routeurs échangent |
| Changement de topologie | l’admin doit corriger à la main | recalcul automatique d’un nouveau chemin |
| Cas d’usage | petit réseau non redondant | réseau moyen ou grand, chemins multiples |
Ce que le routage dynamique apporte :
- découvrir les réseaux distants ;
- maintenir à jour les informations de routage ;
- choisir le meilleur chemin vers chaque destination ;
- trouver un nouveau meilleur chemin quand la topologie change ;
- il peut aussi propager une route statique par défaut aux autres routeurs.
2. Plan de contrôle : distribué ou SDN
Un routeur transmet un paquet en comparant des bits de l’en-tête (l’IP destination) aux entrées de sa table. Deux plans :
Plan de données / plan de contrôle
- Plan de données (data plane) : acheminer le paquet reçu vers la bonne interface, à partir de la table.
- Plan de contrôle (control plane) : calculer cette table.
| Plan de contrôle traditionnel, par routeur | SDN (Software-Defined Networking) | |
|---|---|---|
| Où tourne le calcul | dans chaque routeur (algo distribué) | dans un contrôleur distant |
| Les routeurs se parlent ? | oui, ils échangent pour construire leurs tables | non, ils ne dialoguent pas entre eux pour calculer les chemins |
| Plan de contrôle | réparti | logiquement centralisé |
| Rôle du routeur | décide et transmet | applique les tables installées par le contrôleur |
3. Les protocoles de routage
| Protocole | Nom complet | Famille | Norme |
|---|---|---|---|
| RIP | Routing Information Protocol | vecteur de distance | RFC 1723 |
| EIGRP | Enhanced Interior Gateway Routing Protocol | vecteur de distance « avancé » (Cisco) | ouvert en 2013, RFC 7868 |
| OSPF | Open Shortest Path First | état de liens | RFC 2328 |
| IS-IS | Intermediate System-to-Intermediate System | état de liens | normalisé par l’ISO (pas une RFC à l’origine) |
Rappel de la séance : tous sont des IGP (à l’intérieur d’un système autonome). Entre AS, un seul protocole : BGP (décisions politiques). Voir 2026-09-11 — Routage dynamique et familles de protocoles.
4. Le routage à état de liens, étape par étape
Tous les protocoles à état de liens utilisent Dijkstra
Chaque routeur calcule son propre coût vers chaque destination, en cumulant les coûts des liens depuis lui-même.
Le PDF découpe le processus en 5 étapes (la séance en comptait 3 : connaissance locale, diffusion, calcul).
| # | Étape | Ce qui se passe |
|---|---|---|
| 1 | Réseaux directement connectés | chaque routeur apprend ses propres réseaux (interfaces actives, adresse, coût) |
| 2 | Hello | il envoie des paquets Hello sur ses liens pour découvrir ses voisins. Deux voisins qui se reconnaissent forment une contiguïté (adjacency). Plus de Hello reçus d’un voisin → il est déclaré injoignable |
| 3 | Construction du LSP | le routeur écrit son Link-State Packet : l’état de chacun de ses liens directement connectés |
| 4 | Inondation du LSP | il envoie son LSP à tous ses voisins, qui le relaient. Stocké par chacun dans la LSDB |
| 5 | LSDB → SPF → table | avec la LSDB, chaque routeur a la carte complète, lance SPF (Dijkstra), construit son arbre SPF et installe les meilleurs chemins dans sa table |
Le LSP de R1 (topologie du cours)
| Voisin / réseau | Type de lien | Réseau | Coût |
|---|---|---|---|
| R1 | Ethernet (LAN) | 10.1.0.0/16 | 2 |
| R2 | série point à point | 10.2.0.0/16 | 20 |
| R3 | série point à point | 10.3.0.0/16 | 5 |
| R4 | série point à point | 10.4.0.0/16 | 20 |
Quand un LSP est-il envoyé ?
Uniquement dans deux cas
- Au démarrage du processus de routage sur le routeur (ex. redémarrage).
- À chaque changement de topologie (ex. une liaison tombe).
Pas d’envoi périodique de la table entière, contrairement au vecteur de distance.
Un LSP porte aussi un numéro de séquence et une information d’ancienneté (aging). Ils servent à :
- savoir si le routeur a déjà reçu ce LSP (pas de double traitement) ;
- savoir si le LSP reçu contient une information plus récente que celle de la LSDB.
LSDB, arbre SPF, table
- Une fois l’inondation finie, tous les routeurs ont la même LSDB.
- Chacun lance SPF en se mettant à la racine : même carte, arbres différents.
- R1 commence par ses réseaux directement connectés et leurs coûts, puis ajoute les réseaux inconnus avec leurs coûts, puis SPF calcule le plus court chemin vers chaque réseau.
- Les meilleurs chemins sont ajoutés à la table de routage, avec les routes directement connectées et les routes statiques.
5. L’algorithme de Dijkstra
Notations
| Notation | Sens |
|---|---|
c(x, y) | coût du lien entre x et y ; ∞ si x et y ne sont pas voisins directs |
D(v) | coût actuel du chemin de la source jusqu’à v |
p(v) | prédécesseur de v sur ce chemin |
N' | ensemble des nœuds dont le plus court chemin est définitivement connu |
L’algorithme
1 Initialisation :
2 N' = {u}
3 pour tout nœud v :
4 si v est adjacent à u alors D(v) = c(u, v)
5 sinon D(v) = ∞
6
7 Boucle :
8 trouver w ∉ N' tel que D(w) est minimal
9 ajouter w à N'
10 pour tout v adjacent à w et ∉ N' :
D(v) = min( D(v), D(w) + c(w, v) )
11 jusqu'à ce que tous les nœuds soient dans N'
La phrase à retenir
On fige le plus proche, puis on regarde si passer par lui raccourcit le chemin vers ses voisins.
L’exemple du cours (u, v, w, x, y, z)
Liens : u–v 2 · u–w 5 · u–x 1 · v–w 3 · v–x 2 · x–w 3 · x–y 1 · w–y 1 · w–z 5 · y–z 2
| Étape | N’ | D(v), p(v) | D(w), p(w) | D(x), p(x) | D(y), p(y) | D(z), p(z) |
|---|---|---|---|---|---|---|
| init | u | 2, u | 5, u | 1, u | ∞ | ∞ |
| 1 | ux | 2, u | 4, x | 2, x | ∞ | |
| 2 | uxy | 2, u | 3, y | 4, y | ||
| 3 | uxyv | 3, y | 4, y | |||
| 4 | uxyvw | 4, y | ||||
| 5 | uxyvwz |
À chaque étape, le nœud ajouté à N’ est celui de plus petit D parmi ceux qui restent. Une case vide = nœud déjà dans N’.
Égalité entre v et y
Après l’étape 1, v et y valent tous les deux 2. Le PDF ajoute y d’abord, puis v. Prendre v en premier donne le même résultat final.
Détail des mises à jour du PDF :
- après x :
D(v) = min(2, 1+2) = 2,D(w) = min(5, 1+3) = 4,D(y) = min(∞, 1+1) = 2; - après y :
D(w) = min(4, 2+1) = 3,D(z) = min(∞, 2+2) = 4; - après v :
D(w) = min(3, 2+3) = 3(pas de changement) ; - après w :
D(z) = min(4, 3+5) = 4(pas de changement).
Table de routage de u (le next-hop se lit en remontant les prédécesseurs jusqu’au voisin de u) :
| Destination | Next hop |
|---|---|
| v | route directe |
| x | route directe |
| w | via x (w ← y ← x) |
| y | via x |
| z | via x (z ← y ← x) |
Next-hop ≠ prédécesseur
Le prédécesseur de w est y, mais u envoie vers w via x : on remonte la chaîne jusqu’au premier saut.
Exercice diapo 30
Sur la topologie R1 à R5 : écrire la LSDB de chaque routeur, appliquer Dijkstra depuis chaque routeur, en déduire la table de routage de chacun. Corrigé complet : Dijkstra — Tables de routage OSPF 5 routeurs et Dijkstra pas à pas — Tableaux de calcul 5 routeurs.
6. Métrique
Métrique
Valeur mesurable que le protocole attribue à une route pour en estimer le coût total de la source à la destination. Le coût le plus faible gagne. Elle ne compare que des routes apprises par le même protocole.
| Protocole | Métrique |
|---|---|
| RIP | nombre de sauts |
| OSPF | coût, basé sur la bande passante cumulée |
| EIGRP | bande passante, délai, charge, fiabilité |
Exemple du cours : R1 vers 192.168.4.0/24 (sur R4)
Deux chemins : R1 → R2 → R4 et R1 → R3 → R4, le lien R3–R4 étant plus lent.
| Protocole | Calcul | Résultat |
|---|---|---|
| RIP | 2 sauts par R2, 2 sauts par R3 | égalité → les deux routes installées, load balancing, même si R3–R4 est lent |
| OSPF | le lien lent coûte plus cher | chemin par R3 moins bon → seule la route via R2 est installée |
| OSPF, si R3–R4 était aussi en Gigabit | même coût des deux côtés | les deux routes installées (via 10.0.12.2 vers R2 et via 10.0.13.2 vers R3), trafic réparti |
Load balancing (ECMP)
Même destination + même protocole + même métrique → toutes les routes entrent dans la table et le trafic est réparti. Exemple de la séance : R2 → 10.4.0.0, coût 40 via R1 et via R5.
7. Distance administrative (AD)
Une entreprise n’utilise souvent qu’un seul IGP (OSPF, ou EIGRP en environnement très Cisco). Mais si deux protocoles tournent en même temps, leurs métriques ne se comparent pas.
L'exemple du cours
Vers 192.168.4.0/24 : OSPF propose une métrique de 30, EIGRP une métrique de 33 280. Impossible de dire laquelle est « meilleure » : ce sont deux échelles différentes. On regarde l’AD.
Distance administrative
Indique quelle source de routage est préférée quand un routeur apprend la même destination par plusieurs sources. La plus faible gagne : elle signifie une source jugée plus fiable.
| Source | AD |
|---|---|
| Route directement connectée | 0 |
| Route statique | 1 |
| EIGRP | 90 |
| OSPF | 110 |
| RIP | 120 |
Dans l’exemple : EIGRP (90) l’emporte sur OSPF (110), quelle que soit la métrique. C’est la route EIGRP qui entre dans la table.
Ordre de décision
- AD d’abord, pour départager des sources différentes.
- Métrique ensuite, entre routes d’un même protocole.
8. Exercice de programmation (Moodle)
Coder Dijkstra sans fonction toute faite de plus court chemin :
- représenter la topologie (matrice ou liste d’adjacence, coût par lien) ;
- générer la LSDB de chaque routeur (voisins, liens, coûts) ;
- lancer Dijkstra depuis chaque routeur : distance minimale, chemin complet, prédécesseur ;
- en déduire la table de routage de chaque routeur ;
- afficher LSDB, arbre SPF, distances, chemins, table finale ;
- marcher pour n routeurs, coûts positifs, et détecter les destinations inaccessibles (D reste à ∞).
Projet lié : ~/ESIEA/4A/reseau/projet/dijkstra (fiche projet/fiches/FICHE_OSPF_DIJKSTRA.md).
✅ À savoir faire pour l’examen
- Expliquer statique vs dynamique, et distribué vs SDN.
- Citer les 4 protocoles, leur famille et leur métrique.
- Dérouler les 5 étapes de l’état de liens (Hello, LSP, inondation, LSDB, SPF).
- Dire quand un LSP est envoyé et à quoi servent numéro de séquence et ancienneté.
- Remplir un tableau de Dijkstra et en déduire une table de routage (next-hop).
- Ajouter le coût d’interface pour obtenir le coût d’un réseau.
- Départager deux routes : AD puis métrique, et reconnaître un cas de load balancing.