CHAPITRE 5
Implémentation des algorithmes de routage

5.1 Introduction

Par la suite nous allons procéder à des tests comparatifs des performances de différents algorithmes de routage dynamique.
Nous allons principalement implémenter quatre types différents :

Dans les sections suivantes, nous allons décrire les implémentations de ces algorithmes dans le node domain et le process domain de OPNET.

5.2 Implémentation dans le Node Domain

Les différents types de routeurs sont basés sur un même modèle de nœud comportant quatre entrées et quatre sorties. Les quatre entrées sont notées rcv et les quatre sorties xmt.
Les émetteurs et les récepteurs sont en réalités connectés deux à deux (rcvi avec xmti) pour former une seule et même liaison bidirectionnelle (un seul port physique).

La figure 5.1 illustre le modèle utilisé pour les routeurs.

Fig. 5.1 Le Node model du routeur


Les flèches bleues représentent les packet streams, c'est à dire les canaux par lesquels les modules peuvent échanger des paquets au sein d'un même nœud.

Les paquets sont reçus par les entrées rcv et directement envoyés au process. Ce dernier lance l'algorithme de routage et décide sur quelle sortie xmt renvoyer le paquet.
Les temps d'attente des queues des émetteurs sont communiquées au process via des statistic wires (représentés par les flèches rouges en pointillés).

Il faut noter l'absence de modules implémentant des queues de paquets entre les récepteurs et le processeur, et entre le processeur et les émetteurs.
Par conséquent, ce modèle de nœud est un modèle parfait dans lequel les queues ont une taille infinie : leur taille n'étant pas limitée, elle peut accueillir sans exception tous les paquets reçus et émis.
Dans la réalité, les queues ont une taille fixe et relativement petite pour économiser la mémoire. Par conséquent, si une queue se remplit trop vite (à cause d'une émission ou d'une réception trop brusque), les paquets suivants ne peuvent pas être ajoutés et sont simplement détruits. Ils sont alors définitivement perdus.

5.3 Format de paquet

Pour simplifier les choses, un nouveau format de paquet a été créé et utilisé pour tous les algorithmes.

0
15
31
type
adresse source
adresse destination
coût
renforcement (bits 0-31) ...
... renforcement (bits 32-63)

Fig. 5.2 Format de paquet utilisé

5.4 Implémentation dans le process domain

5.4.1 Best Routing

L'implémentation du Best Routing est une version simplifiée de l'implémentation du n-Best Rourting que nous décrirons dans la section suivante.
La table de routage est construite à l'initialisation en utilisant l'algorithme décrit plus loin.

A la réception d'un paquet (déterminée par la condition ARRIVAL), celui-ci subit un premier traitement qui consiste à extraire la valeur du champ type, indiquant le type de paquet et donc son traitement au sein du routeur :

S'il doit faire suivre le paquet, le routeur extrait l'adresse de destination, et recherche une sortie pour ce paquet.
La consultation de la table de routage est extrêmement simple puisque le routeur ne conserve que le chemin le plus court (en termes de sauts) pour chaque destination du réseau.
Il n'existe aucun choix possible : le routeur se contente de parcourir la table de routage à la recherche d'une entrée correspondant à l'adresse de destination. Si aucune entrée correspondante n'a été trouvée, il sélectionne une sortie par défaut.
Dans le cas contraire, il lit dans la table le numéro de l'interface de sortie, place le paquet dans la file d'attente, et retourne dans le mode d'attente (idle).

