Problème — Plus court chemin et coût de routage

Réseaux : protocoles, routage et sécurité · niveau 3 (difficile)

Énoncé

Problème — Plus court chemin et coût de routage.

On modélise un réseau par un graphe pondéré. Les routeurs sont A, B, C, D, E. Les liens et leurs coûts OSPF sont :

A--B : 2 ; A--C : 5 ;
B--C : 1 ; B--D : 7 ;
C--D : 3 ; D--E : 1 ; C--E : 8.

Déterminer le chemin de coût minimal de A vers E (méthode OSPF), et le comparer au chemin choisi par RIP.

Corrigé

On applique le principe du plus court chemin (Dijkstra) depuis A.

Vers B : $A \to B = 2$ .
Vers C : directement $A \to C = 5$ , ou $A \to B \to C = 2 + 1 = 3$ . On retient 3.
Vers D : $A \to B \to C \to D = 3 + 3 = 6$ (meilleur que $A \to B \to D = 2 + 7 = 9$ ). On retient 6.
Vers E : par D, $6 + 1 = 7$ ; par C directement, $3 + 8 = 11$ . On retient 7.

Le chemin OSPF optimal est $A \to B \to C \to D \to E$ , de coût total 7.

Pour RIP, on compte le nombre de sauts. Quelques chemins possibles :

$A \to C \to E$ : 2 sauts ;
$A \to B \to C \to D \to E$ : 4 sauts.

RIP choisit $A \to C \to E$ (2 sauts), alors que ce chemin a un coût réel de $5 + 8 = 13$ , bien plus élevé que les 7 d'OSPF. Ce problème montre concrètement pourquoi OSPF est préféré sur les grands réseaux : il prend en compte la qualité des liens, pas seulement leur nombre.