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 nud 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 nud.
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 nud 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
|
||||||||||||||||||||||||
|
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 nuds vj voisins du nud traité i.
Il suffit ici d'introduire une condition à l'ajout de chaque nud
: pour chaque nud vj, on parcourt le chemin à sens inverse en partant
de i, jusqu'à atteindre le nud source. Si le nud 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 :
Il faut cependant veiller à ce que P ne soit pas trop petit, sinon les chemins sous-optimaux seraient empruntés dans la plupart des cas, ce qui nuirait à la performance globale du système. Au contraire, si P est trop grand, l'agent n'explore pas assez les autres chemins, et risque de ne pas être informé de l'existence d'un plus court chemin.
Cette méthode
présente un défaut pour le problème du QRouting : si
cet algorithme de routage n'était destiné qu'à acheminer
des paquets de données sans contrainte de délai, il n'y aurait
aucun problème puisque les temps moyens seraient proches de l'optimal.
Or le QRouting est destiné à router des paquets multimédia
avec des contraintes temps réel (voix, vidéo), qui nécessitent
une arrivée dans l'ordre et avec le plus court délai. Les
routeurs ne peuvent donc pas se permettre de sacrifier quelques paquets,
de taille conséquente, dans un seul but d'exploration.
L'article Packet
routing in dynamically changing network : a reinforcement learning approach
[Boyan Littman] traite de ce problème en apportant la solution
du full echo :
Avant de prendre une décision sur le chemin à emprunter, un
routeur envoie d'abord une requête à tous ses voisins, leur
demandant leur valeur de renforcement.
De cette manière, il est informé en permanence de l'état
de tous les chemins possibles, et a plus de chance de trouver le chemin
optimal.
Cette méthode
a cependant le désavantage de surcharger le réseau : dans
le cas d'un routeur à 4 interfaces, celui-ci enverra, à chaque
fois qu'il doit router un paquet, une requête sur toutes les interfaces
(sauf sur l'interface de réception).
De plus cette méthode permet uniquement de détecter une baisse
de charge sur un routeur voisin : si la baisse de charge intervient sur
un lien plus éloigné du réseau, l'amélioration
ne sera pas détectée par cette méthode :
Reprenons l'exemple illustré par la figure 5.7, au moment où le pic de la liaison E-C disparaît. En utilisant la méthode du full echo, A reçoit les valeurs de renforcement de D, qui restent toujours élevées, puisque D n'a toujours pas routé de paquets à destination de E et par conséquent, n'a pas pu l'interroger et s'apercevoir que ses temps d'acheminement ont considérablement diminué. Par conséquent, même en utilisant cette méthode, A continue à emprunter un chemin sous optimal.
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