Virtual network provisioning framework for the future Internet

Architecture d'allocation de réseaux virtuels pour l'Internet du futur 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.