Worldlex Wiki L' algorithme de mise à jour par diffusion ( DUAL ) est utilisé par le protocole de routage EIGRP de Cisco pour garantir le recalcul global d'une route donnée lorsqu'elle risque de provoquer une boucle de routage . Il a été développé par JJ Garcia-Luna-Aceves chez SRI International . Son nom complet est DUAL FSM (DUAL finite-state machine ). EIGRP gère le routage au sein d'un système autonome , et DUAL réagit aux changements de la topologie de routage en ajustant dynamiquement et automatiquement les tables de routage du routeur.
EIGRP utilise une condition de faisabilité pour garantir que seules les routes sans boucle soient sélectionnées. Cette condition est restrictive : lorsqu’elle est vraie, aucune boucle ne peut se former, mais elle peut, dans certaines circonstances, rejeter toutes les routes vers une destination, même si certaines sont sans boucle.
Lorsqu'aucun itinéraire praticable vers une destination n'est disponible, l'algorithme DUAL effectue un calcul de diffusion afin d'éliminer toute trace de l'itinéraire problématique du réseau. L' algorithme de Bellman-Ford classique est ensuite utilisé pour déterminer un nouvel itinéraire.
Opération
DUAL utilise trois tables distinctes pour le calcul des routes. Ces tables sont créées à partir des informations échangées entre les routeurs EIGRP. Ces informations diffèrent de celles échangées par les protocoles de routage à état de liens . Dans EIGRP, les informations échangées comprennent les routes, la métrique (ou coût) de chaque route, et les informations nécessaires à l'établissement d'une relation de voisinage (telles que le numéro de système autonome, les temporisateurs et les valeurs K). Le détail des trois tables et de leurs fonctions est présenté ci-dessous :
- La table des voisins contient des informations sur tous les routeurs directement connectés. Une table distincte existe pour chaque protocole pris en charge (IP, IPX, etc.). Chaque entrée correspond à un voisin et comprend la description de son interface réseau et de son adresse. De plus, un minuteur est initialisé pour déclencher une vérification périodique de la disponibilité de la connexion. Cette vérification s'effectue par l'envoi de paquets « Hello » . Si aucun paquet « Hello » n'est reçu d'un voisin pendant une période donnée, le routeur est considéré comme hors service et supprimé de la table des voisins.
- La table de topologie contient les métriques (informations de coût) de tous les itinéraires vers une destination donnée au sein du système autonome. Ces informations proviennent des routeurs voisins répertoriés dans la table des voisins. Les itinéraires principaux (successeur) et secondaires (successeur possible) vers une destination sont déterminés à partir des informations contenues dans la table de topologie. Chaque entrée de cette table contient notamment les éléments suivants :
- "FD (Distance faisable) : La métrique calculée d'un itinéraire vers une destination au sein du système autonome.
- « RD (Distance signalée) » : La distance jusqu’à une destination, telle qu’annoncée par un routeur voisin. La RD est utilisée pour calculer la FD et pour déterminer si la route remplit la condition de faisabilité.
- État de la route : Une route est marquée comme « active » ou « passive ». Les routes « passives » sont stables et peuvent être utilisées pour la transmission de données. Les routes « actives » sont en cours de recalcul et/ou indisponibles.
- La table de routage contient le ou les meilleurs itinéraires vers une destination (selon la « métrique » la plus basse). Ces itinéraires sont les successeurs de la table de topologie.
DUAL évalue les données reçues des autres routeurs de la table de topologie et calcule les routes principales (successeur) et secondaires (successeur réalisable). La route principale est généralement celle dont la métrique est la plus faible pour atteindre la destination, et la route redondante est celle dont le coût est le deuxième plus faible (s'il remplit la condition de faisabilité). Il peut y avoir plusieurs successeurs et plusieurs successeurs réalisables. Les successeurs et les successeurs réalisables sont conservés dans la table de topologie, mais seuls les successeurs sont ajoutés à la table de routage et utilisés pour acheminer les paquets.
Pour qu'une route devienne une route admissible, son RD doit être inférieur au FD de la route admissible. Si cette condition d'admissibilité est remplie, l'ajout de cette route à la table de routage ne peut en aucun cas créer de boucle.
Si toutes les routes de remplacement vers une destination échouent, la route de remplacement admissible est immédiatement ajoutée à la table de routage. S'il n'existe aucune route de remplacement admissible dans la table de topologie, une requête est lancée pour rechercher une nouvelle route.
Exemple
Légende:
- + = Routeur
- − ou | = Lien
- (X) = Métrique du lien
A (2) B (1) C + - - - - - + - - - - - + | | (2)| | (3) | | + - - - - - + D (1) E
Un client situé sur le routeur E souhaite communiquer avec un client situé sur le routeur A. Cela implique qu'une route entre les routeurs A et E doit être disponible. Cette route est calculée comme suit :
Les voisins immédiats du routeur E sont les routeurs C et D. La commande DUAL sur le routeur E demande la distance (RD) signalée par les routeurs C et D respectivement jusqu'au routeur A. Voici les résultats :
- Destination : Routeur A
- via D : RD(4)
- via C : RD(3)
Le chemin passant par C est donc le plus économique. À l'étape suivante, la distance entre le routeur E et ses voisins est ajoutée à la distance indiquée pour obtenir la distance réalisable (FD).
- Destination : Routeur A
- via D : RD(4), FD(5)
- via C : RD(3), FD(6)
DUAL détermine donc que le trajet via D présente le coût total le plus faible. Ce trajet est alors désigné comme « successeur », doté du statut passif et enregistré dans la table de routage. Le trajet via C est conservé comme « successeur réalisable », car son RD est inférieur au FD du successeur.
- Destination : Routeur A
- via D : RD(4), FD(5) successeur
- via C : RD(3), FD(6) successeur possible