Par conséquent, et à moins que la topologie du réseau ne soit modifiée durant la simulation (chute ou initialisation d'un routeur, par exemple), tous les paquets émis par un hôte A à destination d'un hôte B emprunteront exactement le même chemin.
A aucun moment il n'y a de répartition de charge sur plusieurs chemins, ni de prise en compte d'un éventuel pic de trafic sur une partie du chemin emprunté par les paquets.

Nous pouvons d'ores et déjà imaginer le comportement de l'algorithme :

Cet algorithme nous servira en quelque sorte de témoin. En effet, il représente bien le comportement des protocoles de routage "dynamiques" actuels et nous permettra d'établir des comparaisons avec les nouveaux algorithmes dits "intelligents".

5.4.2 n-Best Routing

Le principal problème des algorithmes actuels est leur manque de réactivité aux modifications de trafic apparaissant de manière sporadique sur le réseau.
Comme tous les paquets de A vers B empruntent le même chemin, les performances peuvent s'écrouler dès l'apparition d'une montée en charge.

L'algorithme présenté ici tente de répartir la charge en distribuant les paquets de manière probabiliste sur toutes les interfaces possibles.
Dans ce but, il est nécessaire de calculer les n plus courts chemins permettant d'atteindre une certaine destination.

L'algorithme présenté au chapitre 3, et permettant de calculer les k plus courts chemins, présente deux défauts du fait qu'il ne tient compte d'aucune contrainte :

Le problème des boucles peut être résolu facilement en modifiant l'algorithme de la figure 3.1 de la manière suivante :
Rappelons que l'étape 2 consiste à ajouter, dans l'arbre de calcul, tous les nœuds vj voisins du nœud traité i.
Il suffit ici d'introduire une condition à l'ajout de chaque nœud : pour chaque nœud vj, on parcourt le chemin à sens inverse en partant de i, jusqu'à atteindre le nœud source. Si le nœud vj se trouve déjà sur le chemin, on ne l'ajoute pas dans l'arbre.

/* XXX */

Rappelons une remarque émise au chapitre 3 : l'algorithme de calcul des k plus courts chemins découvre le chemin complet menant d'une source à une destination, mais le routeur ne conserve dans sa table de routage que les informations suivantes :

En d'autres termes, le routeur effectue tout le calcul uniquement pour savoir sur quelle interface il devra faire suivre le paquet. Par conséquent, d'un point de vue local, des chemins différents peuvent apparaître identiques aux yeux d'un routeur s'ils empruntent tous la même ligne de sortie.
Le calcul des k plus courts chemins est alors inutile puisque le routeur n'empruntera qu'une seule sortie et n'aura pas l'occasion d'explorer les autres.
Certes ces sorties mises à l'écart font emprunter des chemins qui apparaissent plus longs au moment du calcul, mais ces chemins pourraient tout à fait devenir optimaux si une montée en charge apparaît sur les parcourt sélectionnés.

Nous avons donc besoin d'un mécanisme qui assure que les k chemins calculés soient tous différents les uns des autres : ainsi, une montée en charge sur l'un aura moins de chance de se faire sentir sur un autre s'ils passent par des liens différents.

Une solution consisterait à imposer une seconde contrainte à l'algorithme : les k chemins calculés doivent être disjoints.
Nous verrons par la suite que cette solution est inutile, voire même inadaptée dans certaines conditions.

Prenons pour exemple le réseau de la figure 5.4 et supposons que le routeur A cherche à calculer les deux plus courts chemins disjoints menant au routeur H.

Fig. 5.4 Problèmes du calcul des chemins disjoints


Le routeur déroule l'algorithme, et ajoute C et B dans son arbre de calcul. Supposons qu'à la seconde itération, il choisisse le routeur C pour continuer le calcul (les coûts de B et C étant identiques).
A continue la construction de l'arbre et atteint H pour la première fois. Il considère alors que le plus court chemin coûte cinq sauts et passe par {A, C, D, I, G, H}.
Il continue et explore le chemin passant par B. Il tente alors d'ajouter D (voisin de B) à son arbre, mais l'opération est impossible puisque les chemins doivent être disjoints et que le premier chemin passe déjà par D.
Par conséquent le calcul se termine et le routeur considère que :

Ce qui est complètement faux. Si B avait été choisi avant C dans le calcul, l'algorithme aurait pu trouver les deux chemins suivants :

Suivant des choix arbitraires, les résultats peuvent donc être radicalement différents.

En fait, on s'aperçoit que le calcul de chemins disjoints n'est pas adapté au monde des réseaux :
un paquet dans un réseau ne peut pas être comparé à un robot cherchant son chemin dans un labyrinthe, parce que contrairement au robot, il ne décide pas du chemin qu'il va prendre : cette décision est prise à chaque fois qu'il atteint un routeur. Par conséquent, il est inutile pour un routeur de chercher un chemin exact jusqu'à la destination, puisqu'il n'a aucun moyen de faire savoir au routeur suivant quel chemin exact il a choisi.

Par conséquent, il est préférable pour un routeur de savoir quelles interfaces lui permettront d'atteindre la destination, et quelles autres ne le permettront pas :
Nous devons donc déterminer, pour chaque interface du routeur, le plus court chemin menant à destination.
De cette manière, on maximise les chances d'explorer tout le réseau et on évite les problèmes liés au calcul de chemins disjoints.

Le n-Best Routing utilise cette technique pour router les paquets. Son implémentation dans le Process Domain ressemble beaucoup à celle du Best Routing et nécessite la création de 7 états principaux :

La phase d'initialisation (init) est exécutée une seule fois au début de la simulation : elle permet au routeur de :

L'étape de voisinage permet à chaque routeur de signaler sa présence auprès de ses voisins. En effet, la première phase leur a permis de découvrir les réseaux auxquels ils sont connectés, mais ils ne connaissent toujours pas l'adresse des routeurs situés à proximité.
L'émission d'un paquet de voisinage sur toutes les interfaces permet de résoudre ce problème. La seule information importante transportée par ce paquet est l'adresse locale du routeur.

La phase d'initialisation terminée, les routeurs se mettent en état d'attente (idle).

En recevant ce type de paquet (TOPO), un routeur extrait l'adresse de l'émetteur, et met à jour sa base de données, puis construit un paquet de topologie qu'il envoie sur toutes ses interfaces actives.
Un paquet de topologie indique l'existence d'un lien entre deux routeurs du réseau, les adresses de ces routeurs étant contenues dans les champs source et destination.

La réception d'un tel paquet provoque la même action qu'un paquet de voisinage : mise à jour de la base de données et propagation du paquet sur les autres interfaces actives.
Cependant, un mécanisme est prévu pour éviter que les paquets de topologie soient détruits dès qu'ils sont inutiles (c'est à dire dès que tous les routeurs ont pris connaissance de l'information) : le paquet n'est pas réémis s'il contient des informations déjà présentes dans la base de données du récepteur.
Si la condition MODIF_TOPO est réalisée (si la base de données à été modifiée), l'automate passe dans l'état modif_topo, recalcule les tables de routage, inonde l'information sur toutes ses interfaces et retourne dans l'état idle (oisif) pour attendre l'arrivée d'un nouveau paquet.
Si la condition n'est pas vérifiée, la propagation du paquet est inutile et l'automate passe directement à l'état idle.

Fig. 5.5 Le Process Model du n-Best Routing

Le calcul des k plus courts chemins est réalisé en respectant les contraintes évoquées précédemment. Lorsqu'un nouveau chemin est découvert, on crée une entrée dans la table de routage. L'enregistrement du chemin complet étant inutile, seuls l'interface locale et le coût du chemin sont sauvegardés.

La dernière partie de l'automate concerne le routage proprement dit : par défaut, la réception d'un paquet fait passer le routeur dans l'état routage.
Il extrait alors l'adresse de destination du paquet, puis effectue une recherche linéaire dans la table de routage.

Une entrée dans la table est définie comme suit :

	#define MAX_INTERFACE 4

	struct table_routage
	{
		/* Adresse de destination */
		int destination;
		/* Nombre de chemins calculés */
		int nbre_chemins;
		/* Index de l'interface de sortie */
		int sortie[MAX_INTERFACE];
		/* Cout du chemin (Calculé par l'algo du plus court chemin) */
		int cout[MAX_INTERFACE];
	};

La recherche prend fin lorsque le routeur a trouvé une entrée correspondant au sous-réseau de destination. Il reste encore à choisir un chemin parmi les nbre_chemins calculés.
Pour des raisons de commodité, les chemins sont classés par ordre croissant dans les tableaux sortie[] et cout[].
Le choix se fait de la manière suivante :
On assigne la probabilité P au chemin le plus court et (1 - P) à l'ensemble des autres chemins, puis on tire un chiffre au hasard, compris entre 0 et 1. Cette valeur permet alors de sélectionner un chemin dans la liste.
Ainsi, tous les chemins calculés sont explorés de manière probabiliste. En donnant à P une valeur suffisamment grande, on s'assure que la plupart des paquets emprunteront le chemin considéré comme optimal.

On peut s'attendre à de piètres performances de la part de cet algorithme dans le cas d'une faible charge sur le réseau : en effet, bien qu'une majorité emprunte le meilleur chemin, les autres explorent d'autres parties du réseau, ce qui se révèle inutile.

En revanche, si un pic de trafic apparaît sur un lien emprunté par le plus court chemin, le n-Best Routing présentera probablement des performances supérieures au Best Routing puisque certains paquets emprunteront des chemins alternatifs.

5.4.3 QRouting

5.4.3.1 Implémentation

Comme tous les modèles de routeurs créés pendant le stage, le modèle implémentant l'algorithme du QRouting comporte quatre entrées (rcv) et quatre sorties (xmt). Les émetteurs et récepteurs sont reliés deux à deux (rcvi avec xmti) pour former une liaison bidirectionnelle.
Enfin, les émetteurs sont reliés au process via des statistic wires, ce qui permet au process de connaître à tout moment le délai passé dans la file d'attente.

Aucune modification n'a été apportée à l'implémentation décrite dans [Tillier].
J'ai simplement modifié le code de telle façon qu'il utilise le format de paquet créé pour les simulations (l'implémentation précédente utilisait une entête IPv6 non standard).

La figure suivante montre le processus du routeur sous la forme d'une machine à états finis.

Fig. 5.6 Le Process Model du QRouting

Après initialisation, le routeur attend l'arrivée de paquets. A l'arrivée d'un paquet (indiquée par l'évènement ARRIVAL), le routeur détermine son type en lisant la valeur du champ type (initialement, le type du paquet était contenu dans le champs TOS de l'entête IPv6).

Un traitement différent est effectué en fonction du type de paquet :

La table de routage comporte une entrée pour chaque destination du réseau. Chaque entrée contient les délais pour chaque interface du routeur.
L'implémentation est alors très simple et comporte 5 états principaux :

INITIALISATION : cette phase permet principalement de détecter les interfaces actives.

DONNEES : lorsque le routeur reçoit un paquet de données, il met en marche l'algorithme de routage.

REQUETE : pour connaître le délai total pour une destination à partir de toutes les interfaces, une exploration est nécessaire. Un paquet de requête est envoyé régulièrement par les routeurs connectés directement à un sous réseau. Ce paquet ressemble à un paquet de renforcement, avec un signal égal à zéro. Les routeurs voisins reçoivent ce paquet, et s'il apporte une bonne nouvelle, ils mettent à jour leur table. Une recherche du plus court délai est alors effectuée, prenant compte du temps des files d'attente, puis le paquet est construit avec la nouvelle valeur calculée, et envoyé sur toutes les interfaces autres que l'interface de réception.

SIGNAL : le routeur se trouve généralement dans cet état lors de la phase d'initialisation. Le paquet indique l'adresse d'un réseau auquel le routeur est directement connecté. Une nouvelle entrée est créée dans la table de routage, avec un délai égal à 0 pour l'interface de réception.

RENFORCEMENT : le routeur extrait la valeur du signal de renforcement T, ainsi que l'adresse de destination d pour laquelle la fonction de renforcement doit être mise à jour.
La fonction de renforcement pour l'interface de réception i est alors modifiée de la manière suivante :

Q(i,d) = Q(i,d)( 1 - h) + h(T + s)

s étant le temps de transmission pour atteindre le prochain routeur.

5.4.3.2 Nécessité de l'exploration

Pour fonctionner de manière optimale, le QRouting nécessite la mise ne place d'une méthode d'exploration des chemins existants.
En effet, un routeur ne recevra d'informations que des chemins qu'il visite. Or il ne visitera que les chemins qui lui paraissent avoir le plus court délai. Un autre chemin peut donc devenir plus intéressant (par une diminution du trafic, par exemple) sans que le routeur en soit informé, tout simplement parce qu'il n'essayera jamais ce chemin, persuadé qu'il est toujours sous-optimal.

Illustrons ce problème par un exemple : la figure 5.7 présente cinq routeurs implémentant le QRouting sans mécanisme d'exploration :

Fig. 5.7 Nécessité d'exploration

A l'origine, le trafic est nul sur le réseau. A reçoit alors des données à router à destination de C. Supposons que A choisisse le chemin A-D-E-C qu'il considère être le plus rapide.
Par la suite, le lien E-C sature à cause d'une autre communication. Voyant les temps d'acheminement augmenter (grâce aux paquets de renforcement envoyés par E puis par D), A décide d'emprunter le chemin A-B-C pour acheminer les paquets vers C.
Cette décision est la bonne, puisqu'elle permet de diminuer le trafic sur la ligne saturée, et d'en emprunter une autre qui effectivement, à cet instant précis, est optimale.
Imaginons maintenant que le trafic redevienne normal sur le lien E-C. Le routeur A continue à passer par B pour atteindre C, alors que dorénavant, ce chemin est sous-optimal. Malheureusement, A n'a aucun moyen de s'en apercevoir, parce qu'il n'explore plus la liaison A-D-E-C, et ne peut pas faire remonter d'informations en sa provenance.
A peut continuer pendant longtemps à emprunter un chemin sous-optimal sans s'en apercevoir : en fait, il faut attendre l'apparition d'un pic de trafic sur un des lien du chemin A-B-C pour que le routeur A rebascule vers la liaison A-D-E-C.
On voit donc que le QRouting, sans mécanisme d'exploration, se révèle inadapté dans le cas d'une forte baisse de trafic sur une liaison.
En revanche, il réagit parfaitement lorsqu'un pic de trafic est détecté.

5.4.3.3 Méthodes d'exploration

L'exemple précédent montre que la mise en place d'un mécanisme d'exploration est indispensable.

Il existe trois grandes familles de solutions à ce problème :

Les méthodes précédentes ne sont pas adaptées à un environnement dynamique. C'est pourquoi une nouvelle méthode d'exploration a été developpée.

5.4.3.4 Méthode d'exploration du QRouting

Comme nous l'avons vu, les méthodes précédentes ne révèlent inadaptées, voire inefficaces pour un environnement changeant en permanence, et dont les contraintes de délai sont très fortes.
La méthode d'exploration du QRouting repose sur le fait qu'à l'origine, seuls les routeurs directement connecté à un sous-réseau destination ont une idée exacte du délai pour l'atteindre.
Par conséquent, plutôt que de faire en sorte que les routeurs s'échangent entre eux des valeurs qui ne sont que des estimations, où explorent au hasard le réseau, il paraît préférable de faire remonter l'information en partant de la destination, et vers la source : en partant du point d'arrivée, l'information (le délai d'acheminement) se propage petit à petit sur tout le réseau, jusqu'à ce que tous les routeurs soient informés, et cette fois avec une estimation du délai à peu près exacte.

C'est d'ailleurs sur ce principe que fonctionnent les paquets de renforcement du QRouting : à l'origine, un routeur source n'a aucune idée de l'interface à emprunter pour atteindre une destination. Les paquets circulent alors d'un routeur à l'autre, avec plus ou moins de succès, jusqu'au moment où un routeur directement connecté au sous réseau de destination parvient à remettre le paquet à son destinataire. Ce routeur fera alors remonter l'information au routeur précédent (via un paquet de renforcement avec une valeur faible), qui à son tour saura quel chemin emprunter, etc…
La valeur du signal remonte alors progressivement du destinataire vers l'émetteur.

En plus des paquets de renforcement classiques, vient s'ajouter un second mécanisme : chaque routeur directement connecté à un sous réseau devra régulièrement émettre un paquet de renforcement spécial, à destination de tous ses voisins.
A la réception de ce paquet, les voisins mettent à jour leur fonction de renforcement en remplaçant l'ancienne par la nouvelle (h = 1), puis émettent à leur tour un renforcement sur toutes leurs interfaces (sauf celle par laquelle le renforcement est arrivé).
Une technique est aussi mise en place pour stopper la propagation de ces paquets : si le paquet apporte une " mauvaise nouvelle " (c'est à dire une valeur de renforcement supérieure à la valeur actuelle), le paquet est immédiatement détruit.

5.4.4 n-Best QRouting

Comme nous le verrons lors des simulations, les routeurs implémentant l'algorithme QRouting éprouvent des difficultés à faire converger leurs tables au moment de l'initialisation.
A l'origine, les routeurs ne connaissent absolument pas la topologie du réseau et doivent attendre l'arrivée de paquets d'exploration pour découvrir de nouvelles destinations et se faire une idée du délai pour les atteindre.
Cette phase de convergence relativement longue entraîne alors des temps de remise très élevés puisque les paquets sont routés au hasard et empruntent des chemins qui ne sont pas optimaux.

L'idée du n-Best QRouting est de réduire cette phase de convergence en se basant sur le calcul des k plus courts chemins pour chaque destination connue.
Ainsi, à l'initialisation, les routeurs construisent une base de données décrivant la topologie du réseau, et l'utilisent pour déterminer les meilleurs chemins.
L'algorithme de routage prendra alors appui sur ces calculs tant que les tables du QRouting n'ont pas convergé.

Le Process Model du n-Best QRouting apparaît comme une combinaison du n-Best Routing et du QRouting :

Fig. 5.8 Le Process Model du n-Best QRouting

Comme dans le n-Best Routing, les phases d'initialisation et de voisinage préparent le routeur et signalent sa présence sur toutes ses interfaces actives.

A la réception d'un paquet de voisinage ou de topologie, la base de données est mise à jour, les tables sont recalculées et le paquet est envoyé sur toutes les autres interfaces.

Si le paquet est un paquet de données, il faut le faire suivre : le routeur extrait l'adresse de destination et enregistre le numéro de l'interface d'arrivée.


La décision de routage peut alors se faire de deux manières :

La table de routage doit donc être modifiée pour enregistrer à la fois les données calculées par l'algorithme des k plus courts chemins et les signaux de renforcement du QRouting :

	struct table_routage
	{
		int destination;
		int nbre_chemins;
		/* Index de l'interface de sortie */
		int sortie[MAX_PATH];
		/* Cout du chemin (Calculé par l'algo du plus court chemin) */
		int cout[MAX_PATH];
		/* Delai calculé par le QRouting */
		double delay[MAX_PATH];
	};

Le tableau delay[] a pour rôle de sauvegarder les valeurs des signaux de renforcement calculés à partir des paquets de renforcement envoyés par les routeurs voisins.

Nous allons ici tester une technique d'exploration différente de celle employée par le QRouting.
Il s'agit de l'exploration probabiliste, qui consiste à donner une probabilité à chaque route menant à une destination.
Ainsi, le plus court délai aura une probabilité Pmax, et l'ensemble des autres chemins, une probabilité (1 - Pmax). Un nombre tiré au hasard déterminera quel chemin a été choisi. De cette manière, les paquets atteignent leur destination avec un délai proche de l'optimal, tout en assurant une bonne exploration des chemins non optimaux.

Il faut cependant veiller à choisir une bonne valeur pour Pmax :

Le routeur doit donc choisir un chemin dans une liste, au lieu de sélectionner celui qui présente le plus court délai (comme c'est le cas avec la méthode d'exploration du Qrouting).
Par conséquent, il faut modifier des conditions d'envoi des paquets de renforcement :
Par exemple, il est possible qu'un paquet à destination d'un sous-réseau D arrive sur l'interface qui présente le meilleur délai pour D, le routeurs précédent ayant choisi un chemin alternatif dans un but d'exploration.
Dans ce cas il faut :

5.4.5 Routage expérimental

Cet algorithme est né des constatations suivantes :

L'idéal serait donc de combiner les avantages des ces deux techniques. Ainsi ce protocole :

Son implémentation est extrêmement simple :

Fig. 5.9 Le Process Model de l'algorithme expérimental

A l'initialisation, le routeur découvre ses interfaces actives, et arme un temporisateur qui expiera 60 secondes plus tard.
S'il est connecté à un sous-réseau, il envoie un paquet d'information sur toutes ses interfaces. Ce paquet indique à ses voisins l'adresse du sous-réseau qu'il peut atteindre, et son coût (ici il vaut 0.0 + delai_queue puisqu'il s'agit d'une remise directe).

A la réception d'un paquet d'information (INFO), le routeur lit l'état de ses files d'attente, puis met à jour sa table en s'appuyant sur les informations transportées par le paquet.
Afin d'augmenter la réactivité du routeur, une entrée dans la table de routage contient le meilleur délai pour chaque interface, et pas seulement le meilleur délai (comme le ferait RIP).
De cette manière, à chaque modification de la table, on peut trouver le meilleur délai parmi la liste et déterminer la meilleure ligne de sortie pour une destination.

Il faut ensuite prévoir la propagation de l'information sur le réseau :
Si la réception d'un paquet d'information entraîne l'élection d'une meilleure interface, le paquet est envoyé à tous les voisins.

Dans le cas contraire, le paquet est envoyé seulement si le délai a évolué de manière significative depuis le dernier calcul : par exemple, si la différence entre le nouveau et l'ancien délai est supérieure à 20 %.

Les tables de routage sont régulièrement recalculées, pour que le routeur se base sur des temps d'attente qui soient les plus récents possibles.
Ainsi, à l'expiration du temporisateur (fixé par exemple à 30 secondes), le routeur réalise une opération similaire à celle engendrée par la réception d'un paquet d'information :
Après avoir lu les délais de ses files d'attente, il recalcule les meilleurs délais pour chaque destination présente dans sa table, et envoie un paquet d'information à ses voisins si les conditions citées précédemment sont réunies.

Pour limiter l'apparition de boucles lors de modifications dans les tables de routage, chaque routeur doit connaître, pour chaque destination, les routeurs voisins qui le considèrent comme le meilleur prochain saut (next hop). Un routeur ne doit pas réémettre un paquet vers un voisin qui l'a sélectionné comme prochain saut.

L'étape de routage est simple : on recherche l'entrée correspondant à l'adresse de destination, et on sélectionne, parmi la liste contenue dans cette entrée, l'interface qui présente le plus court délai, compte tenu de l'état des files d'attente locales. L'envoi de renforcement n'est pas nécessaire.

Ce protocole engendre donc un trafic de routage similaire à celui de RIP, et beaucoup plus faible que celui du QRouting.
Cependant, on peut s'attendre à une moins bonne réactivité par rapport au QRouting : les valeurs de files d'attente ne sont pas lues en permanence, et le type même de routage (à vecteur de distance, en quelque sorte) entraîne l'apparition de boucles difficilement décelables et qui peuvent nuire aux délais de transit de façon significative, du moins pendant une courte période de convergence.

CHAPITRE 4 - OPNET
CHAPITRE 6 - Simulation des algorithmes

Juin 2003