Network Function Deployment with Balanced Server and Link Resources in Tree Topologies
Yang Chen, Jie Wu · 2019
Network function virtualization (NFV) enables flexible implementation of software middleboxes (network functions) as virtual machines running on standard servers. However, the flexibility also creates a challenge for efficiently placing such VNFs, due to the availability of multiple hosting servers and VNF capability of changing traffic volumes. In this paper, we address the placement problem of a special type of VNF with the traffic-diminishing effect (e.g., spam filters). We aim at minimizing the total bandwidth consumption of flows by placing at most a pre-determined number of VNFs. First, we formulate the Traffic-diminishing VNF Placement (TVP) as an optimization problem. We propose an optimal strategy for the tree-structured networks. Next, we extend the algorithm to the directed acyclic graph (DAG) topology. Then an approximation algorithm is designed after we prove the NP-hardness of our problem in a general topology. Extensive simulations are conducted on CAIDA dataset to evaluate the performance of our proposed algorithms in various scenarios.