Network Function Placement under Randomly Arrived Networking Traffic

The virtual network functions (VNFs) placement problem has drawn significant attention from both academia and industry in recent years. Most of the researchers have ignored the fact that the probability of traffic flows through VNFs cannot always be 100%. In this paper, we study the placement scheme for virtual network function considering randomized data traffic (VNFPRAT). Our objective is to determine optimal deployment locations for VNFs and minimize total end-to-end delay. We formulate the VNFPRAT problem as a 0-1 nonlinear programming problem and prove its NP-hardness. This formulation is linearized to obtain the optimal solution for small scale networks. Besides, two efficient metaheuristics, i.e., greedy and simulated annealing, are proposed quickly find a near-optimal placement solution. Extensive simulations demonstrate that our proposed approach achieves 38.8% less end-to-end delay than the generic algorithm.