Migration Aware Virtual Network Function Placing and Routing in Uncertain Environment
Yanghao Xie, Sheng Wang, Binbin Wang, Long Luo · 2020
Network Function Virtualization (NFV) aims to provide a way to build agile and service-aware networks by building a new paradigm of provisioning network services where physical network functions are deployed as Virtual Network Functions (VNFs). However, how to optimally allocate resources in the uncertain NFV environment where flow rates fluctuate has not been fully resolved. In this paper, we study the cost minimizing problem of VNF placing and routing optimization while two goals are considered: optimizing service migration caused by flow fluctuation and stabilizing queue backlogs in the network. We first formulate the problem as a stochastic optimization programming problem. Then we propose an online algorithm, named Migration Aware VNF plaCing and Routing Online algorithm (MACRO), based on Lyapunov optimization technique. MACRO can make good decisions without knowing any future information. The theoretical analysis suggests that MACRO achieves an optimality gap of O([1/(V)]) and the queue backlogs are bounded by O(V), where V is a tunable parameter that controls the tradeoff between cost and backlogs. The experiment results suggest that MACRO achieves queue stability and outperforms benchmark algorithm by 6% in terms of cost.