Dans le coeur du fonctionnement d’EIGRP: L’algorithme DUAL

Le programme ICND2 de la certification Cisco CCNA prévoit que le candidat soit capable de configurer et vérifier le protocole de routage EIGRP et, si vous lisez le détail du programme, vous trouverez une liste détaillée des termes et concepts à maitriser:

 

2.6 Configure and Verify EIGRP (Single AS)
 2.6.a Feasible Distance/feaasible successor/administrative distance
 2.6.b Feasibility Condition

 

Les termes qui sont présentés pour les parties 2.6.a et 2.6.b sont des termes spécifiques à l’algorithme DUAL (Diffusing Update ALgorithm). Cet algorithme est utilisé par EIGRP pour traiter et choisir les routes qui vont être installés dans la table de routage de façon à garantir l’absence de boucles de routage dans le réseau.

Comme nous l’avons vu dans l’article « EIGRP Update & Échange de routes« , après la détection des voisins, les messages UPDATE sont échangés.  Dans ces messages, il y a les informations sur les différentes destinations et les métriques associées.

 

Absence de boucles

Comme dans tous les protocoles à vecteur de distance, une des problématiques consiste à s’assurer que le routage permet d’identifier des chemins exempts de boucles. En environnement EIGRP, l’absence de boucle est garanti grâce à deux mécanismes:

• Split Horizon
• Feasibility Condition

 

Split Horizon

L’idée consiste à interdire de renvoyer des informations apprises depuis une interface donnée vers cette même interface. C’est ce mécanisme que l’on retrouve également dans le protocole RIP (protocole à vecteur de distance, lui aussi).

 

DUAL Feasibility Condition

Voilà un terme délicat à traduire en français! Je ne m’y risquerai pas… Par contre, il faut bien comprendre le concept qu’il y a derrière. L’idée de base est la suivante:  » Si ta métrique vers une destination est plus petite que ma métrique pour cette même destination, alors tu es plus proche que moi de cette destination (et tu dois donc être le chemin sans boucle vers la destination) « .

 

Vocabulaire DUAL

Le vocabulaire DUAL EIGRP peut paraitre difficile au premier abord. Il faut donc s’habituer à l’utiliser et à connaitre les concepts associés à chacun de ces termes. 

Attention, le terme de métrique n’est pas utilisé par EIGRP. L’implémentation de ce protocole utilise le terme de distance (il ne faudra donc pas mélanger Distance EIGRP et Distance Administrative…).

 

Voici la liste du vocabulaire DUAL/EIGRP à maitriser pour les certifications Cisco Routing & Switching (CCNA, CCNP et CCIE).

 

Successor

Il s’agit du prochain noeud à utiliser pour atteindre une destination donnée. C’est donc le chemin le plus court pour cette destination.

 

Feasible Distance (FD)

C’est la métrique associée au chemin via le successor.  

 

Feasible Successor (FS)

Il s’agit d’un noeud de secours qui permet également d’atteindre la destination. Ce noeud ne présente pas le chemin optimal tant que le successor est disponible mais il peut être utilisé en secours, en cas de panne du successor par exemple.

C’est l’identification, au préalable, de ce chemin de secours qui va permettre au protocole EIGRP de réagir rapidement en cas de panne sur le chemin nominal.

 

Advertised Distance (AD)

Lorsqu’un noeud dispose d’un chemin pour aller vers une destination, il passe par un successor avec une métrique qui est sa Feasible Distance. Cette information est transmise aux autres routeurs (via un message EIGRP UPDATE). Les autres routeurs identifient cette métrique sous le terme Advertised Distance.

La différence entre Feasible Distance et Advertised Distance est donc essentiellement liée au point de vue. La meilleure distance d’un routeur pour une destination (c’est donc sa Feasible Distance) est annoncée à un routeur voisin et elle est donc pour ce routeur voisin une Advertised Distance (c’est pourtant la même valeur…) 

 

Local Distance (LD)

Il s’agit de la métrique pour atteindre un noeud voisin.

A ce stade des définitions, on peut donc voir qu’il faudra ajouter une Local Distance à une Advertised Distance pour avoir la Feasible Distance. Bien sûr, l’algorithme DUAL va privilégier le chemin le plus court donc la Feasible Distance la plus petite..

 Pas facile de suivre ? Un exemple va nous permettre d’associer ces termes dans un environnement concret.

 

Feasibility Condition 

Ce concept est utilisé par EIGP pour savoir si un chemin est valide ou non !

 

Un exemple pour bien comprendre….

Nous allons mieux comprendre le fonctionnement de l’algorithme DUAL en prenant un cas pratique. Considérons donc la topologie ci-dessous:

Etape 1 – Recherche du plus court chemin

Comme le montre le schéma, le routeur R5 est raccordé au réseau R avec une métrique de 1. La Feasible Distance de R5 pour atteindre R est de 1. Cette information est transmise à R2, R3 et R4. De leur point de vue, il s’agit de l’Advertised Distance.

Ainsi, après réception de l’information de routage, chaque routeur sait qu’il peut atteindre le réseau R avec une métrique totale égale à la Local Distance + Advertised Distance.  Donc, R2 peut atteindre R via R5 avec une métrique de (10+ 1) = 11 ; R3 peut atteindre R via R5 avec une métrique de (15+1) = 16 et enfin, R4 peut atteindre R via R5 avec une métrique de (20+1) = 21.

Chaque routeur transmet donc cette information  à ses routeurs voisins (sauf au routeur R5 pour respecter la règle de Split Horizon). Ainsi, R1 va recevoir une annonce venant de R2, R3 et R4. La Feasible Distance devient pour R1 l’Advertised Distance. 

R1 reçoit donc 3 possibilités:

• via R2 avec une Advertised Distance de 11,
• via R3 avec une Advertised Distance de 16,
• via R4 avec une Advertised Distance de 21. 

R1 va choisir le chemin le plus court. Mais pas sur la base de l’Adversité Distance ! Il doit prendre en compte la métrique pour atteindre le routeur qui lui fait l’annonce ! Ainsi, R1 calcule qu’il peut atteindre R:

• via R2 avec une métrique de 21,
• via R3 avec une métrique de 36,
• via R4 avec une métrique de 36.

Le routeur R2 devient donc le Successor pour la destination R. La Feasible Distance est alors de 21.

 

Etape 2 – Recherche de chemins de secours

Après l’identification du plus court chemin, R1 va voir s’il peut utiliser d’autres chemin en secours (pour diminuer les délais de pertes de connectivité suite à une panne sur le chemin nominal).

Le routeur va donc vérifier la Feasibility Condition. C’est à dire comparer l’Advertised Distance (AD) par un voisin avec sa Feasible Distance (FD). Dans notre exemple, pour le réseau R, la FD de R1 est de 21 (via R2).

 

Est-ce que R3 et/ou R4 peuvent être des solutions de secours utilisées par R1 en cas de panne ? 

Pour cela, on sait que R1 a une FD =21. Il va donc chercher quels voisins lui ont annoncer une AD < 21 (c’est la fameuse Feasibility Condition).  R3 a envoyé une AD de 16 et R4 a envoyé un AD de 21. Du coup, 16 < 21  =>seul R3 est un Feasible Successor.

 

 Je pense qu’on a introduit tous les termes obscurs que l’on retrouve autour du protocole EIGRP et de son algorithme DUAL. Comme indiqué en introduction de cet article, ces termes doivent être maitrisés pour la certification Cisco CCNA Routing & Switching.  J’ai écrit cet article dans cette optique: dites moi dans les commentaires si quelque chose ne vous parait pas clair !