EXERCICE TABLE DE ROUTAGE

La table de routage du nœud E peut être, par exemple : routage(E) = [(A, B) ; (B, B) ; (C, B) ; (D, D) ; (E, –) ; (F, F)] où le couple (A, B) signifie : pour aller à A, il faut passer par B. Il y a deux chemins de longueur 2 pour aller de E à A, celui qui passe par B et celui qui passe par F. Nous avons retenu celui qui correspondant à la plus petite lettre dans l’ordre alphabétique. De même pour le chemin de E à C. Avec un algorithme à état des liens, il faut comparer les différents chemins. Le chemin E-B-A est de coût 7 + 2 = 9 alors que E-F-A est de coût 3 + 4 = 7. Ce dernier est meilleur. Remarquons qu’un chemin long comme E-F-D est meilleur que le chemin direct E-D puisque 3 + 3 = 6 est meilleur que 7. L’algorithme de Dijkstra doit donc explorer tous les chemins. On procède par étapes. Cherchons les chemins de longueur 1. On trouve E-B = 2, E-D = 7, E-F = 3. Cherchons maintenant les chemins plus longs à partir du lien le plus prometteur, c’est-à-dire E-B. On trouve E-B-A = 2 + 7 = 9 et E-B-C = 2 + 5 = 7. Cherchons ensuite les chemins plus longs à partir du lien prometteur suivant c’est-à-dire E-F. On trouve E-FA = 3 + 4 = 7, meilleur que l’information précédemment calculée : cette dernière est effacée, on ne conserve que le meilleur chemin. De même E-F-D = 3 + 3 = 6 est meilleur que E-D précédemment calculé à 7. On continue ainsi en explorant les chemins à partir du lien prometteur suivant, ici E-C, etc. La table de routage de E est finalement : routage(E) = [(A, F) ; (B, B) ; (C, B) ; (D, F) ; (E, –) ; (F, F)]. Établissez la table de routage du nœud E de ce réseau, en minimisant le coût des liaisons. Vous supposerez que la topologie entière du réseau est connue. Vous utilisez un algorithme à vecteurs de distance. Vous utilisez un algorithme à état des liens qui s’appuie sur la métrique indiquée à la figure 8.5. Figure 8.5 Topologie et métrique du réseau.

EXERCICE 2ROUTAGE AVEC RIP

