Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Les réseaux de communication devenant de plus en plus présents dans nos activités quotidiennes, l'interruption des services fournis par le réseau, ou même une dégradation significative de leurs qualit és, deviennent de moins en moins tolérables. Une conception robuste des réseaux de communication, anticipant les pannes éventuelles d'équipements ou les variations sur la demande en trafic, devient donc de plus en plus nécessaire. Cette thèse traite de plusieurs problèmes de conception et de planification robustes apparaissant dans le domaine des télécommunications. Nous étudions tout d'abord le problème de la conception et du dimensionnement d'une topologie de communication résilience. Nous proposons un nouveau modèle de conception de réseaux intégrant les coûts et les contraintes des différents équipements (liens, routeurs, cartes). Ce modèle prend également en compte de nombreuses contraintes opérationnelles telles que la présence de noeud potentiel et de capacités modulaires, mais aussi des contraintes sur les délais de communication. Un algorithme exact et deux approximations sont proposés pour résoudre ce problème. Les résultats numériques montrent que des économies substantielles peuvent être effectuées en intégrant les coûts d'équipements dans la phase amont du processus de conception. Avec la croissance exponentielle de l'Internet et l'incroyable développement des applications réseaux, les variations sur les volumes de trafic sont devenus un des problèmes majeurs auxquels sont confrontés les opérateurs. Aujourd'hui, concevoir un réseau sur la base d'une unique matrice de trafic "en heure de pointe" est de moins en moins crédible du fait de la forte volatilité des trafics. Il devient ainsi nécessaire d'intégrer explicitement l'incertitude sur la demande en trafic dans les problèmes d'optimisation du routage. Nous étudions deux problèmes d'optimisation robuste du routage : (1) le problème de conception des VPN dans le cadre du modèle hose d'incertitude sur la de mande et (2) le problème d'optimisation des métriques de routage IGP avec incertitude sur la demande. Nous formulons des modèles mathématiques de chacun de ces problèmes et proposons des heuristiques efficaces basées sur des techniques de recherche locale pour les résoudre. L'efficacité pratique des techniques et méthodes développées dans le cadre de cette thèse est démontrée et validée par une batterie de tests sur des données réalistes. Ce travail a d'autre part donné lieu `a plusieurs développements logiciels dans le logiciel de planification de réseaux NEST de QoS Design.

La technologique utilisée dans les réseaux de télécommunication à commutation de paquets est en développement permanent. La tendance actuelle est orientée vers la mutualisation des services voix et données, de leurs infrastructures et des techniques associées (réseaux IP/MPLS, QoS dans Internet). Les méthodes classiques utilisées pour l'évaluation de performances des ces réseaux sont la modélisation analytique et la simulation événementielle. La simulation événementielle requiert des temps de calcul prohibitifs, tandis que les modèles issus des méthodes analytiques manquent parfois de précision. Le travail présenté dans cette thèse définit un cadre de modélisation appelé Simulation Hybride Distribuée qui combine de manière rigoureuse la théorie différentielle du trafic et la simulation événementielle. Dans une première technique, les ressources du réseau sont partitionnées en domaines dont certains sont simulés par événements, et les autres sont modélisés par des équations intégrées numériquement. La seconde technique proposée permet la circulation de trafics simulés par événements sur les ressources du réseau modélisées par des équations. La simulation hybride permet ainsi de prolonger la modélisation analytique au-delà de ses limites théoriques. Elle permet également de concevoir des modèles d'évaluation de performances très généraux et de développer des logiciels plus performants en temps de calculs. Un prototype de simulateur hybride a été conçu. Il permet de modéliser précisément des routeurs Internet Diffserv et MPLS, le protocole TCP ainsi que diverses sources de trafic multimédia (Audio, Vidéo). Pour réduire les temps de calcul, le simulateur peut être parallélisé. En ce sens, un nouveau noyau de communication de l'environnement de parallélisme LANDA a été conçu. Il offre une bibliothèque à la norme MPI et permet d'utiliser simultanément et efficacement (latence, bande passante) plusieurs media de communication haut-débit ainsi que la mémoire commune S MP.

