Incremental Server Deployment for Software-Defined NFV-Enabled Networks
- 22 October 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. PP (10636692) , 1-14
Abstract
Network Function Virtualization (NFV) is a new paradigm to enable service innovation through virtualizing traditional network functions. To construct a new NFV-enabled network, there are two critical requirements: minimizing server deployment cost and satisfying switch resource constraints. However, prior work mostly focuses on the server deployment cost, while ignoring the switch resource constraints (e.g., switch's flow-table size). It thus results in a large number of rules on switches and leads to massive control overhead. To address this challenge, we propose an incremental server deployment (INSD) problem for construction of scalable NFV-enabled networks. We prove that the INSD problem is NP-Hard, and there is no polynomial-time algorithm with approximation ratio of (1-ε) · łn m, where ε is an arbitrarily small value and m is the number of requests in the network. We then present an efficient algorithm with an approximation ratio of 2· H(q· p), where q is the number of VNF's categories and p is the maximum number of requests through a switch. We evaluate the performance of our algorithm with experiments on physical platform (Pica8), Open vSwitches, and large-scale simulations. Both experimental results and simulation results show high scalability of the proposed algorithm. For example, our solution can reduce the control and rule overhead by about 88% with about 5% additional server deployment, compared with the existing solutions.Keywords
Funding Information
- National Science Foundation of China NSFC (61822210, 61936015, U1709217)
- Anhui Initiative in Quantum Information Technologies (AHY150300)
- National Natural Science Foundation of China (61873177)
This publication has 40 references indexed in Scilit:
- An efficient local search heuristic with row weighting for the unicost set covering problemEuropean Journal of Operational Research, 2015
- Piecing together the NFV provisioning puzzle: Efficient placement and chaining of virtual network functions2015
- The virtual network function placement problem2015
- Network Function Placement for NFV Chaining in Packet/Optical DatacentersJournal of Lightwave Technology, 2015
- NFV: state of the art, challenges, and implementation in next generation mobile networks (vEPC)IEEE Network, 2014
- Making middleboxes someone else's problemACM SIGCOMM Computer Communication Review, 2012
- A scalable, commodity data center network architectureACM SIGCOMM Computer Communication Review, 2008
- What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization2005
- Measuring ISP topologies with rocketfuelACM SIGCOMM Computer Communication Review, 2002
- A threshold of ln n for approximating set coverJournal of the ACM, 1998