Etude comparée de modèles de routage multi-chemins pour l’ingénierie de trafic

03/08/2016
OAI : oai:www.see.asso.fr:545:2009-2:17219
DOI : You do not have permission to access embedded form.

Résumé

Etude comparée de modèles de routage multi-chemins pour l’ingénierie de trafic

Métriques

22
5
940.79 Ko
 application/pdf
bitcache://2d7990e87cb8345a0524f7a137e1edbdf5bbb253

Licence

Creative Commons Aucune (Tous droits réservés)
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/545:2009-2/17219</identifier><creators><creator><creatorName>Khodor Abboud</creatorName></creator><creator><creatorName>Ahmed Rahmani</creatorName></creator></creators><titles>
            <title>Etude comparée de modèles de routage multi-chemins pour l’ingénierie de trafic</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2016</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Wed 3 Aug 2016</date>
	    <date dateType="Updated">Wed 3 Aug 2016</date>
            <date dateType="Submitted">Sat 24 Feb 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">2d7990e87cb8345a0524f7a137e1edbdf5bbb253</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>28973</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

Etude comparée de modèles de routage multi-chemins pour l'ingénierie de trac Khodor ABBOUD, Ahmed RAHMANI Laboratoire d'Automatique, Génie Informatique et Signal Ecole Centrale de Lille, BP 48, 59651 Villeneuve d'Ascq Cedex, France {khodor.abboud,ahmed.rahmani}@ec-lille.fr Résumé Cet article présente une évaluation du compor-tement d'algorithmes de routage multi-chemins (PEMS,LBWDP) pour l'ingénierie de trac et l'équilibrage decharge sur un réseau MPLS (MPLS-TE). Nous comparonsnotamment la capacité de ces algorithmes à équilibrer lacharge tout en faisant de la diérentiation de trac. Ces al-gorithmes seront appliqués sur des grandes topologies, quis'approchent du réseau réel, pour mesurer l'impact de leurcomplexité respective et donc la capacité à les déployer surdes réseaux de grande taille (scalabilité). En utilisant destopologies générées par BRITE avec de nombreux cheminsalternatifs, on peut réaliser des simulations sur des réseauxdont la topologie ore une complexité etvariété de cheminscomparable à ce que l'on peut trouver dans un réseau defournisseur d'accès internet (FAI). Cela permet d'évaluer laqualité oerte de bout-en-bout par les algorithmes de rou-tage dynamique proposés. Mots-clésEvaluation de performances, Génération des to-pologies, MPLS, Ingénierie de trac, DiServ, Routagemulti-chemins, Simulations I. Introduction La croissance des débits d'accès et la convergence des services dits "triple play" (voix/visioconférence, télévi- sion/vidéo à la demande) sur une infrastructure IP en- trainent une augmentation considérable des volumes de trac IP ainsi que de nouvelles contraintes en termes de qualité de service (QdS) [1]. Une solution possible consiste à exploiter des techniques d'ingénierie de trac pour mieux répartir les ux dans l'ensemble du réseau d'un fournisseur d'accès internet (FAI). L'expression "Ingénierie de trac" désigne l'ensemble des mécanismes de contrôle de l'achemi- nement du trac dans le réseau an d'optimiser l'utilisation des ressources et de limiter les risques de congestion. L'ob- jectif de l'ingénierie de trac est de maximiser la quantité de trac pouvant transiter dans le réseau, tout en mainte- nant la qualité de service (bande passante, délai ...) oerte aux diérents ux de données. Il existe plusieurs méthodes d'ingénierie de trac pour les réseaux IP, parmi lesquelles on trouve celle proposée par l'IETF [2] qui est basée sur l'utilisation de la technologie MPLS [3] (MultiProtocol La- bel Switching). Cette technologie permet d'établir des che- mins entre source et destination au travers d'un réseau. Par rapport à un protocole comme IP, elle permet d'intro- duire une technique permettant d'apporter de la connexion à un protocole fonctionnant en mode non connecté, ce qui est nécessaire pour assurer la même qualité de service de l'émetteur au destinataire. L'objectif de cette étude est de comparer deux mo- dèles de routage dynamique par équilibrage de charge (LBWDP et PEMS) sur plusieurs chemins traversant un réseau de fournisseur d'accès internet (FAI). Les réseaux de FAI connaissent des déséquilibres de charge engen- drés par le "sh problem". Pour résoudre ce problème, il existe de nombreux algorithmes d'ingénierie de trac ba- sés sur MPLS (MPLS-TE algorithm) parmi lesquels gure LBWDP (Load Balancing with Widest Disjoint Paths) [4]. D'autre part, certains utilisateurs exigent du réseau une QdS garantie qui peut concerner un ou plusieurs critères comme le délai, la bande passante ou la gigue. Dans ce cadre, il existe de nombreux modèles appartenant à la fa- mille DS-TE (Diserv aware Trac Engineering)[5] parmi lesquels PEMS (PEriodic Multi-Step routing algorithm for DS-TE)[6]. Dans [7,8,9] nous avons montré que ces deux modèles semblent plus performants que d'autres comme MATE [10] ou LDM [11]. Pour cela, nous proposons de les évaluer sur des topologies plus complexes (plusieurs cen- taine de routeurs) et selon diérents scénarios an de dé- terminer s'ils restent performants et s'ils peuvent être dé- ployés sur des réseaux de grandes tailles. Pour cela, nous nous basons sur la génération de topologies de réseaux réa- listes. Cet article est organisé de la manière suivante. Après une introduction, la deuxième partie présente les deux mo- dèles LBWDP et PEMS en les repositionnant par rap- port aux propositions relatives à l'ingénierie de trac basée sur MPLS. La troisième partie présente une étude rela- tive aux générateurs automatiques de topologies. Dans la quatrième partie nous présentons notre expérimentation. La cinquième partie décrit les simulations réalisées et ana- lyse les résultats obtenus. Dans la sixième partie, nous éva- luons la structure de topologie. Enn, nous proposerons une conclusion et quelques perspectives. II. Ingénierie de traffic par routage multi-chemins A. Introduction Il existe de nombreux algorithmes de routage pour l'ingé- nierie de trac. Les algorithmes de routage multi-chemins sont schématiquement composés de deux étapes (gure 1) : le calcul de l'ensemble des chemins candidats et la répar- tition du trac sur ces chemins. L'ensemble des chemins candidats est un sous ensemble de tous les chemins entre une paire source/destination qui vérient un ensemble de e-STA copyright 2009 by see Volume 6, N°2, pp 40-49 critères de QdS comme la bande passante, le nombre de sauts, le délai. Ces critères sont généralement des critères statiques caractérisant les connexions entre routeurs. Un modèle comme WDP [12] est un algorithme de sélection des chemins candidats basé essentiellement sur les critères bande passante et nombre de sauts. La deuxième étape consiste à répartir le trac sur ces che- mins candidats. Le taux de répartition du trac sur chaque chemin candidat dépend d'une métrique basée sur plusieurs critères dynamiques comme le taux de perte de paquets, le délai mesuré, la variation du délai ... LBWDP et PEMS utilisent l'algorithme PER [8,9] comme algorithme de ré- partition du trac. Fig. 1. Schéma général du routage multi-chemins Dans les diérents modèles, on cherche à chaque instant à sélectionner le bon nombre de chemins candidats an de ne pas réduire l'ecacité de la répartition. En eet, un nombre élevé de chemins peut être pénalisant. C'est notam- ment le cas de la répartition d'une demande sur plusieurs chemins. De manière générale, si à un instant donné, il est impossible d'aecter une nouvelle demande, les modèles re- mettent alors en cause le plan de routage courant établi par l'étape de sélection des chemins candidats. B. LBWDP (Load Balancing over Widest Disjoint Paths) LBWDP [4] est un modèle de routage multi-chemins qui comprend une étape de sélection des chemins candidats eectuée par WDP [12] et une étape de répartition du trac faite par PER [8,9]. La sélection des chemins de WDP est essentiellement ba- sée sur 2 concepts : la largeur et la longueur d'un chemin. La largeur d'un chemin est un moyen pour détecter les goulots d'étranglements dans le réseau et de les éviter si possible. La longueur du chemin, contrairement à la ma- jeure partie des autres approches utilisées dans l'internet, n'est pas considérée comme une mesure directe en fonction du nombre de sauts. WDP l'exprime en fonction du taux d'utilisation des liens que comporte le chemin. WDP réa- lise l'étape de sélection des chemins candidats en se basant sur le calcul de la largeur de bande passante résiduelle de l'ensemble des chemins candidats. On sélectionne ainsi un ensemble de chemins disjoints les plus courts du point de vue nombre de sauts et dont la largeur résiduelle est supé- rieure à une limite xée par l'administrateur. Un chemin est ajouté à l'ensemble des chemins candidats si cela per- met d'accroître la largeur de cet ensemble. Par contre, un chemin est supprimé de cet ensemble si cela ne réduit pas sa largeur. LBWDP utilise l'algorithme PER pour la répartition du trac. Il comprend lui-même deux sous-étapes : le calcul d'un paramètre de sélection pour la répartition du trac par la diérence entre le trac désiré et le trac eectif, puis la sélection du chemin qui possède la plus grande va- leur du paramètre de sélection possédant susamment de bande passante résiduelle pour acheminer la totalité de la demande courante. Pour plus d'informations sur PER, se référer [8,9]. C. PEMS (PEriodic Multi-Step routing algorithm for DS- TE) L'IETF s'est intéressé ces dernières années au déploie- ment simultané de MPLS-TE (Trac Engineering based on MPLS) et de DiServ (Dierentiated Services) an de tirer avantage de ces deux techniques d'amélioration de la qua- lité de service dans les réseaux laires. L'intégration de ces deux technologies corresponds à la catégorie des modèles DS-TE (Diserv aware Trac Engineering ). Diérentes approches de DS-TE sont possibles. Dans ce cadre, nous avons proposé un nouvel algorithme appelé PEMS [6]. Il est utilisé pour favoriser les diérents besoins des consom- mateurs et pour fournir des services diérenciés pour les trois classes de trac d'un réseau DS-TE. Son principe gé- néral consiste à mettre en oeuvre l'équilibrage de charge par classes de trac tel que déni par Diserv. L'objectif de PEMS [6] est donc de développer une mé- thode de routage qui eectue de l'équilibrage de charge par classe de trac au niveau de chaque routeur d'entrée dans un réseau FAI. Les trois classes traitées par PEMS sont : le Service Premium (EF ou Expedited Forwarding) pour le trac sensible au délai comme le trac VoIP (Voix sur IP), le Service Garanti (AF ou Assured Forwarding) pour le trac qui nécessite une garantie de bande passante (la vidéo) ou des taux d'erreurs garantis, et le service corres- pondant au trac au mieux (BE ou Best-Eort) pour des applications comme le transfert de chiers ou la messagerie électronique. Le but principal de PEMS est donc de per- mettre à chaque trac d'être acheminé selon ses exigences en QdS. L'algorithme PEMS comporte trois étapes (gure 2) : l'étape du prétraitement, celle de la sélection de chemins candidats et celle de la répartition du trac sur les LSPs (Label Switched Path). L'étape du prétraitement consiste à extraire les meilleurs chemins entre une source et une des- tination. Elle s'eectue hors ligne. Son objectif est d'évi- ter une recherche combinatoire en ligne. Cette recherche est uniquement basée sur la topologie. La deuxième étape consiste à sélectionner des chemins candidats. Elle s'eec- tue en ligne et tient en compte des critères de bande pas- sante résiduelle et de délai mesuré pour sélectionner un sous-ensemble réduit de chemins fournis par l'étape de pré- traitement. A chaque nouvelle mise à jour des paramètres de qualité de service (Link State Update eectué par les routeurs voisins), l'ensemble des chemins candidats est re- calculé an de considérer toujours un ensemble limité de e-STA copyright 2009 by see Volume 6, N°2, pp 40-49 meilleurs chemins. Le nombre de chemins candidats rete- nus et la périodicité des mises à jour sont des paramètres xés par l'administrateur réseau. Pour la dernière étape, PEMS utilise l'algorithme PER [8,9] en l'adaptant aux diérentes classes de trac. Un nombre de chemins candidats est associé à chaque classe de trac. Ces nombres sont xés par l'administrateur ré- seau. Par exemple, sur 10 chemins, ont peut aecter les 4 chemins ayant les meilleurs délais pour acheminer le tra- c de la classe prémium. Ensuite les chemins suivants sont aectés à la classe AF et les derniers sont associés au tra- c BE. Pour chaque classe de trac, PER calcule le taux théorique de répartition sur chaque chemin de la classe. Ce taux est transformé en un taux de répartition relatif qui tient compte de la répartition eective des demandes sur les chemins considérés. Lorsqu'une demande d'une classe donnée arrive, elle est aectée au chemin ayant le taux de répartition relatif le plus grand. En eet, plus ce taux est élevé plus le chemin est sous-utilisé par rapport au plan de routage établi pour la période donnée. L'équilibrage de charge eectué par PER consiste à af- fecter toute nouvelle demande dans sa classe, au chemin le moins utilisé à l'instant donné sous réserve que son taux ré- siduel d'utilisation de bande passante soit compatible avec le débit requis par la demande. Si ce n'est pas le cas, le routeur force une mise à jour des paramètres de qualité de service (délai et bande passante résiduelle) avant la n de la période en cours. Dans ce cas, on relance l'étape de calcul des chemins candidats et on recalcule les taux. Fig. 2. Les trois étapes du PEMS L'objectif de PEMS est de minimiser l'utilisation maxi- male des liens exactement comme LBWDP tout en dié- rentiant les chemins en fonction de la qualité de service requise par la classe de trac de la demande courante. La gure 3 présente certaines caractéristiques de LBWDP et PEMS en termes de structure et d'objectif. Fig. 3. Caractéristiques de LBWDP et PEMS D. Passage à l'échelle des modèles et complexité des algo- rithmes La mesure de la complexité d'un modèle permet de pré- ciser sa capacité de se déployer sur un réseau complexe par sa taille comme internet. Plus la complexité du modèle est faible, plus son implémentation réduit l'utilisation des ressources du réseau. Intserv [13] bien qu'intéressant en la- boratoires se révèle inadapté lors du passage à l'échelle. Le passage à l'échelle dépend de deux facteurs : l'étendue du déploiement et la complexité des algorithmiques mettant en oeuvre le modèle. Sur le plan du déploiement, LBWDP et PEMS réduisent le phénomène de taille car ils nécessitent une implémenta- tion complète que sur les routeurs d'entrée. En eet, dans le cas de LBWDP, une fois le chemin sélectionné dans le routeur d'entrée, le rôle des routeurs du coeur du réseau se limite à la mise en oeuvre des mécanismes de MPLS. Dans le cas de PEMS, les routeurs du coeur du réseau doivent en plus de ces mécanismes mettre en ÷uvre la diérentiation des paquets de Diserv [14]. Comme le passage à l'échelle de Diserv a été prouvé, cela ne remet pas en cause à priori le fonctionnement de PEMS. Le passage à l'échelle de nos modèles est donc fonction de la complexité des algorithmes de sélection des chemins et de la répartition de charge mis en oeuvre sur les routeurs d'en- trée. Cette complexité peut s'exprimer selon deux critères : le temps de calcul et l'espace mémoire utilisé. Dans cette étude, on s'intéresse au temps de calcul pour estimer les plans de routage après chaque Link State Update. Ce temps de calcul peut être approximé théoriquement par le nombre d'itérations dans un algorithme. La gure 4 montre la com- plexité théorique de LBWDP et PEMS selon les étapes qui les constituent. Les étapes les plus coûteuses en temps sont celles relatives à la sélection des chemins. Fig. 4. Complexité des algorithmes III. Génération des topologies A. Introduction Générer une topologie réseau est la première étape à réa- liser dans la création d'un scénario de simulation d'un pro- tocole réseau. Les résultats de simulations dépendent sou- vent de la topologie utilisée, particulièrement dans le cas des protocoles de routage. Par conséquent les topologies réseaux doivent être générées avec la plus grande précision possible. De plus les protocoles destinés à être déployés de- vraient être testés sur des topologies réseaux ressemblant à celle d'Internet. Beaucoup de générateurs de topologies réseaux sont proposés dans la littérature (Waxman [15], Inet [16], GT-ITM [17], Tiers [18], BRITE [19] ...). Le réa- lisme des topologies générées par ces générateurs est im- portant pour que les résultats de simulations soient cohé- rents. Dans cette section nous présentons une étude du gé- nérateur BRITE que nous utiliserons dans nos simulations. e-STA copyright 2009 by see Volume 6, N°2, pp 40-49 Nous comparerons BRITE avec les principaux autres géné- rateurs actuellement proposés dans la littérature. B. BRITE BRITE [19] semble être actuellement un des meilleurs outils fonctionnels. Il est conçu pour être exible. Comme l'illustre la gure 5, BRITE supporte la génération de dif- férentes catégories de modèles. En eet, il peut générer une topologie d'interconnexion de systèmes autonomes (AS) ou d'interconnexion de routeurs. Il peut également intégrer ces deux topologies dans une modélisation hiérarchisée (le sys- tème autonome est constitué de routeurs interconnectés). Lors de la génération, on peut choisir la méthode de pla- cement des noeuds (Aléatoire ou Heavy Tailed) et les pro- priétés de la méthode d'interconnexion utilisée (Waxman ou Barabt'asi-Albert). Fig. 5. Structure de BRITE La gure 6 présente l'architecture principale de BRITE. L'application lit les paramètres de génération depuis le - chier de conguration (1) qui peut être généré manuelle- ment par l'utilisateur ou automatiquement à l'aide de l'in- terface graphique (GUI) de BRITE. BRITE possède éga- lement la capacité d'importer des topologies générées par d'autres générateurs (GT-ITM [17], Inet[16], Tiers [18]), ou des topologies extraites directement de l'internet (NLANR [20], Skitter [21]). En sortie, BRITE possède son propre format propriétaire et peut également fournir la topolo- gie du réseau au format du simulateur de réseau NS2 [22]. BRITE intègre également un outil d'analyse appelé BRIANA. Cet outil fournit un ensemble d'analyses mono- tones qui peuvent être appliquées à une topologie importée dans BRITE. La génération d'un modèle avec BRITE comprend quatre étapes : 1. placement des noeuds dans le plan, 2. connexion des noeuds les uns aux autres, 3. aectation des valeurs aux attributs des composants de la topologie. Ces attributs sont notamment, le délai et la bande passante de chaque lien, 4. génération de la topologie selon le format spécié. BRITE est implémenté avec deux langages de program- mation (Java et C++) et peut être étendu pour incorporer de nouveaux types de topologies. Fig. 6. Architecture de BRITE Notre objectif est de choisir le meilleur générateur per- mettant de modéliser le plus dèlement possible la topolo- gie d'internet. Pour cela, nous avons évalué et comparé la précision de ces générateurs (BRITE, Inet, GT-ITM, Tiers) en mesurant certaines propriétés topologiques des graphes qu'ils génèrent comme le niveau de la topologie générée (Autonomous System (AS) ou niveau des routeurs) et aussi la nature de la topologie (Hiérarchique ou basée sur le de- gré). Fig. 7. Comparaison selon le niveau Fig. 8. Comparaison selon la nature de la topologie Les deux tableaux donnés par les gures 7 et 8 montrent que BRITE est le meilleur générateur en termes de cor- rélation avec une topologie réelle aussi bien au niveau re- présentation (niveau AS ou routeur) qu'au niveau de la structure (hiérarchique ou basé sur le degré), car il est le seul capable de générer des topologies selon ces diérentes caractéristiques. BRITE doit ce résultat au fait qu'il implé- mente la totalité des fonctions de génération de topologies contrairement aux autres générateurs. IV. Modèle des Simulations A. Outils des simulations L'adoption d'un nouveau modèle pour le routage dyna- mique nécessite sa validation par l'une des méthodes sui- e-STA copyright 2009 by see Volume 6, N°2, pp 40-49 vantes : la simulation au moyen d'outils spéciques, ou l'ex- périmentation sur une plate-forme réelle. Dans cette étude, nous avons opté pour la première méthode en utilisant un simulateur réseau appelé NS2 [22]. NS2 est l'un des outils de simulation le plus utilisé au sein de la communauté scien- tique. Il est développé par le département des techniques informatiques de l'université de Berkeley en Californie. Il permet à l'utilisateur de décrire et simuler des communica- tions entre les noeuds du réseau IP. Dans certaines versions de NS2, il est possible d'implémenter la bibliothèque MNS [23] qui permet de réaliser des simulations basées sur le protocole MPLS (MNS patch) [23]. Cette bibliothèque per- met donc d'établir des chemins explicites entre une paire de noeuds source/destination en s'appuyant sur le proto- cole de distribution d'étiquettes LDP (Label distribution Protocol). La simulation sous NS2 est basée sur des scripts TCL. BRITE, quant à lui, génère des topologies en format "brite", donc an d'adapter les topologies générées par BRITE, nous avons développé un utilitaire appelé brite2ns qui permet de transformer une topologie créée par BRITE dans le format TCL adéquat utilisé par le simulateur. B. Modèle La simulation avec NS2 se fait selon trois étapes. B.1 Etape 1 (Génération des topologies) Dans cette étape, on dénit la topologie du réseau gé- nérée par BRITE et on la transforme en NS2 par l'outil brite2ns. Cette topologie contient des noeuds (noeuds IP et noeuds MPLS) et des connexions entre noeuds. Pour chaque lien, on dénit le délai, la bande passante et le type de le d'attente. Enn, on congure les diérentes applica- tions MPLS comme le protocole LDP, le routage explicite et le protocole de signalisation (CR-LDP) et le trac avec QdS, et on connecte plusieurs paires source/destination (trois paires dans notre cas) aux routeurs MPLS. Notons que tous les paramètres sont générés de la même façon et avec les mêmes valeurs pour égaliser les coûts des topolo- gies. Les paramètres des topologies utilisées pour les simu- lations sont indiqués dans la gure 9. Fig. 9. Paramètres des topologies B.2 Etape 2 (Spécication du scénario du trac) Dans cette étape, l'utilisateur spécie les diérents agents de communication qui vont agir pendant la simu- lation. Un agent de communication consiste à aecter une source de trac à un noeud. Il décrit les diérentes opéra- tions (envoi des données, volume des demandes, distribu- tion du trac..). La gure 10 résume les valeurs des para- mètres utilisés dans les simulations. Tous les algorithmes sont simulés avec le même scénario de trac. Fig. 10. Paramètres du trac B.3 Etape 3 (Génération des paramètres de QdS selon le modèle simulé) L'algorithme ainsi généré utilise les deux chiers précé- demment décrits (topologie et trac). Au cours de la simu- lation, les résultats sont stockés dans des chiers. Les prin- cipales données archivées sont : le taux d'utilisation moyen et maximal, le délai moyen de bout en bout. Ces chiers résultats peuvent être directement exploités par NS2 ou par l'un des outils qui l'accompagnent (outil de tracé gra- phique : xgraph, outil d'animation de la simulation : nam [24]). Ils peuvent également être importés par d'autres ou- tils permettant de réaliser des analyses statistiques. V. Evaluation et Analyse des résultats Le principal objectif des modèles LBWDP et PEMS est de contrôler la qualité de service de bout-en-bout en impo- sant une utilisation ecace des ressources du réseau. Dans cette section, nous exploiterons diérents scénarios dans le but d'évaluer les performances des nos deux modèles et l'impact de la densité du réseau (l'augmentation du nombre de noeuds) sur leurs performances. A. Critères d'évaluation Les paramètres de qualité de service utilisés pour cette évaluation sont essentiellement les taux d'utilisation moyen et maximal des liens du réseau et le délai moyen de bout en bout. Le taux d'utilisation moyen permet d'indiquer le niveau d'équilibrage de charge dans le réseau. Plus il est faible plus le modèle eectue un bon équilibrage du trac. Le taux d'utilisation maximal des liens nous renseigne sur le risque de congestion dans le réseau. Quant au délai moyen, il permet de fournir une indication sur la capacité de l'algo- rithme à diérencier le délai selon les classes de trac. La corrélation des délais moyens obtenus en fonction de ces taux est une analyse permettant de savoir si l'équilibrage de la charge permet d'optimiser le délai moyen. B. Cas étudiés An de tenir compte de l'eet des paramètres de qua- lité de service, nous proposons d'étudier un réseau dans diérentes situations. B.1 Réseau de petite taille B.1.1 Scénario e-STA copyright 2009 by see Volume 6, N°2, pp 40-49 Dans [25], nous avons utilisé des réseaux composés d'un nombre de noeuds variant de 10 à 30 noeuds. Les para- mètres de la topologie et ceux du trac sont donnés res- pectivement par les gures 9 et 10. B.1.2 Analyse des résultats La gure 11 montre que le taux d'utilisation moyen de LBWDP est inférieur à celui de PEMS dans les 5 cas. Ce qui permet de conclure que LBWDP équilibre mieux la charge du réseau que PEMS. La gure 12 montre que le taux d'utilisation maximal de LBWDP est inférieur à celui de PEMS dans les 5 cas. Fig. 11. Taux d'utilisation moyen Fig. 12. Taux d'utilisation maximal Comme le montre la gure 13, le délai moyen de la classe EF est légèrement inférieur à celui des autres classes, ce qui implique que PEMS a diérencié le délai selon les classes de trac, alors que LBWDP (gure 14) traite toutes les classes de trac avec la même priorité, même si la gure 14 montre que le délai moyen de la classe AF est inférieur ou égal à celui de la classe EF. Pour plus de détails, se référer à [25]. B.2 Réseau de grande taille B.2.1 Scénario Nous avons simulés trois topologies contenant 100, 200 et 300 noeuds en utilisant les paramètres des gures 9 et 10. B.2.2 Analyse des résultats Fig. 13. Délai moyen pour PEMS Fig. 14. Délai moyen pour LBWDP LBWDP (gure 15) possède un taux moyen inférieur à celui de PEMS dans les 3 cas simulées. Donc, LBWDP équilibre mieux la charge du réseau que PEMS dans ce cas, car il minimise plus l'utilisation des liens du réseau. Cette conclusion est d'ailleurs renforcée par l'analyse des résultats du taux d'utilisation maximal des liens (gure 16). Fig. 15. Taux d'utilisation moyen La gure 17 montre que PEMS diérencie le délai se- lon chaque classe de trac, et il aecte le meilleur délai à la classe EF. LBWDP (gure 18) traite toutes les classes de trac avec la même priorité. Il n'a pas privilégié l'envoi du trac premium (classe EF) sur les chemins de meilleur délai. Si on compare les délais moyens des 2 algorithmes, on remarque que les délais moyens de LBWDP sont plus petits que ceux de PEMS, ce qui est normal pour la classe Best Eort mais surprenant pour EF. En eet PEMS a été conçu pour privilégier le trac EF même dans des situa- e-STA copyright 2009 by see Volume 6, N°2, pp 40-49 Fig. 16. Taux d'utilisation maximal tions de congestion. Il est donc surprenant d'obtenir un tel résultat qui remet en cause l'intérêt même de PEMS. Cela pourrait s'expliquer en arguant que la complexité supplé- mentaire introduite par Diserv ne compense pas le choix des meilleurs chemins. Des tests supplémentaires seront né- cessaires pour conrmer ou inrmer cette hypothèse. Fig. 17. Délai moyen pour PEMS Fig. 18. Délai moyen pour LBWDP Les simulations des topologies de 100 à 300 noeuds per- mettent d'analyser l'impact de la densité du réseau sur la qualité de l'équilibrage et dans une moindre mesure sur les délais. Concernant l'équilibrage de charge, on constate d'après les simulations que plus le réseau compte de noeuds, mieux la charge est équilibrée. Le nombre de noeuds est une caractéristique de la densité du réseau. Cela signie donc que l'augmentation du nombre de noeuds entraine l'augmentation du nombre de chemins disjoints entre une source et une destination. Par contre, l'impact de la densité sur le délai est moins mesurable ici. En eet, tout dépend du gain relatif de la baisse des congestions par rapport à l'augmentation de la largeur moyenne des chemins. B.3 Réseau faiblement chargé B.3.1 Scénario Dans ce cas, nous comparons les deux algorithmes avec les mêmes topologies de 100 noeuds mais on diminue la de- mande. Les paramètres de simulations sont donnés par les gure 9 et 10, avec un volume de demande de 100 [KB] au lieu de 500 [KB]. B.3.2 Analyse des résultats Le taux d'utilisation moyen (gure 19) est sensiblement le même pour les deux algorithmes. Par contre, PEMS a un taux d'utilisation maximal (gure 20) plus grand que celui de LBWDP. Fig. 19. Taux d'utilisation moyen pour un réseau moins chargé Fig. 20. Taux d'utilisation maximal pour un réseau moins chargé La gure 21 montre que PEMS diérencie le délai selon les classes de trac en privilégiant la classe EF qui a le meilleur délai, tandis que LBWDP, traite toutes les classes de la même manière. D'autre part, on remarque que les délais moyens de PEMS sont inférieurs à ceux de LBWDP, à l'inverse du cas V.B.2. B.4 Réseau fortement chargé B.4.1 Scénario Dans cette partie, nous augmentons la valeur de la de- mande à 1000 [KB] an d'arriver à un réseau proche de la saturation, et nous gardons les mêmes paramètres de simu- lations illustrés par les gures 9 et 10. B.4.2 Analyse des résultats La gure 22 montre le taux d'utilisation moyen des deux modèles. On remarque que l'équilibrage de charge est e-STA copyright 2009 by see Volume 6, N°2, pp 40-49 Fig. 21. Délai moyen pour un réseau moins chargé meilleur dans le cas de LBWDP que dans celui de PEMS. PEMS (gure 23) possède aussi un taux d'utilisation maxi- mal plus grand que celui de LBWDP, le taux de saturation des liens est très élevé dans le cas de PEMS. Fig. 22. Taux d'utilisation moyen pour un réseau plus chargé Fig. 23. Taux d'utilisation maximal pour un réseau plus chargé Concernant le délai moyen, la gure 24 montre que PEMS diérencie le délai selon les classes de trac et LBWDP traite toutes les classes avec la même priorité. On remarque que dans ce cas, la tendance des résultats concer- nant le taux d'utilisation et le délai moyen est la même que dans le cas V.B.2. B.5 Conclusion Dans cette partie, nous avons simulé plusieurs scénarios qui représentent l'état de charge d'un réseau FAI, aussi bien que sa taille. Dans un premier cas, nous avons pré- senté les résultats de simulation obtenus sur des réseaux de petites tailles et avec un volume de demande moyen. Dans le deuxième cas, nous avons augmenté le nombre de noeuds Fig. 24. Délai moyen pour un réseau plus chargé avec des topologies variantes de 100 à 300 noeuds en gar- dant le même scénario de trac moyen. Les gures ont mon- tré que LBWDP équilibre mieux la charge du réseau que PEMS, mais que PEMS diérencie le délai selon les classes de trac, tandis que LBWDP traite toutes les classes de trac avec la même priorité. L'analyse de l'eet de l'aug- mentation du nombre de noeuds sur les performances des deux algorithmes, a montré que plus le nombre de noeuds augmente, plus l'équilibrage devient meilleur. Dans le troi- sième cas, on a xé le nombre de noeuds à 100 et on a diminué le volume de trac à 100 [KB] an d'avoir un ré- seau faiblement chargé. Les simulations ont montré que les deux algorithmes possèdent presque le même taux d'utili- sation moyen, et que PEMS a un taux d'utilisation maxi- mal plus grand que LBWDP. Concernant le délai moyen, PEMS diérencie toujours le délai selon les classes de tra- c, et LBWDP les traite de la même manière. Par contre, on a remarqué que les délais moyens de PEMS sont plus petits que ceux de LBWDP, à l'inverse du cas V.B.2. Cela peut être expliqué par le fait que le critère de la largeur d'un chemin, utilisé par LBWDP, peut jouer un rôle im- portant dans la sélection des bons chemins pour satisfaire une demande de trac plus élevée que dans le cas d'un ré- seau moins chargé. Apparemment, dans un réseau moins chargé, la largeur d'un chemin n'ore pas cet intérêt ma- jeur, vu que l'utilisation des liens reste limitée. Ainsi les chemins gardent toujours des bandes passantes résiduelles largement susantes pour acheminer le trac sans pertur- ber l'envoi de trac diérencié selon les classes, où le critère du nombre de sauts utilisé par PEMS favorise dans ce cas le délai de l'envoi de ce trac. Finalement, dans le cas d'un réseau fortement chargé, les résultats ont montré que l'équi- librage de charge est meilleur avec LBWDP, et que PEMS diérencie le délai selon les classe de trac. En analysant les diérents scénarios, on peut remarquer que l'état de charge du réseau inuence les performances des deux modèles, et on remarque aussi une corrélation entre les deux principaux critères d'évaluation : le taux d'utilisation moyen et le délai moyen. VI. Réseau de grande taille et de topologie variable A. Introduction Dans cette partie, nous évaluons la structure des dié- rentes topologies générées par BRITE ainsi que leurs eets sur les performances des algorithmes tout en changeant de e-STA copyright 2009 by see Volume 6, N°2, pp 40-49 méthode de génération des topologies. Les diérentes mé- thodes sont l'emplacement de noeuds (Heavy-tailed, Ran- dom) [Fig.25] et l'interconnexion entre les noeuds (Wax- man, Barabt'). Les autres paramètres des topologies et de trac sont illustrés respectivement par les gures 9 et 10. Fig. 25. Méthodes d'emplacement Random et Heavy-Tailed B. Changement de méthode d'emplacement de noeuds La gure 26 montre le taux d'utilisation maximal de PEMS simulé avec diérentes topologies de 100 noeuds gé- nérées par les deux méthodes d'emplacement de noeuds (Heavy Tailed : HT-1, HT-2 et Random : R-1, R-2) et avec la même méthode d'interconnexion entre noeuds (Wax- man). On peut observer qu'on obtient de meilleurs résul- tats dans le cas des topologies générées avec la méthode Random que dans celui des topologies générées avec la mé- thode Heavy-Tailed. Par contre, avec deux topologies gé- nérées par la même méthode d'emplacement de noeuds, la diérence est moins importante. Fig. 26. Comparaison du taux d'utilisation maximal de PEMS avec les méthodes Random et Heavy Tailed C. Changement de méthode d'emplacement de noeuds et d'interconnexion entre noeuds En changeant la méthode d'interconnexion entre noeuds (Waxman, Barabt') et de méthode d'emplacement de noeuds (Heavy-Tailed, Random), on peut remarquer, d'après la gure 27, qu'avec la méthode Barabt' d'intercon- nexion entre noeuds, le modèle semble plus performant que ça soit avec la méthode d'emplacement de noeuds Heavy- Tailed ou Random. Avec la méthode Barabt', on obtient à peu près le même taux d'utilisation maximal pour les 2 méthodes d'emplacement de noeuds (Heavy-Tailed, Ran- dom). Ce taux est meilleur qu'avec la méthode Waxman d'interconnexion entre noeuds. Ces simulations prouvent que la structure du réseau joue un rôle sur les performances de l'algorithme dont il est implémenté, où on remarque que son comportement peut s'améliorer d'une structure à l'autre. Fig. 27. Taux d'utilisation du PEMS avec les méthodes d'emplace- ment et d'interconnexion pour des topologies de 100 noeuds Concernant le délai moyen, la gure 28 montre que PEMS garde toujours son avantage puisqu'il diérencie toujours le délai selon chaque classe de trac pour toutes les topologies simulées. On peut remarquer aussi que le délai moyen change légèrement selon le type de topologie simu- lée. Ce qui est cohérent avec le taux d'utilisation obtenu avec la même topologie (gure 27). Cela renforce d'ailleurs l'idée que le délai moyen dépend du taux d'utilisation de liens. Fig. 28. Délai moyen du PEMS avec les méthodes d'emplacement et d'interconnexion pour des topologies de 100 noeuds VII. Conclusion Dans cet article, nous avons évalué les deux modèles LBWDP et PEMS de routage dans le cadre des technolo- gies MPLS-TE. Leur objectif est de réduire les phénomènes de congestion en équilibrant mieux la charge sur l'ensemble d'un réseau de fournisseur d'accès internet. La technique qu'ils utilisent pour l'ingénierie du trac est celle du rou- tage multi-chemins sur un réseau IP-MPLS. LBWDP et PEMS reposent sur un premier critère fédérateur pour la e-STA copyright 2009 by see Volume 6, N°2, pp 40-49 qualité de service, à savoir le taux d'utilisation d'un lien. Sur cette base, nous avons comparé ces deux modèles se- lon diérents scénarios pour tester leurs capacités d'adap- tation à plusieurs situations. Nous avons simulés les deux algorithmes sur plusieurs topologies de tailles diérentes et en changeant le volume de trac. Nous avons constaté que l'état de charge du réseau inuence fortement sur les per- formances des deux modèles. Leur comportement respectif a changé d'un scénario à l'autre. Nous avons remarqué que l'équilibrage obtenu dans le cas d'un réseau plus grand est meilleur que celui obtenu dans celui d'un réseau de taille plus petite. Nous avons montré, d'après des simulations sur diérentes topologies générées par BRITE, que la struc- ture du réseau agit sur les performances du modèle. Cette étude nous amène à envisager des tests supplémentaires pour vérier si l'hypothèse de comportement selon le taux de charge est vériée. Si cette hypothèse est conrmée nous envisageons de développer un modèle à commutation entre LBWDP et PEMS en fonction de l'état de charge d'un ré- seau. Nous souhaitons également vérier la scalabilité des modèles. VIII. Annexe Fig. 29. Prole de trac EF en Temps/Source émetteur Fig. 30. Prole de trac AF en Temps/Source émetteur Fig. 31. Prole de trac BE en Temps/Source émetteur Références [1] Z. Wang "Internet QoS : Architectures and Mechanisms for Quality of Service", Morgan Kaufmann Publishers, Lucent Tech- nology (2001) [2] IETF working group,"'http ://www.ietf.org/html.charters/wg- dir.html'" [3] E. Rosen, "Multiprotocol label switching architecture", IETF RFC3031, http ://ietf.org/rfc/rfc3031.txt, 2001. [4] K. Lee, A. Rahmani, A. Toguyeni, "Stable load balancing algo- rithm in MPLS network", IMAACA'2005,France [5] CISCO, MPLS Trac Engineering-DiServ Aware (DS-TE), http ://www.cisco.com/en/US/docs/ios/1- 2s/feature/guide/fsdserv3.html [6] K. Lee, A. Rahmani, A. Toguyeni, "PEMS, a PEriodic Multi- Step routing algorithm for DS-TE", IeCCS'06, 2006 [7] K. Lee, A. Rahmani, A. Toguyeni, "Hybrid Multipath Routing Algorithms for Load Balancing in MPLS Based IP Network", AINA 2006, Austria [8] K. Lee, A. Toguyeni, A. Rahmani,"Comparison of multipath al- gorithms for load balancing in a MPLS Network", ICOIN'2005, Korea. [9] K. Lee, "Global QoS model in the ISP networks : DiServ aware MPLS Trac Engineering", Thesis, LAGIS, Ecole centrale de Lille, 2006. [10] A. Elwalid, C. Jin, S. Low, I. Widjaja,"MATE : MPLS Adaptive Trac Engineering", INFOCOM 2001 [11] J. Song, S. Kim and M. Lee,"Dynamic Load Distribution in MPLS Networks",Department of Computer Science, Ewha Wo- mans University, 2003. [12] S. Nelakuditi and Z.i Zhang,"On Selection of Paths for Multi- path Routing", University of Minnesota, Deparment of Computer Science Engineering,2002. [13] IntServ, "`http ://www.ietf.org/html.charters/OLD/intserv- charter.html"' [14] F. Le Faucheur, "MPLS Support of Dierentiated Services", draft-ietf-mpls-di-ext-09.txt, April 2001. [15] B. Waxman, "GRouting of Multipoint Connections", IEEE J. Select. Areas Commun., December 1988. [16] C. Jin, Q. Chen, and S. Jamin, "Inet : Internet Topology Gene- rator", Technical Report Research Report CSE-TR-433-00, Uni- versity of Michigan at Ann Arbor, 2000. [17] K. Calvert, M. Doar, and E. Zegura, "Modeling Internet Topo- logy", IEEE Transactions on Communications, pages 160–163, December 1997. [18] M. Doar, "A Better Model for Generating Test Networks", In Proceeding of IEEE GLOBECOM, November 1996. [19] BRITE, "BRITE : Boston university Representative Internet Topology gEnerator", Computer Science Department Boston University, BUCS-TR-2001-003, April 12, 2001 [20] NLANR, "National Laboratory for Applied Network Research (NLANR)", http ://moat.nlanr.net/rawdata/. [21] K.C. Clay and D. McRobb, "Measurement and Vi- sualization of Internet Connectivity and Performance", http ://www.caida.org/Tools/Skitter. [22] NS2, "The Network Simulator (NS2)", http ://www.isi.edu/nsnam/ns/. [23] MNS, "MPLS Simulation Tools", http ://folk.uio.no/johanmp/mpls.html. [24] Nam, "Nam : Network Animator", http ://www.isi.edu/nsnam/nam/. [25] K. Abboud, A. Toguyeni, A. Rahmani,"Evaluation de perfor- mances et de la complexité d'algorithmes de routage multi- chemins pour MPLS-TE", CIFA 2008, Roumanie e-STA copyright 2009 by see Volume 6, N°2, pp 40-49