Un réseau relie quatre routeurs

Exercice supplémentaire · niveau 3 (difficile) · NSI (première), chapitre 9 — Machines, systèmes et réseaux · Réseaux, un cran plus loin

Énoncé

Un réseau relie quatre routeurs. Les liaisons directes sont : $A$ – $B$ (coût $1$ ), $B$ – $C$ (coût $1$ ), $A$ – $C$ (coût $5$ ), $C$ – $D$ (coût $1$ ), $B$ – $D$ (coût $4$ ).

Quel est le chemin de coût minimal de $A$ à $D$ ? Quel coût ?
La liaison $B$ – $C$ tombe. Nouveau chemin, nouveau coût ?
Un routeur ne connaît que ses voisins. Comment peut-il pourtant faire ce calcul ?

Corrigé

1. Les chemins de $A$ à $D$ :

Chemin	Coût
$A \to B \to C \to D$	$1 + 1 + 1 = 3$
$A \to B \to D$	$1 + 4 = 5$
$A \to C \to D$	$5 + 1 = 6$

Le meilleur est $A \to B \to C \to D$ , de coût $3$ — celui qui passe par le plus de routeurs. Le nombre de sauts n'est pas le coût.

2. Sans $B$ – $C$ : restent $A \to B \to D$ (coût $5$ ) et $A \to C \to D$ (coût $6$ ). Le nouveau chemin est $A \to B \to D$ , de coût $5$ .

3. Par échange d'information avec ses voisins. Chaque routeur leur annonce, pour chaque destination, le coût auquel lui sait l'atteindre ; il retient pour chaque destination la meilleure offre reçue, augmentée du coût du lien qui l'en sépare. De proche en proche, l'information se propage, et les tables convergent vers les chemins optimaux — sans qu'aucun routeur n'ait jamais vu le réseau entier.

Prolongement : la même idée sert à calculer les plus courts chemins dans un graphe, sujet de terminale. Et la difficulté réelle n'est pas le calcul, c'est la panne : quand un lien tombe, l'information circule lentement, et les routeurs peuvent se renvoyer les paquets pendant quelques instants — chacun croyant que l'autre sait faire mieux.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.