- Nguyen Van Nam Institut de la Francophonie pour. - 5.4 Développement d’OSPF_LOOPFREE. - 6.5 Comparaison de la performance des deux algorithmes. - Figure 2-2: La représentation sous forme d'un graphe de la topologie. - Figure 2-7: Le FIB du routeur C de la topologie 2.1. - Figure 3-11: Destination influencée par un changement de la métrique du lien B→A: E 25 Figure 3-12: Topologies potentielles pour les boucles transitoire qui contiennent des carrés ou/et des anneaux. - Figure 6-5: La distribution du temps de la longueur des ORMS sur quatre topologies selon l'algorithme LIF. - 72 Figure 6-8: La comparaison entre LIF et LE&DKM de la longueur des ORMS sur ISP1. - 73 Figure 6-9: La comparaison entre LIF et LE&DKM de la longueur des ORMS sur ISP274. - De l’autre côté, les boucles transitoires sont provoquées lorsqu’il y a des changements de la topologie des réseaux à cause du délai de la convergence dans les protocoles de type. - de la durée des ruptures (l’axe. - L'idée d'oFIB est que si les FIBs sont mis à jour selon un ordre convenable lors du changement de la métrique d'un lien, il n'y aura pas de boucle dans le réseau. - L’objectif de ce travail est d’améliorer et d’implémenter l’algorithme de reconfiguration de métrique (LIF) pour éviter des boucles transitoire durant la convergence du protocole de routage OSPF (Open Shortest Path First) lors des changements de la topologie en consistant à réduire le nombre des ruptures dans les réseaux IP.. - LIF considère les changements de la topologie d’un réseau qui causent ceux de la métrique des liens. - LIF assure que l'application de la séquence sur le lien permet aux routeurs de mettre à jour les FIBs en ordre convenable (selon oFIB). - L’amélioration de l’algorithme : Néanmoins, LIF considère toutes les boucles comme les mêmes et le temps de calcul de LIF dépend du nombre des métriques de la séquence.. - Toutefois, la raison de la rapidité de LE&DKM ouvre une nouvelle orientation de recherche sur ce problème.. - Nous voyons les nœuds influencés par le changement de la métrique d'un lien pour limiter le nombre de destinations à vérifier dans chaque itération de LIF. - En fonction de la portée de fonctionnement des protocoles de routage, nous en distinguons deux types. - Ensuite, nous étudierons la façon de la diffusion des informations entre les routeurs OSPF (OSPF version 2 pour IPv4).. - Un routeur OSPF construit une vue entière de la topologie du réseau. - Chaque nœud est assigné une étiquette qui se compose du nœud précédant et la distance temporaire dans le chemin de la racine (S). - C'est un arbre (un graphe connecté et sans boucle) parce que: il y a des chemins de la racine vers les autres nœuds (orienté, connecté) et s'il y a une boucle, la plus courte distance entre un nœud de la boucle et lui- même (0) sera égale à la longueur de la boucle.. - Par exemple, dans la topologie de la figure 2.1, le réseau contient cinq routeurs. - Lorsqu’il y a un changement du routage ou de la topologie d’un réseau, la table de routage est mise à jour et ces changements sont référés dans le FIB. - Le FIB maintient l’information de l’adresse du prochain hôte basant sur les informations de la table de routage [21].. - Par exemple, en se basant sur l’arbre des plus courts chemins dans la figure 2-6, le FIB du routeur C de la topologie dans la figure 2.1 est dans la figure 2.7.. - A 192.168.3.1/24, eth0, 10. - B 192.168.2.1/24, eth1, 10. - D 192.168.2.1/24, eth1, 20. - 192.168.6.1/24, eth2, 20. - E 192.168.6.1/24, eth2, 10. - Ces derniers sont inondés aux autres routeurs dans le réseau qui leur permet à construire la vue entière de la topologie. - Chaque Summary-LSA décrit une route vers une destination à l'extérieur de la zone dans un AS (inter-area route) iv) ASBR Summary LSA (Type 4-LSA): il est origine des routeurs de frontière (BR). - Dans ce chapitre, nous étudierons le mécanisme des boucles transitoires durant la convergence d’OSPF lors du changement de la métrique des liens.. - Les boucles de routage peuvent être détectées par la trace de la répétition des instances (replicas stream) d’un paquet dans un seul lien [23].. - Dans la topologie de la figure 2.1, supposons que la métrique du lien entre l'interface 192.168.2.1 du routeur 192.168.1.2 (B) et l'interface 192.168.2.2 du routeur 192.168.2.2 (C) est reconfigurée par 30.. - Néanmoins, lorsqu'il y a un changement de la métrique d'un lien X→Y, seuls les chemins utilisent ce lien pour atteindre une destination Z sont influencées. - En revanche, si Y n'est pas dans le plus court chemin de X vers Z, les routes vers Z des autres nœuds restent les mêmes lorsqu'il y a un changement de la métrique du lien X→Y.. - Propriété 3.4.1 Étant donné un graphe G=(V,E), un lien X→Y qui appartient à E, les destinations influencées par un changement de la métrique du lien X→Y se trouvent dans le sous arbre de l’arbre des plus courts chemins de X dont la racine est Y [1].. - Figure 3-11: Destination influencée par un changement de la métrique du lien B→A: E. - Avec ISP 1, ISP 2 et Tier B, le changement de la métrique de 40 % liens peut causer des micro boucles.. - En effet, dans un anneau, le changement de la métrique de chaque lien X→Y peut causer une boucle. - Si le plus court chemin de A vers B passe X→Y, A pourra changer son plus court chemin vers B lors du changement de la métrique de ce lien. - Les boucles transitoires durant la convergence d’OSPF sont à cause de la mise à jour des FIBs des routeurs lors du changement de la métrique d’un lien. - Les boucles pour toutes les destinations sont trouvées en ne balayant que celles influencées par le changement de la métrique d’un lien. - DUAL (Diffusion Update Algorithm) [24], une partie du protocole EIGRP de CISCO, est le plus connu algorithme d’évitement des boucles transitoires et le contage jusqu’à l’infini du protocole de routage de type « vecteur à distance » lors des changements de la topologie ou de la métrique d’un lien. - Pour éviter les boucles transitoires lors du changement de la métrique d’un lien, chaque nœud doit mettre à jour son FIB après ses fils [1].. - Dans ce chapitre, nous proposons aussi une méthode alternative (LE&DKM- Loop enumeraiton and decisive key metric) pour calculer de la séquence de métrique à appliquer, et nous comparons la complexité théorique de ces méthodes.. - Afin de réduire le temps requis pour atteindre l'état final du lien (sa nouvelle métrique), le nombre des métriques de la séquence doit être minimisé.. - Cet ensemble sert de base pour la constitution de la séquence de métriques permettant d'éviter les boucles transitoires.. - Ensuite, nous présenterons le pseudo code de l'algorithme permettant de réduire la longueur de la séquence de reconfiguration et nous en analyserons la complexité.. - Comme analysé dans le chapitre 3, dans un graphe G=(V,E), une destination D Є V et un lien X→Y Є E, le changement de la métrique du lien X→Y influence le plus court chemin de certains nœuds du graphe vers D, par exemple nœud C. - Si il existe un autre chemin de C vers D (par exemple r 2 ) ne passant pas par X→ Y, un changement de la métrique du lien X→ Y peut forcer C à choisir r 2 au lieu de r 1. - Lorsqu'il y a un changement de la métrique du lien X→Y de m à M, la métrique clef du lien X→Y en. - Distance D (N, X→Y =m) est dans la notation 1) de la cette partie.. - Notons que cette séquence est croissante dans le cas d'une augmentation de la métrique d'un lien, et décroissant dans le cas de la diminution de la métrique d'un lien. - Nous ne considérons que l'augmentation de la métrique d'un lien. - Les techniques visant à gérer les cas de la diminution de la métrique d'un lien sont très similaires à celles des cas d'augmentation de métrique [1].. - Dans l'exemple de la partie 3.3, chapitre 3, nous avons : KMS A (B→C:10, 39)={10,30,39}. - Dans l'exemple de la partie 3.3 du chapitre 3, nous avons : KMS A (B→C:10, 39)={10,30,39},. - Dans l'exemple de la section 3.3, la séquence des métriques de reconfiguration correspondant à cette définition, notée nRMS A (B→C:10, 39), est égale à. - L'exemple de la section 3.3 va illustrer l'application des métriques basée sur le Théorème 4.2.2.2, pour la reconfiguration du poids du lien B→C de 10 à 39. - Le passage de la métrique de B→C de 30 à 31 forcerait B à arrêter d'utiliser le lien B→C pour joindre A. - Toutes les métriques entre rm 1 et rm j sont supprimées de la séquence. - La première procédure correspond au calcul de la séquence de reconfiguration étant donné un lien et une métrique terminale pour ce lien.. - trouver la plus longue métrique M dans RMS de sorte que la transition de la métrique courante à M ne cause pas de boucle pour la destination D*/. - Cette dernière se compose de deux phases importantes: la recherche binaire et la vérification de la présence de boucles. - La complexité de la première est O(logL) où L est la longueur de la RMS [17]. - résultat de la fusion de. - Selon le théorème 4.2.2.1, il n'y a pas de boucle dans la transition de la métrique. - Nous allons montrer que l’application de la séquence produites par LE&DKM est sans boucle.. - Étant donné un graphe G=(V,E), D Є V, X→Y Є avec la métrique initiale de X→Y=m et la métrique terminale de X→Y = M, l'algorithme LE&DKM produit une séquence des métriques de reconfiguration qui peut éviter toutes les boucles transitoires lors du changement de la métrique du lien X→Y de m à M.. - Selon la détection des boucles du chapitre 2, l'étape i) permet de détecter toutes les boucles possibles dans le réseau lors du changement de la métrique du lien X→Y de m à M.. - Le théorème 4.2.2.2 assure qu’il n’y a pas de boucles transitoires lors de l'application de la séquence des métriques clefs décisives moins 1.. - C’est un groupe des noeuds dans un même chemin de la racine ver une feuille. - choisit le père de la famille: le noeud le plus proche de la racine. - Dans l'algorithme DFS, nous balayons toutes les arêtes du graphe de la fusion de deux rSPTs et reconstruisons un cycle lorsqu'il est détecté. - Celle de la recherche de la métrique clef décisive pour chaque cycle est de O(N logN). - Pourtant, notons que le temps de calcul de LIF dépend de la longueur des KMS mais celui de LE&DKM dépend de la forme des boucles (micro boucle ou macro boucle).. - interval est l'intervalle (en ms) entre deux applications de métriques de la RMS, lors du changement de configuration.. - 1: protocols { 2: ospf_loopfree. - 8: protocols { 9: ospf_loopfree. - Par exemple, la location de la procédure pour mette à jour la. - Le fichier ospf_loopfree_base.hh contient la déclaration de la classe XrlOspfLoopfreeTargetBase dont les méthodes virtuelles correspondent aux procédures d’OSPF_LOOPFREE. - Le code source de ces méthodes sera rempli lors du développement de la boucle principale du processus (la partie suivante).. - La procédure « notifyLSDBchange » est responsable d’envoyer l’appel via XRL avec l’ID du routeur vers la procédure send_notify_lsdb_change d’OSPF_LOOPFREE (la ligne 5 de la figure 5.4). - Il envoie ensuite des XRLs vers OSPF pour appliquer, étape par étape, chaque métrique de la séquence. - Dans ce chapitre, nous analyserons l'efficacité des algorithmes de reconfiguration de métrique décrits dans le chapitre 3 (LIF et LE&DKM), en nous basant sur des mesures de la performance de notre implémentation en XORP. - %CDF » représente le taux cumulé de la longueur des ORMS et l’axe « RMS length » représente la longueur des ORMS pour les liens dans une topologie.. - %CDF » représente le taux cumulé de la longueur des ORMS et l’axe « RMS length » représente la longueur des ORMS pour les liens d’ISP1 et d’ISP2, respectivement... - DKM ne dépend pas de la longueur des RMS et les boucles sont de type. - «micro» comme analysé dans le chapitre 3 et dans ce cas LE&DKM est plus rapide que LIF (l’analyse de la complexité dans le chapitre 4). - Figure 6-8: La comparaison entre LIF et LE&DKM de la longueur des ORMS sur ISP1. - Figure 6-9: La comparaison entre LIF et LE&DKM de la longueur des ORMS sur ISP2. - Deux aspects ont été étudiés : le temps de calcul et la longueur de la séquence de reconfiguration. - Annexe 1 : Un exemple de la LSDB dans un routeur. - interface ospf_loopfree/0.1. - ospf_loopfree/0.1. - Annexe 6 : Un extrait de la déclaration de la classe XrlOspfLoopfreeNode pour traiter les fonctionnalités d’OSPF_LOOPFREE