Protocoles de routage

Spé. NSI · Terminale · cours rédigé et vérifié par Claryo, conforme au Bulletin officiel

L'essentiel

Internet est un ensemble de réseaux interconnectés. Le routage est le processus qui détermine le chemin suivi par les paquets depuis leur source jusqu'à leur destination, en passant de routeur en routeur. Un routeur relie plusieurs réseaux ; à chaque paquet reçu, il consulte sa table de routage (qui associe à une destination un prochain saut et une interface de sortie) pour décider vers où le réémettre.

Les protocoles de routage servent à construire et maintenir ces tables automatiquement. Deux grandes familles sont au programme :

  • Protocoles à vecteur de distance (ex. RIP) : chaque routeur ne connaît que les distances annoncées par ses voisins directs ; il n'a qu'une vision locale. La métrique est le nombre de sauts. RIP plafonne une route à 15 sauts (16 signifie « inaccessible ») afin de borner le comptage à l'infini et d'éviter les boucles. Sa convergence est lente.
  • Protocoles à état de liens (ex. OSPF) : chaque routeur diffuse l'état de ses liens à tout le réseau ; chacun reconstruit une carte complète de la topologie, puis calcule les plus courts chemins par un algorithme de type Dijkstra. La métrique est un coût lié au débit des liens. OSPF converge plus vite et choisit de meilleurs chemins que RIP.

La convergence désigne le délai au bout duquel tous les routeurs partagent une vision cohérente du réseau après un changement (panne, nouveau lien).

Formules et schémas clés

Coût d'un chemin = somme des métriques de ses liens : \text{coût}(s_0 \to s_1 \to \dots \to s_k) = \sum_{i=0}^{k-1} \text{poids}(s_i, s_{i+1}).

L'algorithme de Dijkstra (poids positifs) calcule le coût minimal depuis une source : on traite à chaque étape le sommet non visité de plus petite distance et on relâche ses voisins : \text{si } \text{dist}[u] + \text{poids}(u,v) < \text{dist}[v], \text{ alors } \text{dist}[v] \leftarrow \text{dist}[u] + \text{poids}(u,v). Avec une file de priorité, la complexité est O((n+m)\log n) pour n sommets et m arêtes.

Méthode type bac

1. Pour un calcul de chemin optimal, énumérer les chemins simples possibles, sommer les coûts, retenir le minimum (penser à vérifier qu'un détour comme A-B-C-D peut battre un lien direct cher). 2. Pour comparer RIP et OSPF, structurer sur deux axes : vision (locale vs globale) et performance (convergence, qualité du chemin). 3. Pour la limite des 15 sauts, relier au problème du comptage à l'infini et des boucles.

Pièges

  • Croire qu'un lien direct est toujours le meilleur : un chemin à plusieurs sauts de faible coût peut être préférable (ici A-B-C-D = 4 bat A-B-D = 6).
  • Oublier que RIP n'a qu'une vision locale : il ne « voit » pas la topologie complète.
  • Confondre métrique RIP (nombre de sauts) et métrique OSPF (coût/débit).
  • Appliquer Dijkstra avec des poids négatifs : l'algorithme suppose des poids positifs.

Pour l'épreuve

Sachez définir routage, routeur et table de routage, et opposer clairement vecteur de distance (RIP, sauts, vision locale, lent) et état de liens (OSPF, coût, carte globale, rapide). Le calcul de plus court chemin sur un petit graphe pondéré est attendu : entraînez-vous à énumérer puis à comparer les coûts, et à dérouler Dijkstra. Mémorisez la limite des 15 sauts de RIP et sa justification (comptage à l'infini, boucles). À l'épreuve pratique, Dijkstra avec heapq sur un dictionnaire d'adjacence est l'implémentation de référence.