Les prestataires de service réseau doivent faire face à la demande croissante des besoins des utilisateurs, en particulier vers une plus grande flexibilité et toujours plus de capacité. La "softwerisation" et la "cloudification" des composants du réseau offrent une solution prometteuse pour obtenir l'agilité nécessaire afin de répondre dynamiquement à l'exigence au niveau de la consommation des ressources. Cette vision se traduit par le déploiement de la Virtualisation des Fonctions Réseau (NFV) où les Fonctions de Réseau Virtuels (VNFs) peuvent être associées pour créer des services réseau. Cette thèse étudie la problématique de l'allocation de ressources dans un système NFV afin de minimiser son coût sous contraintes sur l'interconnectivité entre les VNF, les ressources du système et les exigences de service. La principale considération est la réduction du coût global du déploiement en ressources informatiques. Nous étudions également d'autres objectifs à satisfaire tels que la migration des fonctions réseau et la gestion de la congestion. Notre premier objectif est d'augmenter notre compréhension de la performance d'un système NFV en étudiant le placement et le routage des fonctions réseau. Nous formalisons le problème dans une approche globale en tenant compte d'un large ensemble de paramètres pertinents. Nous prendrons en compte les cas statiques (Hors Ligne) et dynamiques (En Ligne) du problème. Nous proposons et analysons trois algorithmes heuristiques: deux sont conçus pour traiter de grandes dimensions du scenario "Hors Ligne" et le dernier est conçu pour résoudre le scénario "En Ligne". Les résultats montrent que notre solution surpasse l'état de l'art par rapport à l'indicateur de performance critique. Nous évaluons également l'impact de la migration d'une série de demandes simultanées et proposons une technique de migration simple pour ce système dynamique. A la lumière de ces premiers résultats, nous étendons notre étude afin d'améliorer l'efficacité de notre solution en proposant un modèle plus simple. La seconde partie de notre étude se concentre sur l'optimisation de l'utilisation des ressources d'un système NFV. La principale distinction est que nous pouvons appliquer le modèle à un système dynamique avec de grandes instances. De plus, nous fournissons également une méthode originale pour engendrer de fortes inégalités afin d'améliorer la résolution de la programmation linéaire (LP) dans un espace de dimension supérieur. Les résultats obtenus n'améliorent pas seulement le modèle, mais promettent aussi de pouvoir être utiliser efficacement dans d'autres modèles. Une troisième contribution de notre travail concerne le problème de routage dans NFV. En effet, une évolution importante des besoins des utilisateurs est représentée par la demande d'accès croissante aux ressources réseau, de stockage et de calcul afin de combiner dynamiquement le niveau de consommation de ressources avec leurs besoins de service. Par conséquent, nous nous intéressons au routage efficace d'une demande utilisateur à travers les noeuds qui traitent les fonctions impliquées dans une chaîne de services donnée. Nous proposons une formulation originale de ce problème basée sur la construction d'un réseau étendu. Nous formulons une solution mathématique exacte et proposons plusieurs algorithmes approximatifs tenant compte les principaux paramètres du système. Nous conclurons en soulignant les contributions principales de notre travail et proposons quelques pistes pour des travaux futurs. / Network service providers have to cope with the growing on-demand need from end-users as well as the diversity of usage. The "softwerization" and "loudification" of the network components offer a promising solution to achieve the agility necessary to dynamically match the servcice requirements with the level of resource consumption. Cloud-based solutions promises an economy of scale and simpler management. Virtualizing the many network appliances offers the flexibility to adapt to the varying service demand. This materializes with the deployment of Network Functions Virtualization (NFV) where Virtual Network Functions (VNFs) may be chained together to create network services. This dissertation studies the resource allocation problem in an NFV system for minimizing its cost under constraints on interconnectivity among VNFs, system resources, and service requirements. The main consideration is the reduction of the overall deployment cost while efficiently utilizing the available resources. In addition, a number of other important constraints are considered such as migration and congestion. Our first goal is to increase our understanding of the performance of an NFV system with respect to network functions placement and routing. We formalize the problem in a comprehensive maner taking into account a broad set of relevant parameters. The static (OFFLINE) and dynamic (ONLINE) cases are considered. We propose and analyze three heuristic algorithms: two for handling large dimensions of the OFFLINE problem and one designed to address the ONLINE scenario. The results show that our solution outperforms the state of the art with respect to critical performance index. We also evaluate the impact of migrating a set of running demands, and propose a simple migration technique for the dynamic system. We extend this work by proposing a simpler model to improve the performance of our solution. The second part of our work focuses on minimizing the resource utilization of an NFV system. The main distinctive point is that we can apply the model to a dynamic system with large instances. Moreover, we also provide an interesting method for generating some strong inequalities to improve the Linear Programming (LP) solving in a higher dimensional space. The obtained results are not only making the model easier but also can be used efficiently in other models. A third contribution focuses specifically on the routing problem in NFV. An important evolution of the users’ needs is represented by the dynamic on-demand access to network, vstorage and compute resources. Therefore, routing efficiently a demand across nodes handling the functions involved in a given service chain constitutes the a novel problem that we address in this last section. We provide an original formulation of this problem based on the construction of an expanded network. We derive the exact mathematical formulation and propose several approximate algorithms taking into account the main system’s parameters. We conclude by deriving some interesting insights both about the algorithms and the network performance. We finally conclude with our main findings and highlight many avenues for future work.

La densification de réseau à l'aide de petites cellules massivement déployées sur les zones macro-cellules, représente une solution prometteuse pour les réseaux mobiles 5G avenir pour faire face à l'augmentation du trafic mobile. Afin de simplifier la gestion de l'hétérogène du réseau d'accès radio (Radio Access Network RAN) qui résulte du déploiement massif de petites cellules, des recherches récentes et des études industrielles ont favorisé la conception de nouvelles architectures de RAN centralisés appelés comme Cloud-RAN (C-RAN), ou RAN virtuel (V-RAN), en incorporant les avantages du cloud computing et Network Functions Virtualization (NFV). Le projet de DynaRoC vise l'élaboration d'un cadre théorique de l'orchestration de ressources pour les C-RAN et dériver les limites de performance fondamentaux ainsi que les arbitrages entre les différents paramètres du système, et la conception de mécanismes d'orchestration de ressources dynamiques sur la base des conclusions théoriques à atteindre un équilibre de performance souhaité, en tenant compte des différents défis de conception. Le doctorant va étudier les mécanismes d'optimisation des ressources novatrices pour favoriser le déploiement de C-RAN, améliorer leur performance exploitant la technologie Network Functions Virtualization / Network densification using small cells massively deployed over the macro-cell areas, represents a promising solution for future 5G mobile networks to cope with mobile traffic increase. In order to simplify the management of the heterogeneous Radio Access Network (RAN) that results from the massive deployment of small cells, recent research and industrial studies have promoted the design of novel centralized RAN architectures termed as Cloud-RAN (C-RAN), or Virtual RAN (V-RAN), by incorporating the benefits of cloud computing and Network Functions Virtualization (NFV). The DynaRoC project aims at (1) developing a theoretical framework of resource orchestration for C-RAN and deriving the fundamental performance limits as well as the tradeoffs among various system parameters, and (2) designing dynamic resource orchestration mechanisms based on the theoretical findings to achieve a desired performance balance, by taking into account various design challenges. The PhD student will investigate innovative resource optimization mechanisms to foster the deployment of C-RANs, improving their performance exploiting the enabling Network Functions Virtualization technology