1. Incremental Server Deployment for Software-Defined NFV-Enabled Networks
- Author
-
Hongli Xu, Gongming Zhao, Xuwei Yang, Jianchun Liu, Chen Qian, Xingpeng Fan, and He Huang
- Subjects
Computer Networks and Communications ,Computer science ,business.industry ,Approximation algorithm ,020206 networking & telecommunications ,02 engineering and technology ,Construct (python library) ,Computer Science Applications ,Software ,Software deployment ,Server ,Scalability ,0202 electrical engineering, electronic engineering, information engineering ,Overhead (computing) ,Electrical and Electronic Engineering ,Service innovation ,business ,Computer network - 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-\epsilon) \cdot \ln m$ , where $\epsilon $ 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\cdot H(q\cdot 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.
- Published
- 2020
- Full Text
- View/download PDF