Le projet de recherche porte sur l'étude des problèmes de conception et de planification d'un réseau optique de longue distance, aussi appelé réseau de coeur (OWAN-Optical Wide Area Network en anglais). Il s'agit d'un réseau qui transporte des flots agrégés en mode commutation de circuits. Un réseau OWAN relie différents sites à l'aide de fibres optiques connectées par des commutateurs/routeurs optiques et/ou électriques. Un réseau OWAN est maillé à l'échelle d'un pays ou d’un continent et permet le transit des données à très haut débit. Dans une première partie du projet de thèse, nous nous intéressons au problème de conception de réseaux optiques agiles. Le problème d'agilité est motivé par la croissance de la demande en bande passante et par la nature dynamique du trafic. Les équipements déployés par les opérateurs de réseaux doivent disposer d'outils de configuration plus performants et plus flexibles pour gérer au mieux la complexité des connexions entre les clients et tenir compte de la nature évolutive du trafic. Souvent, le problème de conception d'un réseau consiste à prévoir la bande passante nécessaire pour écouler un trafic donné. Ici, nous cherchons en plus à choisir la meilleure configuration nodale ayant un niveau d'agilité capable de garantir une affectation optimale des ressources du réseau. Nous étudierons également deux autres types de problèmes auxquels un opérateur de réseau est confronté. Le premier problème est l'affectation de ressources du réseau. Une fois que l'architecture du réseau en termes d'équipements est choisie, la question qui reste est de savoir : comment dimensionner et optimiser cette architecture pour qu'elle rencontre le meilleur niveau possible d'agilité pour satisfaire toute la demande. La définition de la topologie de routage est un problème d'optimisation complexe. Elle consiste à définir un ensemble de chemins optiques logiques, choisir les routes physiques suivies par ces derniers, ainsi que les longueurs d'onde qu'ils utilisent, de manière à optimiser la qualité de la solution obtenue par rapport à un ensemble de métriques pour mesurer la performance du réseau. De plus, nous devons définir la meilleure stratégie de dimensionnement du réseau de façon à ce qu'elle soit adaptée à la nature dynamique du trafic. Le second problème est celui d'optimiser les coûts d'investissement en capital(CAPEX) et d'opération (OPEX) de l'architecture de transport proposée. Dans le cas du type d'architecture de dimensionnement considérée dans cette thèse, le CAPEX inclut les coûts de routage, d'installation et de mise en service de tous les équipements de type réseau installés aux extrémités des connexions et dans les noeuds intermédiaires. Les coûts d'opération OPEX correspondent à tous les frais liés à l'exploitation du réseau de transport. Étant donné la nature symétrique et le nombre exponentiel de variables dans la plupart des formulations mathématiques développées pour ces types de problèmes, nous avons particulièrement exploré des approches de résolution de type génération de colonnes et algorithme glouton qui s'adaptent bien à la résolution des grands problèmes d'optimisation. Une étude comparative de plusieurs stratégies d'allocation de ressources et d'algorithmes de résolution, sur différents jeux de données et de réseaux de transport de type OWAN démontre que le meilleur coût réseau est obtenu dans deux cas : une stratégie de dimensionnement anticipative combinée avec une méthode de résolution de type génération de colonnes dans les cas où nous autorisons/interdisons le dérangement des connexions déjà établies. Aussi, une bonne répartition de l'utilisation des ressources du réseau est observée avec les scénarios utilisant une stratégie de dimensionnement myope combinée à une approche d'allocation de ressources avec une résolution utilisant les techniques de génération de colonnes. Les résultats obtenus à l'issue de ces travaux ont également démontré que des gains considérables sont possibles pour les coûts d'investissement en capital et d'opération. En effet, une répartition intelligente et hétérogène de ressources d’un réseau sur l'ensemble des noeuds permet de réaliser une réduction substantielle des coûts du réseau par rapport à une solution d'allocation de ressources classique qui adopte une architecture homogène utilisant la même configuration nodale dans tous les noeuds. En effet, nous avons démontré qu'il est possible de réduire le nombre de commutateurs photoniques tout en satisfaisant la demande de trafic et en gardant le coût global d'allocation de ressources de réseau inchangé par rapport à l'architecture classique. Cela implique une réduction substantielle des coûts CAPEX et OPEX. Dans nos expériences de calcul, les résultats démontrent que la réduction de coûts peut atteindre jusqu'à 65% dans certaines jeux de données et de réseau. / The research project focuses on the design and planning problems of long distance optical networks also called OWANs (Optical Wide Area Networks) or "backbone". These are networks that carry aggregate flows in circuit switching mode. OWAN networks connect sites with optical fibers, cross-connected by optical and/or electric switches/routers. OWAN networks are meshed throughout a country or continent and allow the transit of data at very high speed. In the first part of the thesis, we are interested in the design problem of agile optical networks. The problem of agility is motivated by the growing of bandwidth demand and by the dynamic pattern of client traffic. Equipment deployed by network operators must allow greater reconfigurability and scalability to manage the complexity of connections among clients and deal with a dynamic traffic pattern. Often, the problem of network design is to provide the required bandwidth to grant a given traffic pattern. Here, we seek to choose the best nodal configuration with the agility level that can guarantee the optimal network resource provisioning. We will also study two other types of problems that can face a network operator. The first problem is the network resource provisioning. Once the network architecture design is chosen, the remaining question is : How to resize and optimize the architecture to meet the agility level required to grant any demand. The definition of the network provisioning scheme is a complex optimization problem. It consists of defining a set of optical paths, choosing the routes followed by them, and their assigned wavelengths, so as to optimize the solution quality with respect to some network metrics. Moreover, we need to define the best design strategy adapted to the dynamic traffic pattern. The second problem is to optimize the capital investment cost (CAPEX) and the operational expenses (OPEX) of the selected optical transport architecture. In the case of the design architecture considered in this thesis, the CAPEX includes the routing cost, the installation cost and the commissioning service cost for all required network equipment in end connections and intermediate nodes. OPEX correspond to expenses related to the operation of the transport network. Given the symmetrical nature and the exponential number of variables in most mathematical formulations developed for these types of problems, we particularly explored solving approaches based on a column generation algorithm and greedy heuristics which adapt well to these types of modeling and large scale mathematical models. A comparative study of several provisioning strategies and solution algorithms on different traffic and OWAN network instances show that the minimum network cost is obtained in two cases : An anticipative dimensioning strategy combined with a column generation solution combined with a rounding off heuristic in the context of no disturbance or possible disturbance of previously granted connections. Also, a good repartition of used network resources (MSPPs, PXC and wavelengths) is observed with the scenarios using a myopic strategy and a column generation solution approach. The results obtained from this thesis also show that a considerable saving in CAPEX and OPEX costs are possible in the case of an intelligent allocation and heteregenous distribution of network resources through network nodes compared with the classical architecture that adopts a uniform architecture using the same configuration in all nodes. Indeed, we demonstrated that it is possible to reduce the number of PXCs (Photonic Switches) while satisfying the traffic matrix and keeping the overall cost of provisioning network unchanged compared to what is happening in a classic architecture. This implies a substantial reduction in network CAPEX and OPEX costs. In our experiments with various network and traffic instances, we show that a careful dimensioning and location of the nodal equipment can save up to 65% of network expenses.

