L'implémentation des algorithmes précédents n'avait d'autre objectif que leur simulation et l'évaluation de leurs performances dans des situations considérées comme réelles.
6.1 Réseau utilisé
La figure suivante montre le réseau utilisé pour les simulations :
Fig. 6.1 Réseau utilisé pour la simulation
Il est composé de 32 routeurs. Les zones Est et Ouest sont très
denses mais elles ne sont interconnectées que par deux liens :
- Le lien 15-16 (c'est à dire situé entre les routeurs 15 et 16)
- La zone Nord constituée de routeurs à deux interfaces.
6.2 Conditions de simulation
Les tests vont porter sur
l'évolution du temps de transit (end-to-end delay) de paquets échangés
entre deux hôtes : le nud 100 jouera le rôle d'un client et
émettra régulièrement des paquets à destination
d'un serveur, le nud 101.
A la réception d'un paquet, le nud 101 calcule le temps de transmission
et l'enregistre dans une base de données.
A la fin de la simulation, ces données enregistrées pourront être
étudiées et permettront d'évaluer les performances de chaque
algorithme.
On réalise une simulation pour chaque algorithme dans des conditions de trafic différentes :
6.3 Résultats
Les résultats suivants ont été obtenus en lançant des simulations pour les cinq types de routeurs créés. La durée de la simulation (6 heures) permet de visualiser le comportement de chaque algorithme en fonction des situations, notamment des brusques montées en charge.
6.3.1 Conditions de trafic faible
La figure suivante indique le temps de transit (end-to-end delay) moyen mesuré par le nud 101, sur des paquets envoyés par le nud 100.
Fig. 6.2 Temps de transit moyen pour un trafic faible
A l'exception du n-Best
Routing (courbe en rouge), les temps sont pratiquement identiques et constants
au cours de la simulation, ce qui indique que la plupart des paquets empruntent
le chemin optimal passant par le lien 15-16.
Comme prévu, le temps de convergence du QRouting est largement supérieur
aux autres algorithmes : ses temps moyens se stabilisent après environ
20 minutes de simulation.
Enfin, signalons les piètres performances du n-Best Routing, dont les temps moyens sont 30 % plus élevés. Les nombreux paquets explorant les chemins alternatifs et sous-optimaux expliquent ce résultat.
6.3.2 Conditions de trafic fort
Examinons à présent le comportement des routeurs lorsque le lien 15-16 est soumis à un trafic fort pendant toute la durée de la simulation.
Fig. 6.3 Temps moyens pour un trafic fort
Sous ces conditions, de grandes disparités apparaissent :
Les routeurs implémentant
le Best Routing (en bleu) ignorent complètement la montée en charge
sur les routeurs 15 et 16 et continuent à emprunter la route passant
par le lien 15-16 ce qui se traduit par une augmentation conséquente
du temps de transit entre les nuds 100 et 101.
Malgré les nombreux paquets empruntant le chemin secondaire (au Nord
du réseau), le n-Best Routing (en rouge) ne présente pas de meilleures
performances.
En revanche, le QRouting
(en vert) parvient à détecter le pic de trafic. Malgré
un temps de convergence toujours élevé, les routeurs remettent
les paquets plus rapidement que les algorithmes précédents.
Le n-Best QRouting fait même encore mieux et présente des temps
moyens qui sont parfois inférieurs d'1 ms par rapport au Best Routing.
Enfin signalons l'extrême difficulté avec laquelle notre algorithme expérimental converge dans ces conditions : il semble que l'apparition de boucles sur le réseau ait pour conséquence des temps de transit quelquefois supérieurs à 300 ms
6.3.3 Comportement face à des pics de trafic
Pendant cette simulation, nous avons déclenché un pic de trafic entre les routeurs 15 et 16, une heure après le début de la simulation. Le trafic entre les nuds 102 et 103 a été totalement interrompu deux heures plus tard.
Fig. 6.4 Temps de transit lors de pics de trafic
Pendant le pic de trafic
(de 1 heure à 3 heures), les temps du QRouting se confondent avec ceux
du Best Routing. En revanche, ceux du n-Best QRouting deviennent rapidement
meilleurs.
Dès le début de la quatrième heure, tous les algorithmes
réagissent à la diminution du trafic. Les temps du QRouting et
du n-Best QRouting restent inférieurs aux autres et tendent à
converger.
Il faut toutefois noter que les temps de transit utilisés pour construire
ces graphes sont des temps moyens depuis le début de la simulation :
ceci explique pourquoi, après la quatrième heure, les temps diminuent
mais restent supérieurs aux valeurs enregistrées pendant la première
heure.
Pour mesurer de manière significative la réactivité du
QRouting face à de brefs pics de trafic, nous avons réalisé
une seconde simulation d'une durée d'une heure avec un pic de trafic
de dix minutes.
La figure 6.5 indique le résultat de cette simulation :
Fig. 6.5 Temps de transit avec un pic de trafic de 10 minutes
On voit clairement l'écroulement des performances du Best Routing et du n-Best Routing quand la charge du réseau devient importante (le pic commence dix secondes après le début de la simulation, et s'arrête après dix minutes).
Le QRouting (courbe verte) présente des délais moyens inférieurs d'une milliseconde : il réagit rapidement à la montée en charge et route les paquets vers un chemin alternatif. Pendant le pic de trafic, la pluspart des paquets émis par le nud 100 empruntent la partie Nord du réseau pour atteindre le nud 101 et ainsi éviter les liens congestionnés. De plus, il converge plus rapidement que l'algorithme de routage classique lorsque la charge redevient normale.
Enfin, le n-Best QRouting (courbe cyan) présente clairement les meilleures performances. Après une période d'adaptation, les délais sont largement inférieurs aux délais induits par les autres protocoles. L'algorithme sélectionne bien le chemin optimal en condition de charge élevée, mais aussi lorsque le pic disparaît : c'est l'algorithme qui converge le plus rapidement vers la valeur optimale.
Enfin, la figure suivante
montre le comportement des algorithmes face à deux pics de trafic successifs.
Pendant une heure, on introduit deux montées en charge du réseau
: le premier pic commence dix secondes après le début de la simulation
et s'arrête dix minutes plus tard.
Trois minutes après, un second pic d'une durée de dix minutes
fait son apparition.
Fig. 6.6 Temps de transit avec deux pics de trafic successifs
Ici encore, on ne peut que
constater l'efficacité du QRouting (courbe verte) face aux algorithmes
classiques (courbe bleue).
Le n-Best Qrouting présente une fois de plus les meilleures performances
: son adaptation est extrêmement rapide, et l'apparition du second pic
est à peine perceptible.
Remarque : nous n'avons
pas pris en compte les résultats du cinquième algorithme (routage
expérimental) dans les deux derniers graphes : son extrême difficulté
à converger lors de la modification des tables de routage fait que ses
performances sont largement en dessous de celles des autres algorithmes.
Il apparaît de façon évidente que des améliorations,
ainsi qu'une mise au point du protocole sont nécessaires pour limiter
l'apparition de boucles qui nuisent considérablement à son efficacité.
CHAPITRE 5 - Implémentation des algorithmes |
CHAPITRE
7 - Implémentation dans un routeur IP
|
Juin 2003