NGUYEN Thi Minh

PhD student at Sorbonne University
Team : NPA
https://lip6.fr/Thi-Minh.Nguyen

Supervision : Serge FDIDA

Optimization of Resource Allocation in Network Function Virtualization Infrastructure

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 “cloudification" of the network components offer a promising solution to achieve the agility necessary to dynamically match the service 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 manner 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, storage 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.

Defence : 12/07/2017

Jury members :

M. Kavé SALAMATIAN - Professor, Université de Savoie
M. Fabio MARTIGNON - Professor, Université Paris-Sud
M. Vania CONAN - Research Director, Thales Communications & Security
M. Marinho P BARCELLOS - Associate Professor, INF/UFRGS
M. Michel MINOUX - Professor, Université Pierre et Marie Curie
Mme. Anne FLADENMULLER - Associate Professor, Université Pierre et Marie Curie
M. Tuan-Minh PHAM - Doctor, Thuy Loi University, Vietnam
M. Serge FDIDA - Professor, Université Pierre et Marie Curie

Departure date : 12/31/2017

2017-2019 Publications