Revenir
Revenir

Routage

Vous habitez Paris et votre ami Marseille. Imaginez que vous voulez envoyer une lettre à celui-ci. La...

Sommaire

Les principes de base du routageLe principe du routage d'un courrierLe principe du routage d'un paquet de donnéesLe routage sur le réseau des réseaux
Différentes stratégies de routage sur les réseauxExemple de réseau de routeurs interconnectés - GraphiqueConstruire un graphe en arbre des plus courts cheminsQuelques stratégies de routage à envisagerConstruire un tableau des sauts d'un routeur à un autreAlgorithme de modification de la table de routage d'un routeurLa solution du routage dynamique
Questions sur le routage
La table des chemins les plus courts - Questions
Les stratégies de routage - Questions
La table des sauts - Questions
Le routage dynamique - Questions

Les principes de base du routage

Le principe du routage d'un courrier

Vous habitez Paris et votre ami Marseille. Imaginez que vous voulez envoyer une lettre à celui-ci. La lettre contient un message renfermant des informations que vous souhaitez lui transmettre. Maintenant, pour que la lettre atteigne votre ami, elle doit, après que vous l'ayez déposée au bureau de poste, passer par plusieurs centres de tris postaux intermédiaires.
Lorsque vous remettez votre lettre au bureau de poste, celle-ci est acheminée jusqu'au centre de tri principal de la ville. Constatant que l'adresse du destinataire n'est pas celle de la ville de dépôt, la lettre est envoyée au centre de tri régional. Constatant que l'adresse du destinataire n'est pas dans la région de la ville où le dépôt a été effectué, la lettre est envoyée au centre de tri de la région où se trouve la ville du destinataire. La lettre est alors envoyée vers le centre de tri principal de la ville de votre destinataire puis remise au facteur responsable de la tournée du quartier où se trouve la maison dans laquelle votre ami habite.

Le principe du routage d'un paquet de données

Dans un réseau informatique, chaque centre de tri postal représente un routeur et la lettre est comparable à un paquet de données. Les routeurs sont responsables de faire passer les paquets d'un point à un autre à travers le réseau, tout comme les centres de tri font passer les lettres d'un endroit à un autre.
Pour ce faire, les routeurs examinent l'en-tête du paquet de données qui contient l'adresse IP de destination. Ils utilisent cette information pour déterminer le prochain routeur (ou nœud) vers lequel ils doivent envoyer le paquet.
Chaque routeur dispose de sa propre table de routage qui contient des informations sur les réseaux et les chemins disponibles. Ces tables de routage permettent aux routeurs de prendre des décisions sur la meilleure route à emprunter pour acheminer les paquets.

Le routage sur le réseau des réseaux

Internet est un réseau mondial global, non centralisé, constitué de millions d'autres réseaux aussi bien publics que privés. Pour trouver son chemin et être transmise d'une machine source vers une machine cible, une information doit transiter par des passerelles, appelées également routeurs, qui assurent l'interface entre différents réseaux de natures très différentes. Le routage, c'est-à-dire la capacité qu'une information emprunte le bon chemin, s'inscrit dans le cadre du protocole IP : son efficacité est la clé de voûte du fonctionnement d'Internet.
Le routage IP est un processus itératif où les paquets sont transmis de routeur en routeur jusqu'à ce qu'ils atteignent finalement leur destination. Chaque routeur examine l'adresse de destination et détermine le prochain routeur vers lequel il doit envoyer le paquet. Ce processus se poursuit jusqu'à ce que le paquet atteigne sa destination finale.

Différentes stratégies de routage sur les réseaux

Exemple de réseau de routeurs interconnectés - Graphique

Construire un graphe en arbre des plus courts chemins

Il est possible de modéliser un réseau par un graphe en arbre à partir du routeur chargé d'acheminer l'information. Ce graphe permet de construire un tableau dans lequel figurent tous les chemins les plus courts, au sens de plus proches voisins, entre un nœud de départ et les autres nœuds qui composent le réseau.

Quelques stratégies de routage à envisager

