Avec la croissance exponentielle des demandes de service, les opérateurs ont déployé de nombreux équipements, et par conséquent, la gestion du réseau est devenue de plus en plus difficile et coûteuse. La virtualisation des fonctions réseau (NFV) a été proposée comme un nouveau paradigme pour réduire les coûts liés à l’acquisition et à la maintenance pour les réseaux de télécommunications. Dans ce travail de thèse, nous nous intéressons aux problèmes du chaînage des fonctions virtuelles (VNFs) qui combinent des décisions de localisation des VNFs et de routage des demandes. D'un point de vue d'optimisation, ce problème est une combinaison des problèmes de localisation (pour la partie d'installation des VNFs) et de conception de réseaux (pour la partie de routage). Ces deux problèmes ont été largement étudié dans la littérature. Cependant, leur combinaison représente des divers challenges en termes de modélisation et de résolution. Dans la première partie de cette thèse, nous considérons une version réaliste du problème du chaînage des VNFs (VNF-PR) afin de comprendre l'impact des différents aspects sur les coûts et les performances de gestion du réseau. Dans ce but, nous étendons le travail dans~\cite{Addis2015} en considérant des caractéristiques et des contraintes plus réalistes des infrastructures NFV et nous proposons un modèle de programmation linéaire et une heuristique mathématique pour le résoudre. Dans le but de mieux comprendre la structure du problème et ses propriétés, la deuxième partie de la thèse est orientée vers l'étude théorique du problème, où nous avons étudié une version compacte du problème du chaînage des VNFs. Nous fournissons des résultats sur la complexité de calcul sous divers cas de topologie et de capacité. Ensuite, nous proposons deux modèles et nous les testons sur un testbed avec plus de 100 instances différentes avec différents cas de capacité. Au final, nous abordons la scalabilité du problème en proposant des méthodes constructives et des méthodes heuristiques basées sur la programmation linéaire entière pour traiter efficacement des instances de taille grande (jusqu'à 60 nœuds et 1800 demandes). Nous montrons que les heuristiques proposées sont capables de résoudre efficacement des instances de taille moyenne (avec jusqu'à 30 nœuds et 1 000 demandes) de cas de capacité difficiles et de trouver de bonnes solutions pour les instances dures, où le modèle ne peut fournir aucune solution avec un temps de calcul limité. / Due to the exponential growth of service demands, telecommunication networks are populated with a large and increasing variety of proprietary hardware appliances, and this leads to an increase in the cost and the complexity of the network management. To overcome this issue, the NFV paradigm is proposed, which allows dynamically allocating the Virtual Network Functions (VNFs) and therefore obtaining flexible network services provision, thus reducing the capital and operating costs. In this thesis, we focus on the VNF Placement and Routing (VNF-PR) problem, which aims to find the location of the VNFs to allocate optimally resources to serve the demands. From an optimization point of view, the problem can be modeled as the combination of a facility location problem (for the VNF location and server dimensioning) and a network design problem (for the demands routing). Both problems are widely studied in the literature, but their combination represents, to the best of our knowledge, a new challenge. We start working on a realistic VNF-PR problem to understand the impact of different policies on the overall network management cost and performance. To this end, we extend the work in [1] by considering more realistic features and constraints of NFV infrastructures and we propose a linear programming model and a math-heuristic to solve it. In order to better understand the problem structure and its properties, in the second part of our work, we focus on the theoretical study of the problem by extracting a simplified, yet significant variant. We provide results on the computational complexity under different graph topology and capacity cases. Then, we propose two mathematical programming formulations and we test them on a common testbed with more than 100 different test instances under different capacity settings. Finally, we address the scalability issue by proposing ILP-based constructive methods and heuristics to efficiently deal with large size instances (with up to 60 nodes and 1800 demands). We show that our proposed heuristics can efficiently solve medium size instances (with up to 30 nodes and 1000 demands) of challenging capacity cases and provide feasible solutions for large size instances of the most difficult capacity cases, for which the models cannot find any solution even with a significant computational time.

L'informatique en nuage (Cloud Computing) a émergé comme un nouveau paradigme pour offrir des ressources informatiques à la demande et pour externaliser des infrastructures logicielles et matérielles. Le Cloud Computing est rapidement et fondamentalement en train de révolutionner la façon dont les services informatiques sont mis à disposition et gérés. Ces services peuvent être demandés à partir d’un ou plusieurs fournisseurs de Cloud d’où le besoin de la mise en réseau entre les composants des services informatiques distribués dans des emplacements géographiquement répartis. Les utilisateurs du Cloud veulent aussi déployer et instancier facilement leurs ressources entre les différentes plateformes hétérogènes de Cloud Computing. Les fournisseurs de Cloud assurent la mise à disposition des ressources de calcul sous forme des machines virtuelles à leurs utilisateurs. Par contre, ces clients veulent aussi la mise en réseau entre leurs ressources virtuelles. En plus, ils veulent non seulement contrôler et gérer leurs applications, mais aussi contrôler la connectivité réseau et déployer des fonctions et des services de réseaux complexes dans leurs infrastructures virtuelles dédiées. Les besoins des utilisateurs avaient évolué au-delà d'avoir une simple machine virtuelle à l'acquisition de ressources et de services virtuels complexes, flexibles, élastiques et intelligents. L'objectif de cette thèse est de permettre le placement et l’instanciation des ressources complexes dans des infrastructures de Cloud distribués tout en permettant aux utilisateurs le contrôle et la gestion de leurs ressources. En plus, notre objectif est d'assurer la convergence entre les services de cloud et de réseau. Pour atteindre cela, nous proposons des algorithmes de mapping d’infrastructures virtuelles dans les centres de données et dans le réseau tout en respectant les exigences des utilisateurs. Avec l'apparition du Cloud Computing, les réseaux traditionnels sont étendus et renforcés avec des réseaux logiciels reposant sur la virtualisation des ressources et des fonctions réseaux. En plus, le nouveau paradigme d'architecture réseau (Software Defined Networks) est particulièrement pertinent car il vise à offrir la programmation du réseau et à découpler, dans un équipement réseau, la partie plan de données de la partie plan de contrôle. Dans ce contexte, la première partie propose des algorithmes optimaux (exacts) et heuristiques de placement pour trouver le meilleur mapping entre les demandes des utilisateurs et les infrastructures sous-jacentes, tout en respectant les exigences exprimées dans les demandes. Cela inclut des contraintes de localisation permettant de placer une partie des ressources virtuelles dans le même nœud physique. Ces contraintes assurent aussi le placement des ressources dans des nœuds distincts. Les algorithmes proposés assurent le placement simultané des nœuds et des liens virtuels sur l’infrastructure physique. Nous avons proposé aussi un algorithme heuristique afin d’accélérer le temps de résolution et de réduire la complexité du problème. L'approche proposée se base sur la technique de décomposition des graphes et la technique de couplage des graphes bipartis. Dans la troisième partie, nous proposons un cadriciel open source (framework) permettant d’assurer la mise en réseau dynamique entre des ressources Cloud distribués et l’instanciation des fonctions réseau dans l’infrastructure virtuelle de l’utilisateur. Ce cadriciel permettra de déployer et d’activer les composants réseaux afin de mettre en place les demandes des utilisateurs. Cette solution se base sur un gestionnaire des ressources réseaux "Cloud Network Gateway Manager" et des passerelles logicielles permettant d’établir la connectivité dynamique et à la demande entre des ressources cloud et réseau. Le CNG-Manager offre le contrôle de la partie réseau et prend en charge le déploiement des fonctions réseau nécessaires dans l'infrastructure virtuelle des utilisateurs / Cloud computing emerged as a new paradigm for on-demand provisioning of IT resources and for infrastructure externalization and is rapidly and fundamentally revolutionizing the way IT is delivered and managed. The resulting incremental Cloud adoption is fostering to some extent cloud providers cooperation and increasing the needs of tenants and the complexity of their demands. Tenants need to network their distributed and geographically spread cloud resources and services. They also want to easily accomplish their deployments and instantiations across heterogeneous cloud platforms. Traditional cloud providers focus on compute resources provisioning and offer mostly virtual machines to tenants and cloud services consumers who actually expect full-fledged (complete) networking of their virtual and dedicated resources. They not only want to control and manage their applications but also control connectivity to easily deploy complex network functions and services in their dedicated virtual infrastructures. The needs of users are thus growing beyond the simple provisioning of virtual machines to the acquisition of complex, flexible, elastic and intelligent virtual resources and services. The goal of this thesis is to enable the provisioning and instantiation of this type of more complex resources while empowering tenants with control and management capabilities and to enable the convergence of cloud and network services. To reach these goals, the thesis proposes mapping algorithms for optimized in-data center and in-network resources hosting according to the tenants' virtual infrastructures requests. In parallel to the apparition of cloud services, traditional networks are being extended and enhanced with software networks relying on the virtualization of network resources and functions especially through network resources and functions virtualization. Software Defined Networks are especially relevant as they decouple network control and data forwarding and provide the needed network programmability and system and network management capabilities. In such a context, the first part proposes optimal (exact) and heuristic placement algorithms to find the best mapping between the tenants' requests and the hosting infrastructures while respecting the objectives expressed in the demands. This includes localization constraints to place some of the virtual resources and services in the same host and to distribute other resources in distinct hosts. The proposed algorithms achieve simultaneous node (host) and link (connection) mappings. A heuristic algorithm is proposed to address the poor scalability and high complexity of the exact solution(s). The heuristic scales much better and is several orders of magnitude more efficient in terms of convergence time towards near optimal and optimal solutions. This is achieved by reducing complexity of the mapping process using topological patterns to map virtual graph requests to physical graphs representing respectively the tenants' requests and the providers' physical infrastructures. The proposed approach relies on graph decomposition into topology patterns and bipartite graphs matching techniques. The third part propose an open source Cloud Networking framework to achieve cloud and network resources provisioning and instantiation in order to respectively host and activate the tenants' virtual resources and services. This framework enables and facilitates dynamic networking of distributed cloud services and applications. This solution relies on a Cloud Network Gateway Manager and gateways to establish dynamic connectivity between cloud and network resources. The CNG-Manager provides the application networking control and supports the deployment of the needed underlying network functions in the tenant desired infrastructure (or slice since the physical infrastructure is shared by multiple tenants with each tenant receiving a dedicated and isolated portion/share of the physical resources)