Algorithms for Virtual Network Functions chaining

Cette these traite du placement optimal et heuristique de fonctions reseau et de chaines de fonction reseau dans des infrastructures cloud et reseau virtualisees. L'emergence de la virtualisation des fonctions reseau, connu sous l'acronyme NFV pour Network Function Virtualization, permet de decoupler les fonctions reseau en mode logiciel du materiel d'hebergement et de s'appuyer sur des serveurs generiques et d'eviter l'usage de, et la dependance a, des materiels dedies voire proprietaires.Le placement de fonctions reseau virtualisees (representees 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'hebergement). Les solutions optimales, en particulier la programmation lineaire en nombre entier (ILP), ne passent pas a l'echelle. Sachant que la demande est dynamique et peut varier dans le temps et que le reseau est lui meme variable dans le temps, il est important de prevoir des adaptations des placements. Cela peut s'effectuer par de l'elasticite sur les ressources d'hebergement reservees a une fonction reseau virtualisee, a un graphe de service reseau et par une extension du graphe de service lui meme en fonction du contexte et des exigences des utilisateurs ou tenants.La these propose une famille d'algorithmes pour le placement de chaines de services (ou fonctions) reseau avec la possibilite d'etendre les ressources d'hebergement des VNFs (c'est a dire assurer l'elasticite du service d'hebergement en augmentant les ressources allouees ou en generant plusieurs instances de VNFs pour ecouler le trafic et repondre a la demande) en plus du placement initial. Une solution en programmation en nombre entier est elaboree et aussi utilisee comme reference pour une comparaison avec l'etat de l'art et avec les extensions proposees. L'optimisation etant effectuee en instantanee au fur a mesure de l'arrivee des demandes, une a la fois, une solution qui regroupe plusieurs demandes pour y repondre simultanement, en elaborant un graphe composite, permet d'ameliorer les performances. Cette approche connue sous le nom de "batch" n'ameliore que partiellement la performance, la recompense sur le long terme (en efficacite, minimisation des ressources consommees, et en equilibrage de charge) est necessairement limitee.La these s'est penchee aussi sur l'extension de graphes de services reseau, de tenants, deja deployes, en adoptant une approche de type arbre de recouvrement, Spanning Tree. Plus specifiquement une modelisation du probleme en un "Steiner Tree Problem" a conduit a des performances proches de l'optimal pour des extensions de graphes au fil des demandes, en les traitant separement. Les travaux de these sont par la suite revenus sur la rentabilite sur le long terme des algorithmes, en approchant le placement de chaines de services et fonctions reseau comme un objectif long terme via de l'apprentissage par renforcement en se souciant plus de la rentabilite et de l'efficacite long terme des algorithmes contrairement aux approches visant exclusivement l'optimalite instantanee a chaque nouvelle demande.Cette these a permis de faire avancer autant que faire se peut l'etat de l'art du placement optimal dans les infrastructures cloud et reseau partagees. Notamment, le probleme, et besoin, d'extension de graphes, de tenants, deja deployes, sans perturber l'hebergement initial, a recu peu d'attention. Pourtant ce besoin est essentiel pour repondre a des deploiements additionnels de nouvelles fonctions et services reseau, et pour reagir aux degradations et a l'accroissement de la demande, aux attaques et pour assurer l'introduction de nouveaux services et fonctions de securite autour du graphe initial. L'approche peut aussi repondre a des modifications de graphes et d'isolations d'une partie (defectueuse ou compromise) d'un graphe et de son remplacement par d'autres services et graphes fiables et non alteres.