Algorithmes exacts et heuristiques pour le chainage de services réseaux virtualisés

Cette thèse traite du placement optimal et heuristique de fonctions réseau et de chaînes de fonction réseau dans des infrastructures cloud et réseau virtualisées. L'émergence de la virtualisation des fonctions réseau, connu sous l'acronyme NFV pour Network Function Virtualization, permet de découpler les fonctions réseau en mode logiciel du matériel d'hébergement et de s'appuyer sur des serveurs génériques et d'éviter l'usage de, et la dépendance à, des matériels dédiés voire propriétaires.Le placement de fonctions réseau virtualisées (représentées par VNF, Virtualized Network Functions) est NP-Difficile puisqu'il s'agit de projeter un petit graphe de ressources virtuelles sur un graphe plus grand (graphe de l'infrastructure d'hébergement). Les solutions optimales, en particulier la programmation linéaire en nombre entier (ILP), ne passent pas à l'échelle. Sachant que la demande est dynamique et peut varier dans le temps et que le réseau est lui même variable dans le temps, il est important de prévoir des adaptations des placements. Cela peut s'effectuer par de l'élasticité sur les ressources d'hébergement réservées à une fonction réseau virtualisée, à un graphe de service réseau et par une extension du graphe de service lui même en fonction du contexte et des exigences des utilisateurs ou tenants.La thèse propose une famille d'algorithmes pour le placement de chaînes de services (ou fonctions) réseau avec la possibilité d'étendre les ressources d'hébergement des VNFs (c'est à dire assurer l'élasticité du service d'hébergement en augmentant les ressources allouées ou en générant plusieurs instances de VNFs pour écouler le trafic et répondre à la demande) en plus du placement initial. Une solution en programmation en nombre entier est élaborée et aussi utilisée comme référence pour une comparaison avec l'état de l'art et avec les extensions proposées. L'optimisation étant effectuée en instantanée au fur à mesure de l'arrivée des demandes, une à la fois, une solution qui regroupe plusieurs demandes pour y répondre simultanément, en élaborant un graphe composite, permet d'améliorer les performances. Cette approche connue sous le nom de "batch" n'améliore que partiellement la performance, la récompense sur le long terme (en efficacité, minimisation des ressources consommées, et en équilibrage de charge) est nécessairement limitée.La thèse s'est penchée aussi sur l'extension de graphes de services réseau, de tenants, déjà déployés, en adoptant une approche de type arbre de recouvrement, Spanning Tree. Plus spécifiquement une modélisation du problème en un "Steiner Tree Problem" a conduit à des performances proches de l'optimal pour des extensions de graphes au fil des demandes, en les traitant séparément. Les travaux de thèse sont par la suite revenus sur la rentabilité sur le long terme des algorithmes, en approchant le placement de chaînes de services et fonctions réseau comme un objectif long terme via de l'apprentissage par renforcement en se souciant plus de la rentabilité et de l'efficacité long terme des algorithmes contrairement aux approches visant exclusivement l'optimalité instantanée à chaque nouvelle demande.Cette thèse a permis de faire avancer autant que faire se peut l'état de l'art du placement optimal dans les infrastructures cloud et réseau partagées. Notamment, le problème, et besoin, d'extension de graphes, de tenants, déjà déployés, sans perturber l'hébergement initial, a reçu peu d'attention. Pourtant ce besoin est essentiel pour répondre à des déploiements additionnels de nouvelles fonctions et services réseau, et pour réagir aux dégradations et à l'accroissement de la demande, aux attaques et pour assurer l'introduction de nouveaux services et fonctions de sécurité autour du graphe initial. L'approche peut aussi répondre à des modifications de graphes et d'isolations d'une partie (défectueuse ou compromise) d'un graphe et de son remplacement par d'autres services et graphes fiables et non altérés.Network Function Virtualization (NFV) is an innovative emerging concept that decouples network functions (such as firewalls, DNS, NATs, load balancers, etc.) from dedicated hardware devices (the traditional expensive middleboxes). This decoupling enables hosting of network services, known as Virtualized Network Functions (VNFs), on commodity hardware (such as switches or servers) and thus facilitates and accelerates service deployment and management by providers, improves flexibility, leads to efficient and scalable resource usage, and reduces costs. This paradigm is a major turning point in the evolution of networking, as it introduces high expectations for enhanced economical network services, as well as major technical challenges.One of the main technical challenges in this domain is the optimal placement of the VNFs within the hosting infrastructures. This placement has a critical impact on the performance of the network, as well as on its reliability and operation cost. The VNF Placement and Chaining Problem is NP-Hard and there is a need for placement approaches that can scale with problem size and find good solutions in acceptable times. The overarching goal of this thesis is to enable dynamic virtual network resources provisioning to deal with demand fluctuation during the virtual network lifetime, and to enhance the substrate resource usage. Reserving a fixed amount of resources is inefficient to satisfy the VNF resource requirements. To cope with these problems, we propose dynamic resource management strategies.In this thesis, both exact and heuristic algorithms are designed and evaluated in terms of optimality, complexity, ability to scale, and compared with the state of the art. Elastic mechanisms and scaling algorithms are first presented to improve adaptation and deployment of virtualized network functions in NFV infrastructures to support increasing demand while increasing provider's revenue. Since network providers not only need to control, classify and steer user and application traffic flows in their dedicated slices but also want to extend their already acquired and operational virtual networks or slices with additional service graphs, the thesis proposes extension algorithms of already hosted network functions graphs without disrupting initially deployed and active service instances. The proposed algorithms extend already deployed network services and functions graphs to respond to new demands while taking into account the constraint of minimizing the impact on the original service graphs. The extension algorithms are particularly useful and suitable for situations where already deployed graphs need to be enhanced with new features and properties (adding new functions) and modified to react to degradation and attacks such as removing a fraction of the graph and replacing with new complex and composed functions into more capable and uncompromised graphs.The thesis also addresses the VNF placement and chaining problem in an online and in a batch mode to improve performance in terms of longer time reward. An enhanced Reinforcement Learning-based approach is also proposed to improve the long term reward beyond what the previous methods can achieve. This is analyzed and realized for a load balancing objective but can be adjusted for other criteria