Le réseau Internet est un système d'une complexité considérable et sa structure est sujette à des changements fréquents. Ces changements peuvent inclure des pannes ou une saturation temporaire des routeurs, des liaisons coupées, l'ajout de nouveaux routeurs et de nouveaux réseaux locaux, entre autres.
Dans ce contexte, il est essentiel d'automatiser et d'optimiser la recherche du chemin le plus court afin de permettre l'acheminement des messages en quelques dizaines de millisecondes vers n'importe quel endroit de la Terre.
Cependant, il est important de souligner que certaines stratégies envisageables, présentées ici, auraient été incompatibles avec le développement de l'Internet à l'échelle actuelle. Il convient donc de prendre en considération les inconvénients de ces stratégies.
Stratégie 1 -Chaque information est diffusée vers tous les nœuds du réseau : elle finira bien par arriver à destination.
Stratégie 2 -Chaque routeur dispose d'un tableau des chemins les plus courts vers tous les autres nœuds du réseau qu'il doit actualiser à chaque changement d'architecture.
Stratégie 3 -Chaque routeur dispose d'une carte complète du réseau, mise à jour régulièrement. Cette carte est consultée à chaque fois qu'une information doit prendre une chemin alternatif en raison d'un problème sur le meilleur chemin possible.
Stratégie 4 -Un serveur central héberge une carte complète du réseau. Cette carte est accessible à tous les routeurs et est régulièrement mise à jour.

Construire un tableau des sauts d'un routeur à un autre

Une autre manière de modéliser la propagation d'une information dans un réseau est de ne pas raisonner sur les plus courts chemins, mais sur le nombre de sauts minimum à effectuer d'un routeur à un autre.

Algorithme de modification de la table de routage d'un routeur

En réalité, personne ne dispose d'une carte complète et précise d'Internet, et cela n'est absolument pas nécessaire pour le routage. Ce qui importe, c'est que chaque routeur connaisse l'état de ses voisins immédiats et puisse indiquer la direction à prendre pour chaque information transmise, sans avoir connaissance de l'ensemble du chemin à parcourir. Mais comment s'assurer qu'il indique la bonne direction ? Cela est rendu possible grâce à un algorithme, par lequel chaque routeur, dès qu'il est informé d'un changement d'état chez l'un de ses voisins immédiats, informe à son tour les autres voisins de ce changement. Ces derniers pourront éventuellement modifier la direction qu'ils indiqueront aux futurs messages. Ainsi, l'information sur les changements du réseau se propage progressivement, et en temps réel, chaque routeur adapte sa table de routage en conséquence.
L'algorithme ci-dessus résume, d'une manière simplifiée, l'adaptation de la table de routage d'un routeur lorsque celui-ci est informé qu'un routeur voisin, nommé M, est en panne, inaccessible ou a été supprimé. La procédure décrite est mise en œuvre pour une destination donnée notée X.

La solution du routage dynamique

