CHAPITRE 6
Simulation des algorithmes

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 nœud 100 jouera le rôle d'un client et émettra régulièrement des paquets à destination d'un serveur, le nœud 101.
A la réception d'un paquet, le nœud 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 nœud 101, sur des paquets envoyés par le nœud 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 nœuds 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 nœuds 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 nœud 100 empruntent la partie Nord du réseau pour atteindre le nœud 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