À l’état initial, chaque routeur ne connaît que ses voisins directs. La table de routage de A est donc : routage(A) = [(A, 0, –) ; (B, 1, B) ; (E, 1, E)]. De même les tables de routage des autres routeurs sont : routage(B) = [(A, 1, A) ; (B, 0, –) ; (C, 1, C) ; (E, 1, E)]. routage(C) = [(B, 1, B) ; (C, 0, –) ; (D, 1, D) ; (E, 1, E) ; (F, 1, F)]. routage(D) = [(C, 1, C) ; (D, 0, –) ; (F, 1, F)]. routage(E) = [(A, 1, A) ; (B, 1, B) ; (C, 1, C) ; (E, 0, –) ; (F, 1, F)]. routage(F) = [(C, 1, C) ; (D, 1, D) ; (E, 1, E) ; (F, 0, –)]. À la date T = 30 secondes, chaque routeur envoie sa table à ses voisins. Nous traiterons les événements dans l’ordre alphabétique. Quand A envoie routage(A) = [(A, 0, –) ; (B, 1, B) ; (E, 1, E)] à B, celui-ci constate qu’il n’y a aucune nouvelle entrée et que pour celles qu’il a déjà, les informations envoyées par A ne sont pas plus intéressantes que les siennes. De même pour E quand il reçoit routage(A) = [(A, 0, –) ; (B, 1, B) ; (E, 1, E)]. Maintenant traitons l’envoi par B de routage(B) = [(A, 1, A) ; (B, 0, -) ; (C, 1, C) ; (E, 1, E)] à ses voisins A, C et E. On considère le système autonome illustré à la figure 8.6, constitué de 6 routeurs nommés A, B, C D, E et F. On utilise le protocole RIP comme protocole de routage interne pour ce système autonome avec une périodicité d’envoi de messages de 30 secondes. Le coût de chaque saut est toujours 1. Une table de routage sera notée comme un ensemble d’entrées (X, distance, Y) dans lequel X est la destination qu’on cherche à atteindre, distance est la distance actuellement connue en passant par Y qui est donc le routeur suivant sur le chemin. Pour le routeur X, l’entrée correspondant à la destination X sera notée (X, 0, –) soit une distance nulle sans routeur intermédiaire. Établissez les tables de routage de chacun des 6 routeurs. L’ordre dans lequel circulent les messages du protocole RIP a-t-il de l’importance ? Combien de temps faut-il pour que l’algorithme converge ? La liaison entre B et C tombe en panne. Le routeur B détecte cette rupture et met à jour sa table en supposant que C se trouve maintenant à une distance 16 ; de même pour le routeur C. Montrez comment l’information se propage aux autres routeurs. Combien de temps faut-il pour que tous les routeurs aient recalculé leur table de routage ? Figure 8.6 Système autonome à 6 routeurs.A apprend que B connaît une route de distance 1 pour atteindre C, il ajoute donc dans sa table une nouvelle entrée (C, 2, B) : C est à une distance 1 de B ou B est à une distance 1 de A donc C est globalement à une distance 1 + 1 = 2 en passant par B. Les autres informations envoyées par B ne changent rien, la nouvelle table de A est maintenant : routage(A) = [(A, 0, –) ; (B, 1, B) ; (C, 2, B) ; (E, 1, E)]. C apprend que B connaît une route de distance 1 pour atteindre A, il ajoute donc dans sa table une nouvelle entrée (A, 2, B) : A est à une distance 1 de B ou B est à une distance 1 de C donc A est globalement à une distance 1 + 1 = 2 en passant par B. Les autres informations envoyées par B ne changent rien, la nouvelle table de C est maintenant : routage(C) = [(A, 2, B) ; (B, 1, B) ; (C, 0, –) ; (D, 1, D) ; (E, 1, E) ; (F, 1, F)]. Pour E, l’envoi de B n’apporte rien, sa table reste inchangée. Maintenant traitons l’envoi par C de routage(C) = [(B, 1, B) ; (C, 0, –) ; (D, 1, D) ; (E, 1, E) ; (F, 1, F)] à ses voisins B, D, E et F. (Remarque : il s’agit bien de la table initiale de C et non de celle qui a été mise à jour ci-dessus ; par contre les mises à jour se font sur les tables déjà modifiées.) B apprend que C connaît une route de distance 1 pour atteindre D et F, il ajoute donc dans sa table deux nouvelles entrées (D, 2, C) et (F, 2, C). Les autres informations envoyées par C ne changent rien, la nouvelle table de B est maintenant : routage(B) = [(A, 1, A) ; (B, 0, –) ; (C, 1, C) ; (D, 2, C) ; (E, 1, E) ; (F, 2, C)]. La nouvelle table de D devient : routage(D) = [(B, 2, C) ; (C, 1, C) ; (D, 0, –) ; (E, 2, C) ; (F, 1, F)]. et de même pour E et F : routage(E) = [(A, 1, A) ; (B, 1, B) ; (C, 1, C) ; (D, 2, C) ; (E, 0, –) ; (F, 1, F)]. routage(F) = [(B, 2, C) ; (C, 1, C) ; (D, 1, D) ; (E, 1, E) ; (F, 0, –)]. L’envoi par D de sa table routage(D) = [(C, 1, C) ; (D, 0, –) ; (F, 1, F)] n’apporte rien à C ni à F. L’envoi par E de sa table routage(E) = [(A, 1, A) ; (B, 1, B) ; (C, 1, C) ; (E, 0, –) ; (F, 1, F)] provoque l’apparition de l’entrée F dans la table de A et de l’entrée A dans la table de F. routage(A) = [(A, 0, –) ; (B, 1, B) ; (C, 2, B) ; (E, 1, E) ; (F, 2, E)] routage(F) = [(F, 2, E) ; (B, 2, C) ; (C, 1, C) ; (D, 1, D) ; (E, 1, E) ; (F, 0, –)]. Enfin, l’envoi par F de sa table routage(F) = [(C, 1, C) ; (D, 1, D) ; (E, 1, E) ; (F, 0, –)] ne change rien. À la fin de cette étape, les tables de routage sont donc les suivantes : routage(A) = [(A, 0, –) ; (B, 1, B) ; (C, 2, B) ; (E, 1, E)]. routage(B) = [(A, 1, A) ; (B, 0, –) ; (C, 1, C) ; (D, 2, C) ; (E, 1, E) ; (F, 2, C)]. routage(C) = [(A, 2, B) ; (B, 1, B) ; (C, 0, –) ; (D, 1, D) ; (E, 1, E) ; (F, 1, F)]. routage(D) = [(B, 2, C) ; (C, 1, C) ; (D, 0, –) ; (E, 2, C) ; (F, 1, F)]. routage(E) = [(A, 1, A) ; (B, 1, B) ; (C, 1, C) ; (D, 2, C) ; (E, 0, –) ; (F, 1, F)]. routage(F) = [(F, 2, E) ; (B, 2, C) ; (C, 1, C) ; (D, 1, D) ; (E, 1, E) ; (F, 0, –)]. On constate que les chemins de longueur 2 sont maintenant connus.