Le routage dynamique est un mode opératoire utilisé dans les réseaux informatiques pour déterminer la meilleure façon de diriger les données (ou paquets) d'un point à un autre à travers le réseau. Plutôt que d'utiliser des chemins prédéfinis, le routage dynamique permet aux routeurs du réseau de communiquer entre eux et de prendre des décisions en temps réel sur la meilleure route à suivre.
Les avantages du routage dynamique sont multiples :
1. Adaptabilité
Le routage dynamique permet aux réseaux de s'adapter aux changements de topologie ou aux pannes. Lorsqu'un routeur détecte un changement dans le réseau, tel qu'une nouvelle connexion ou une défaillance d'un lien, il peut communiquer avec les autres routeurs pour mettre à jour les informations présentes dans leurs tables de routage respectives. Cela permet d'optimiser le chemin emprunté par les paquets pour atteindre leur destination, même en présence de modifications constantes.
2. Optimisation
Dans les réseaux de grande taille, il peut y avoir des milliers de routeurs interconnectés. Le routage dynamique permet une gestion efficace de ces réseaux en répartissant la charge de calcul entre les différents routeurs. Chaque routeur est responsable de calculer les meilleurs chemins vers les destinations qu'il connaît, ce qui réduit la charge globale sur le réseau.
3. Convergence accélérée
La convergence fait référence à la capacité du réseau à se rétablir rapidement après une panne ou un changement. Grâce au routage dynamique, les routeurs peuvent détecter les changements rapidement et mettre à jour les tables de routage en conséquence. Cela permet au réseau de converger rapidement vers un nouvel état stable, minimisant ainsi les temps d'indisponibilité.
Néanmoins avec le routage dynamique, le temps requis pour délivrer un message n'est pas garanti. En effet, lorsqu'un paquet est envoyé à travers un réseau, il peut emprunter différents chemins pour atteindre sa destination. Ces chemins peuvent avoir des longueurs (métriques) différentes, des délais de transmission différents ou des congestions variables. En raison de ces variations potentielles, il est impossible de garantir un temps de livraison constant pour les paquets.
De plus, les décisions de routage prises par les routeurs sont basées sur des informations partielles et des estimations de l'état actuel du réseau. Ces informations sont échangées entre les routeurs via des protocoles de routage, mais elles peuvent être incomplètes ou prendre un certain temps pour se propager à travers le réseau. Par conséquent, les routeurs peuvent prendre des décisions basées sur des informations qui ne sont pas à jour, ce qui peut affecter les délais de livraison des paquets.

Questions sur le routage

La table des chemins les plus courts - Questions

1. En vous basant sur le réseau-exemple, recherchez les chemins les plus courts entre le nœud C et le nœud I.
2. En vous inspirant du graphe en arbre partant du nœud A et du tableau des plus courts chemins qui lui est associé, procédez de la même façon en partant du nœud B.
3. Si le routeur E tombe en panne ou s'il est saturé, quel est alors le meilleur chemin entre B et I ? Combien de « meilleurs » chemins partant de B seront affectés et devront être recalculés ?
4. Comment cette panne affectera-t-elle les meilleurs chemins possibles depuis le nœud A ?
5. À la lumière des questions 3 et 4, que peut-on en déduire ?

Les stratégies de routage - Questions

1. La modélisation du réseau-exemple présente plusieurs inconvénients par rapport à la réalité. Citez quelques-uns d'entre eux.
2. Trouvez les inconvénients majeurs de chacune des stratégies présentées dans le document « Quelques stratégies de routage à envisager ».
3. Existe-t-il, selon vous, une autre stratégie bien meilleure que les précédentes ?

La table des sauts - Questions

1. Complétez le tableau du réseau exemple qui modélise la propagation d'une information depuis le nœud A sous la forme de sauts d'un routeur à l'autre.
2. Dans ce tableau complété, certaines informations sont redondantes. Proposez le même tableau sous une forme simplifiée.
3. Reprenons l'hypothèse que le routeur E tombe en panne. En appliquant l'algorithme de modification de la table de routage, comment le routeur B va-t-il modifier la sienne pour acheminer une information vers H ?
4. Supposons maintenant que le routeur A est informé du changement de la table de routage du routeur B. Quel est désormais le plus court chemin de routeur A vers le routeur I ?

Le routage dynamique - Questions

1. Proposez un algorithme qui s'activerait dès qu'un routeur voisin informerait d'une modification de sa table de routage et qui aurait pour objectif de corriger si nécessaire celle-ci afin de garantir le chemin le plus court. Pour simplifier, on considèrera que l'algorithme traitera d'une seule destination notée X.
2. La mise en œuvre de l'algorithme précédent n'intègre pas la garantie du temps de transmission ni le fait d'empêcher qu'une information puisse s'égarer par des renvois sans fin notamment si un chemin principal est hors service. Proposez une solution pour qu'une information ne soit pas transmise indéfiniment dans le réseau afin de ne pas l'encombrer inutilement.
3. Sans le routage dynamique, Internet n'aurait pas pu se développer aussi rapidement. Expliquez rapidement ses principaux avantages et son principal défaut.