Les avancées récentes de la recherche dans le domaine de la virtualisation des réseaux ainsi que l'émergence de nouveaux acteurs, ont beaucoup motivé la recherche et le développement de nouvelles approches et techniques permettant de relever les défis de l'Internet du Futur. Cette thèse a été motivée par ces avancées et par le besoin de concevoir une architecture d'allocation de réseaux virtuels à la demande à partir d'une infrastructure physique partagée. L'objectif de la thèse était, par conséquent, de concevoir et développer des algorithmes d'optimisation et des méthodes d'allocation de ressources virtuelles pour composer et créer des réseaux virtuels selon les besoins des utilisateurs et les conditions du réseau physique partagé. Ce travail suppose l'existence d'un acteur tiers «broker», appelé fournisseur de réseau virtuel, responsable de négocier et d'allouer des ressources virtuelles, offertes comme des services par des fournisseurs d'infrastructures, et de créer et offrir des réseaux virtuels à la demande pour des utilisateurs. L'objectif de la thèse est donc de développer des mécanismes et des algorithmes de découverte (ou «matching»), de correspondance (ou «mapping») et d'instanciation de réseaux virtuels tout en optimisant l'utilisation des ressources du substrat d'une part, et en réduisant, d'autre part, le coût pour les fournisseurs. Dans une première partie, l'analyse et la comparaison de plusieurs algorithmes d'allocation de réseau virtuel proposés dans la littérature ont été menées. Les différentes phases d'allocation de réseaux virtuels comprenant le matching, le mapping et l'instanciation sont définies et explorées en considérant la présence de plusieurs fournisseurs d'infrastructures (multi-domaine). La deuxième partie de cette thèse porte sur la conception, le développement et l'évaluation des algorithmes heuristiques de découverte (matching) permettant la recherche de correspondance entre les besoins spécifiés par les requêtes de réseau virtuel et les propriétés fonctionnelles (ou statiques) des ressources disponibles du substrat physique. Des techniques de regroupement conceptuel sont utilisées pour faciliter et accélérer la découverte et le matching des ressources virtuelles. Des solutions de partitionnement exactes et heuristiques, basées sur des algorithmes de max-flow/min-cut et des techniques de programmation linéaire, sont également proposées et évaluées pour partitionner les requêtes de réseaux virtuels entre plusieurs fournisseurs d'infrastructures tout en réduisant les coûts. La troisième partie de la thèse se focalise sur la conception, le développement et l'évaluation des algorithmes de mapping heuristiques et exacts qui consistent à extraire un graphe de réseau virtuel à partir d'un graphe de substrat physique d'une manière optimale. Un algorithme de mapping heuristique et distribué, basé sur l'approche multi-agents, est développé et évalué permettant d'améliorer le passage à l'échelle et d'assurer une distribution de charge. Un autre algorithme de mapping exact est également modélisé comme étant un programme linéaire afin d'assurer une sélection optimale des ressources tout en réduisant les coûts et maximisant le taux d'acceptation des requêtes. Dans la dernière partie, des algorithmes d'allocation adaptative de réseaux virtuels sont proposés, développés et évalués pour maintenir des réseaux virtuels suite à des changements dynamiques au niveau des services demandés ou bien au niveau des infrastructures physiques. / Recent advances in computer and network virtualisation combined with the emergence of new actors and business models motivated much research and development of new approaches to face the challenges of future Internet architectures. This thesis was motivated by these advances and by the need for efficient algorithms and frameworks to allocate virtual resources and create on demand virtual networks over shared physical infrastructures. The objective of the thesis has consequently been to conceive and develop provisioning algorithms and methods to set up and maintain virtual networks according to user needs and networking conditions. The work assumes the existence of virtual network providers acting as brokers that request virtual resources, on behalf of users, from multiple infrastructure providers. The investigation and research objective is to explore how virtual resources, offered as a service by infrastructure providers, are allocated while optimising the use of substrate resources and reducing the cost for providers. This thesis starts off with the analysis and comparison of several virtual network provisioning approaches and algorithms proposed in the literature. Provisioning phases are defined and explored including resource matching, embedding and binding. The scenario where multiple infrastructure providers are involved in the virtual network provisioning is addressed and a mathematical model of the VN provisioning problem is formulated. The second part of this thesis provides the design, implementation and evaluation of exact and heuristic matching algorithms to search, find and match virtual network requests with available substrate resources. Conceptual clustering techniques are used to facilitate finding and matching of virtual resources in the initial provisioning phases. Exact and heuristic algorithms are also proposed and evaluated to efficiently split virtual network requests over multiple infrastructure providers while reducing the matching cost. The request splitting problem is solved using both max-flow min-cut algorithms and linear programming techniques. The third part of this thesis presents the design, implementation and evaluation of exact and heuristic embedding algorithms to simultaneously assign virtual nodes and links to substrate resources. A distributed embedding algorithm, relying on a multi-agent based approach, is developed for large scale networks. An exact embedding algorithm, formulated as a mixed integer program, is also proposed and evaluated to ensure optimal node and link mapping while reducing cost and increasing the acceptance ratio of requests. Finally, this thesis presents the design and development of adaptive provisioning frameworks and algorithms to maintain virtual networks subject to dynamic changes in services demands and in physical infrastructures. Adaptive matching and embedding algorithms are designed, developed and evaluated to repair resource failures and dynamically optimize substrate networks utilisation.
| Identifer | oai:union.ndltd.org:theses.fr/2010TELE0007 |
| Date | 26 April 2010 |
| Creators | Louati, Inès |
| Contributors | Evry, Institut national des télécommunications, Zeghlache, Djamal |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0023 seconds