Models and Methods for Network Function Virtualization (NFV) Architectures

Meihui Gao 1
1 OPTIMIST - OPTImisation Methods for Integrated SysTems
LORIA - NSS - Department of Networks, Systems and Services
Abstract : 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.
Complete list of metadatas

Cited literature [119 references]  Display  Hide  Download

https://hal.univ-lorraine.fr/tel-02132766
Contributor : Thèses Ul <>
Submitted on : Friday, May 17, 2019 - 2:59:07 PM
Last modification on : Sunday, May 19, 2019 - 1:20:44 AM

File

DDOC_T_2019_0025_GAO.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-02132766, version 1

Citation

Meihui Gao. Models and Methods for Network Function Virtualization (NFV) Architectures. Networking and Internet Architecture [cs.NI]. Université de Lorraine, 2019. English. ⟨NNT : 2019LORR0025⟩. ⟨tel-02132766⟩

Share

Metrics

Record views

134

Files downloads

149