Comment les routeurs d'internet apprennent-ils les meilleures routes, et pourquoi peuvent-ils se tromper ?
Avec RIP, chaque routeur reprend les distances annoncées par ses voisins et ajoute 1 : en au plus n − 1 échanges, chacun connaît les plus courts chemins (algorithme de Bellman-Ford). Si une liaison tombe, deux routeurs peuvent se renvoyer des distances qui croissent de 1 en 1 : c'est pourquoi RIP fixe l'infini à 16.
Grand oral session 2027 : exposé de 10 minutes debout, puis 10 minutes d'échange, sans calculatrice. Plan prévu pour 9,5 min.
Pourquoi cette question : un modèle d'introduction
Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.
En NSI, nous avons simulé sur papier des tables de routage avec le protocole RIP. Chaque routeur ne parle qu'à ses voisins, et pourtant tous finissent par connaître le réseau entier. Mais j'ai vu qu'une panne pouvait provoquer une sorte de boucle, où les distances montaient lentement. J'ai voulu comprendre ces deux comportements avec des suites.
L'enjeu et les notions du programme
Étudier la convergence d'un algorithme distribué par une récurrence, et analyser un comportement pathologique par une suite arithmétique.
Mathématiques
- Raisonnement par récurrence (terminale)
- Suites arithmétiques (première)
- Minimum d'un ensemble fini (seconde)
Numérique et sciences informatiques
- Protocoles de routage RIP et OSPF, tables de routage (terminale)
- Graphes, distance en nombre de sauts (terminale)
Le plan de l'exposé en 9,5 min
1. Introduction
1 minInternet est un graphe de routeurs. Avec le protocole RIP, chaque routeur connaît seulement ses voisins et leur envoie régulièrement sa table : pour chaque destination, sa distance en nombre de sauts. Problématique : ces échanges locaux suffisent-ils à trouver les meilleures routes ?
2. Mathématiques : convergence en n − 1 échanges
4 minRègle : la distance de R vers une destination D est 1+min des distances annoncées par ses voisins. C'est l'algorithme de Bellman-Ford, réparti entre les routeurs.
Propriété P(k) : après k échanges, chaque routeur connaît la vraie distance vers D si un plus court chemin vers D fait au plus k sauts. Initialisation : D se connaît à distance 0. Hérédité : si un plus court chemin de R fait k+1 sauts, son premier voisin V est à k sauts ; après k échanges V le sait, et au suivant R calcule 1+k.
Un plus court chemin passe au plus par n routeurs, donc fait au plus n-1 sauts : après n-1 échanges, toutes les tables sont justes.
Comptage à l'infini : A est relié à B, B à la destination D. La liaison B–D tombe. B voit que A annonce « D à 2 » (en passant par B, ce que B ignore) : il note 3. A reçoit 3 et note 4, B note 5… La distance suit une suite arithmétique de raison 1 et ne s'arrête jamais.
3. NSI : les remèdes
3 minRIP pose que 16 sauts signifie « inaccessible » : la suite s'arrête quand elle atteint 16, après une quinzaine d'échanges (environ 30 secondes chacun). Conséquence : RIP ne convient qu'aux réseaux de moins de 16 sauts.
D'autres remèdes : ne pas annoncer une route au voisin par lequel on la connaît (« horizon partagé »). Les grands réseaux utilisent plutôt OSPF : chaque routeur connaît toute la carte du réseau et calcule lui-même les plus courts chemins avec Dijkstra, en pondérant les liaisons par leur débit.
4. Conclusion
1,5 minLes routeurs apprennent les meilleures routes en reprenant les distances de leurs voisins : une récurrence montre qu'il suffit de n-1 échanges. Mais après une panne, une information périmée peut faire croître les distances de 1 en 1, d'où la limite de 16. J'ouvre sur BGP, le protocole qui relie les grands réseaux entre eux.
Ce que j'écris au tableau
Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.
après k échanges : distances justes jusqu'à k sauts panne : 3,4,5,…,16=∞
Conclusion : la réponse à la question
Le routage RIP est un algorithme de plus court chemin réparti, dont une récurrence prouve la convergence. Le comptage à l'infini montre qu'un algorithme correct dans un réseau stable peut mal réagir aux changements.
Les questions probables du jury
Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.
Pourquoi un plus court chemin fait-il au plus n − 1 sauts ?
Il ne repasse jamais par le même routeur (sinon on pourrait couper la boucle), donc il visite au plus n routeurs.
Combien d'échanges pour passer de 3 à 16 dans le comptage à l'infini ?
La distance augmente de 1 à chaque annonce : 13 annonces successives entre A et B.
Quelle métrique utilise OSPF ?
Un coût lié au débit de chaque liaison, souvent la référence 10⁸ divisée par le débit en bit/s.
Qu'est-ce que l'horizon partagé ?
Un routeur n'annonce pas une route au voisin qui la lui a apprise, ce qui évite les boucles à deux routeurs.
Pourquoi RIP converge-t-il lentement sur un grand réseau ?
L'information ne progresse que d'un saut par échange, et les échanges ont lieu toutes les 30 secondes.
Les pièges qui coûtent des points
- Confondre nombre de sauts et distance kilométrique.
- Oublier que chaque routeur ne voit que ses voisins.
- Croire que RIP calcule avec Dijkstra (c'est OSPF).
Revoir les notions
Autres questions : graphes et réseaux
- Comment un GPS trouve-t-il le plus court chemin sans essayer tous les itinéraires ?
- Comment classer les pages du web par importance en ne regardant que les liens entre elles ?
- Peut-on parcourir tous les ponts d'une ville une seule fois chacun ? Le problème des ponts de Königsberg
- Est-il vrai que tout le monde sur Terre est relié à n'importe qui par une chaîne de six connaissances ?
Préparer l'oral, pas seulement le contenu
Gestion des 20 minutes de préparation, usage du tableau, posture debout, réponses au jury : la méthode complète, conforme aux règles de la session 2027.
Méthode : traiter une question de Grand oral →