Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

7l/3;3 3 o Université de ]Vlontréal Groupage de trafic à coût minimum dans les

7l/3;3 3 o Université de ]Vlontréal Groupage de trafic à coût minimum dans les réseaux anneaux WDM par Abdallah Jarray Département d’informatique et de recherche opérationnelle Faculté des arts et des sciences IViémoire présenté à la Faculté des études supérieures cii vue de l’obtention du grade de Maître ès sciences (M. Sc.) en informatique Décembre, 2004 Copyright © Ahdallah Jarray, 2004 ah Q CN Q Université tJIh de Montréal Direction des bibliothèques AVIS L’auteur a autorisé l’Université de Montréal à reproduire et diffuser, en totalité ou en partie, par quelque moyen que ce soft et sur quelque support que ce soit, et exclusivement à des fins non lucratives d’enseignement et de recherche, des copies de ce mémoire ou de cette thèse. L’auteur et les coauteurs le cas échéant conservent la propriété du droit d’auteur et des droits moraux qui protègent ce document. Ni la thèse ou le mémoire, ni des extraits substantiels de ce document, ne doivent être imprimés ou autrement reproduits sans l’autorisation de l’auteur. Afin de se conformer à la Loi canadienne sur la protection des renseignements personnels, quelques formulaires secondaires, coordonnées ou signatures intégrées au texte ont pu être enlevés de ce document. Bien que cela ait pu affecter la pagination, il n’y a aucun contenu manquant. NOTICE The author of this thesis or dissertation has granted a nonexclusive license allowing Université de Montréal to reproduce and publish the document, in part or in whole, and in any format, solely for noncommercial educationa! and research purposes. The author and co-authors if applicable retain copyright ownership and moral rights in this document. Neither the whole thesis or dissertation, nor substantial extracts from it, may be printed or otherwise reproduced without the author’s permission. In compliance with the Canadian Privacy Act some supporting forms, contact information or signatures may have been removed from the document. While this may affect the document page count, it does flot represent any loss of content from the document. Université de Montréal faculté des études supérieures Ce mémoire intitulé Groupage de trafic à coût minimum dans les réseaux anneaux WDM présenté par Abdallah Jarray o a été évalué par un jury composé des personnes suivantes Jean-Yves Potvin président-rapporteur Brigitte Jaumard directeur de recherche Abdelhakim Hafid membre du jury Mémoire accepté le, 19 janvier 2005 Résumé Mots clés : Anneau, $ONET, UPSR, BLSR, WDM, MSPP, $ADM, OADM, F3, FNB. Le projet de recherche porte sur la définition d’un modèle de programmation mathématique permettant l’étude de plusieurs scénarios de dimensionnement pour l’optimisation à coût minimum du groupage de trafic à faible débit et à plusieurs granularités dans les réseaux optiques SONET-WDM et MSPP en forme d’anneau. Nous étudions différents scénarios d’architecture de réseaux et de modèles de trafic. Nous considèrons le cas des anneaux unidirectionnels (UPSR) et bidirection nels (3LSR), les flots non bifurqués et les flots bifurqués, avec ou sans contrainte de continuité de longueurs d’onde et avec des capacités de longueurs d’onde fixées à l’avance ou calculées selon le besoin minimum lien par lien selon le trafic. Le coût est estimé à travers le nombre de cartes de transport, considérées comme l’élément le plus coûteux dans les anneaux SONET-WDM et MSPP. Les programmes mathématiques développés pour ces différents scénarios sont résolus à l’aide des bibliothèques de programmes de CPLEX-MIP. Les résultats sont comparés au schéma classique de dimensionnement des anneaux $ONET WDM avec un noeud de service (DXC+ $ADMs). Les résultats de calcul obtenus à l’issue de ces travaux démontrent un gain considérable des coûts de conception d’un réseau SONET-WDIVI qui utilise des composantes intelligentes distribuées sur l’ensemble des noeuds de type MSPP par rapport à l’architecture classique avec un noeud de service. u Une étude comparative de plusieurs scénarios de dimensionnement sur des intances différentes de réseaux SONET-WDM et MSPP et de trafic démontre qu’une architecture BL$R sans contrainte de continuité de longueurs d’onde et avec des capacités de longueurs d’onde calculées selon les besoins serait un bon choix technologique pour mettre en place un réseau optimisé avec une architecture adaptée à plusieurs sénarios de trafic. Un tel scénario génère une réduction des coûts qui est de l’ordre de 8 à 40 9o par rapport à la solution classique. Abstract Keywords RING, SONET, UPSR, BLSR, WDM, lVI$PP, SADM, OADM, BF, NBF. We consider the problem of trafic grooming in WDIVI and MSPP rings with 10w-rate traffic anci heterogeneous granularities. While networks are no longer limi tecl by transmission handwiclth, the key issue in WDM network design has evolved towards the processing capahilities of electronic switches, routers and multiplexers. Therefore, we focus here on trafic grooming with minimum interconnecting equip ment cost. We first formulate the problem a.s an integer linear programming (ILP) or a mixed integer linear programming (MILP) problem depending on the design specifications UPSR vs BLSR, non bifurcated vs bifurcated fiows, wavelength continuity vs free wavelength regeneration. Considering the case study of MSPP WDM rings, we define the cost hy a function of the number of transport blades, taking into account that the number of MSPP transport blades makes up a signi ficant portion of the total cost. Using the CPLEX linear programming package, we next compare the optimal solutions of the ILP or MILP programs for different design assumptions, including the classical assumptions with a single hub where the lighpaths directly connect the hub to all others nodes. The computation results obtained at the end of this work shows a significant profit on the cost design value of a SONET-WDIVI ring network using intelligent I\/1$PP components compared to the classical architecture with a node service. We observe that as the size of the ring increases, differences increase. The distrihuted 111 iv electronic equipment design is clearly cheaper, with a rnuch smaller number of wavelengths. A comparative study of the varions scenarios on different instances of SONET WDM networks and MSPP and of traffic shows that BLSR architecture without any wavelength continuity constraint and a wavelength capacity calculated accor ding to the traffic needs would be a good technical choice to set up an optimized network. It offers an architecture aclapted for variable traffic network loads. Such a scenario offers a cost reduction which is about 8 to 40% compared to the tradi tional solution with a node service. Table des matières Résumé . Abstract iii Table des matières y Liste des tableaux ix Table des figures xii Liste des sigles et abréviations xiv Dédicaces xv Remerciements xvi 1 Introduction 1 2 Les anneaux SONET-WDM 4 2.1 La fibre optique 4 2.2 Les technologies de multiplexage T 2.2.1 Multiplexage fDM 7 2.2.2 Multiplexage TDM 8 2.2.3 Multiplexage WDM 9 V TABLE DES MATIÈRES vi 2.3 Les réseaux SONET 10 2.3.1 Equipements d’interconnexion 10 2.3.2 Architectures 13 3 Problème GRWA 22 3.1 Définition de la prob1ématicue 22 3.2 Contribution du mémoire 25 3.3 Revue de la littérature 27 3.3.1 Résolutioll heuristique 28 3.3.2 Résolution exacte 30 4 Modélisation mathématique 35 4.1 Introduction 35 4.2 Modèle Mathématique 35 4.2.1 Rappel sur la théorie de graphes 35 4.2.2 Modélisation 36 4.3 Fonction objectif 37 4.4 Contraintes génériques du problème 38 4.4.1 Contrainte de capacité d’une longueur d’onde 38 4.4.2 Contrainte de capacité d’un lien optique 38 4.4.3 Constrainte d’exclusivité de choix d’un lien optique . . . 38 4.4.4 Calcul du nombre de ports MSPP 39 TABLE DES MATIÈRES ii 4.4.5 Calcul du nombre de cartes de transport MSPP 43 4.4.6 Contrainte de conservation des flots 44 4.5 Limite sur le nombre de sauts 47 4.6 Changement du signal de transport 47 4.7 Calcul de la charge du réseau 48 4.8 Récapitulatif des scénarios de conception 49 4.8.1 Contraintes 49 4.8.2 IViodèle 50 5 Résultats Numériques 54 5.1 Outils d’optimsation 54 5.1.1 La librairie d’optimisation Cplex 54 5.1.2 Méthodologie de résolution 54 5.1.3 Les outils d’accélération de la résolution 55 5.2 Instances des réseaux et modèles de trafic 56 5.3 Dimensionnement classique 59 5.4 Résultats de calcul de l’algorithme exact 69 5.4.1 Avec continuité de la longueur d’onde et capacité fixée du signal de transport 70 5.4.2 Sans continuité de la longueur d’onde avec capacité du si gnal de transport fixée 74 5.4.3 Sans continuité de la longueur d’onde avec capacité du si gnal de transport calculée par le programme 78 TABLE DES MATIÈRES viii 5.5 Récapitulatif des valeurs de la fonction objectif pour les différents scénarios de conception 80 5.6 Interprétation des résultats 82 6 Conclusion 84 ANNEXE A 86 Bibliographie 94 Liste des tableaux 2.1 Débit de transmission en OC-x/STS-x/STIVI-y et Mbit/s [321. . . 6 3.1 Solution avec 9 SADMs 25 3.2 Solution avec 8 $ADvIs 25 3.3 Comparaison des approches heuristiques 32 3.4 Comparaison des approches exactes 33 3.5 Suite de tableau 3.2 34 4.1 Récapitulatif des scénarios de conception 49 5.1 Coût des cartes OC-48 et OC-192 en unité monétaire 60 5.2 Calcul de FlotiN et FtotouT pour l’anneau R4 61 5.3 Calcul de FÏotJN et FÏotouT pour l’anneau R7 63 5.4 Calcul de FtotJN et FtotouT pour l’anneau Ripa 65 5.5 Calcul de FtotJN et FtotouT pour l’anneau uploads/s1/ jarray-abdallah-2004-memoire.pdf