Le projet de recherche porte sur l'étude des problèmes de conception et de planification d'un réseau optique de longue distance, aussi appelé réseau de coeur (OWAN-Optical Wide Area Network en anglais). Il s'agit d'un réseau qui transporte des flots agrégés en mode commutation de circuits. Un réseau OWAN relie différents sites à l'aide de fibres optiques connectées par des commutateurs/routeurs optiques et/ou électriques. Un réseau OWAN est maillé à l'échelle d'un pays ou d’un continent et permet le transit des données à très haut débit. Dans une première partie du projet de thèse, nous nous intéressons au problème de conception de réseaux optiques agiles. Le problème d'agilité est motivé par la croissance de la demande en bande passante et par la nature dynamique du trafic. Les équipements déployés par les opérateurs de réseaux doivent disposer d'outils de configuration plus performants et plus flexibles pour gérer au mieux la complexité des connexions entre les clients et tenir compte de la nature évolutive du trafic. Souvent, le problème de conception d'un réseau consiste à prévoir la bande passante nécessaire pour écouler un trafic donné. Ici, nous cherchons en plus à choisir la meilleure configuration nodale ayant un niveau d'agilité capable de garantir une affectation optimale des ressources du réseau. Nous étudierons également deux autres types de problèmes auxquels un opérateur de réseau est confronté. Le premier problème est l'affectation de ressources du réseau. Une fois que l'architecture du réseau en termes d'équipements est choisie, la question qui reste est de savoir : comment dimensionner et optimiser cette architecture pour qu'elle rencontre le meilleur niveau possible d'agilité pour satisfaire toute la demande. La définition de la topologie de routage est un problème d'optimisation complexe. Elle consiste à définir un ensemble de chemins optiques logiques, choisir les routes physiques suivies par ces derniers, ainsi que les longueurs d'onde qu'ils utilisent, de manière à optimiser la qualité de la solution obtenue par rapport à un ensemble de métriques pour mesurer la performance du réseau. De plus, nous devons définir la meilleure stratégie de dimensionnement du réseau de façon à ce qu'elle soit adaptée à la nature dynamique du trafic. Le second problème est celui d'optimiser les coûts d'investissement en capital(CAPEX) et d'opération (OPEX) de l'architecture de transport proposée. Dans le cas du type d'architecture de dimensionnement considérée dans cette thèse, le CAPEX inclut les coûts de routage, d'installation et de mise en service de tous les équipements de type réseau installés aux extrémités des connexions et dans les noeuds intermédiaires. Les coûts d'opération OPEX correspondent à tous les frais liés à l'exploitation du réseau de transport. Étant donné la nature symétrique et le nombre exponentiel de variables dans la plupart des formulations mathématiques développées pour ces types de problèmes, nous avons particulièrement exploré des approches de résolution de type génération de colonnes et algorithme glouton qui s'adaptent bien à la résolution des grands problèmes d'optimisation. Une étude comparative de plusieurs stratégies d'allocation de ressources et d'algorithmes de résolution, sur différents jeux de données et de réseaux de transport de type OWAN démontre que le meilleur coût réseau est obtenu dans deux cas : une stratégie de dimensionnement anticipative combinée avec une méthode de résolution de type génération de colonnes dans les cas où nous autorisons/interdisons le dérangement des connexions déjà établies. Aussi, une bonne répartition de l'utilisation des ressources du réseau est observée avec les scénarios utilisant une stratégie de dimensionnement myope combinée à une approche d'allocation de ressources avec une résolution utilisant les techniques de génération de colonnes. Les résultats obtenus à l'issue de ces travaux ont également démontré que des gains considérables sont possibles pour les coûts d'investissement en capital et d'opération. En effet, une répartition intelligente et hétérogène de ressources d’un réseau sur l'ensemble des noeuds permet de réaliser une réduction substantielle des coûts du réseau par rapport à une solution d'allocation de ressources classique qui adopte une architecture homogène utilisant la même configuration nodale dans tous les noeuds. En effet, nous avons démontré qu'il est possible de réduire le nombre de commutateurs photoniques tout en satisfaisant la demande de trafic et en gardant le coût global d'allocation de ressources de réseau inchangé par rapport à l'architecture classique. Cela implique une réduction substantielle des coûts CAPEX et OPEX. Dans nos expériences de calcul, les résultats démontrent que la réduction de coûts peut atteindre jusqu'à 65% dans certaines jeux de données et de réseau. / The research project focuses on the design and planning problems of long distance optical networks also called OWANs (Optical Wide Area Networks) or "backbone". These are networks that carry aggregate flows in circuit switching mode. OWAN networks connect sites with optical fibers, cross-connected by optical and/or electric switches/routers. OWAN networks are meshed throughout a country or continent and allow the transit of data at very high speed. In the first part of the thesis, we are interested in the design problem of agile optical networks. The problem of agility is motivated by the growing of bandwidth demand and by the dynamic pattern of client traffic. Equipment deployed by network operators must allow greater reconfigurability and scalability to manage the complexity of connections among clients and deal with a dynamic traffic pattern. Often, the problem of network design is to provide the required bandwidth to grant a given traffic pattern. Here, we seek to choose the best nodal configuration with the agility level that can guarantee the optimal network resource provisioning. We will also study two other types of problems that can face a network operator. The first problem is the network resource provisioning. Once the network architecture design is chosen, the remaining question is : How to resize and optimize the architecture to meet the agility level required to grant any demand. The definition of the network provisioning scheme is a complex optimization problem. It consists of defining a set of optical paths, choosing the routes followed by them, and their assigned wavelengths, so as to optimize the solution quality with respect to some network metrics. Moreover, we need to define the best design strategy adapted to the dynamic traffic pattern. The second problem is to optimize the capital investment cost (CAPEX) and the operational expenses (OPEX) of the selected optical transport architecture. In the case of the design architecture considered in this thesis, the CAPEX includes the routing cost, the installation cost and the commissioning service cost for all required network equipment in end connections and intermediate nodes. OPEX correspond to expenses related to the operation of the transport network. Given the symmetrical nature and the exponential number of variables in most mathematical formulations developed for these types of problems, we particularly explored solving approaches based on a column generation algorithm and greedy heuristics which adapt well to these types of modeling and large scale mathematical models. A comparative study of several provisioning strategies and solution algorithms on different traffic and OWAN network instances show that the minimum network cost is obtained in two cases : An anticipative dimensioning strategy combined with a column generation solution combined with a rounding off heuristic in the context of no disturbance or possible disturbance of previously granted connections. Also, a good repartition of used network resources (MSPPs, PXC and wavelengths) is observed with the scenarios using a myopic strategy and a column generation solution approach. The results obtained from this thesis also show that a considerable saving in CAPEX and OPEX costs are possible in the case of an intelligent allocation and heteregenous distribution of network resources through network nodes compared with the classical architecture that adopts a uniform architecture using the same configuration in all nodes. Indeed, we demonstrated that it is possible to reduce the number of PXCs (Photonic Switches) while satisfying the traffic matrix and keeping the overall cost of provisioning network unchanged compared to what is happening in a classic architecture. This implies a substantial reduction in network CAPEX and OPEX costs. In our experiments with various network and traffic instances, we show that a careful dimensioning and location of the nodal equipment can save up to 65% of network expenses.