Network Function Virtualization (NFV) can cost-efficiently provide network services by running different virtual network functions (VNFs) at different virtual machines (VMs) in a correct order. This can result in strong couplings between the decisions of the VMs on the placement and operations of VNFs. This paper presents a new fully decentralized online approach for optimal placement and operations of VNFs. Building on a new stochastic dual gradient method, our approach decouples the real-time decisions of VMs, asymptotically minimizes the time-average cost of NFV, and stabilizes the backlogs of network services with a cost-backlog tradeoff of [ϵ,1/ϵ], for any ϵ>0. Our approach can be relaxed into multiple timescales to have VNFs (re)placed at a larger timescale and hence alleviate service interruptions. While proved to preserve the asymptotic optimality, the larger timescale can slow down the optimal placement of VNFs. A learn-and-adapt strategy is further designed to speed the placement up with an improved tradeoff [ϵ,log2(ϵ)/ϵ]. Numerical results show that the proposed method is able to reduce the time-average cost of NFV by 23 percent and reduce the queue length (or delay) by 74 percent, as compared to existing benchmarks.
Bibliographical noteFunding Information:
The work in this paper was supported by the National Natural Science Foundation of China grant 61671154, the National Science and Technology Major Project grant 2018ZX03001009, the National Key Research and Development Program of China grant 2017YFB0403402, the Innovation Program of Shanghai Municipal Science and Technology Commission grant 17510710400, and the US NSF grants 1509005, 1508993, 1423316, and 1442686. X. Chen was with Fudan University and Macquarie University while this work was done.
- Network function virtualization
- distributed optimization
- stochastic approximation
- virtual machine