Multi-Timescale Online Optimization of Network Function Virtualization for Service Chaining

Xiaojing Chen, Wei Ni, Tianyi Chen, Iain B. Collings, Xin Wang, Ren Ping Liu, Georgios B. Giannakis

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


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.

Original languageEnglish (US)
Article number8570806
Pages (from-to)2899-2912
Number of pages14
JournalIEEE Transactions on Mobile Computing
Issue number12
StatePublished - Dec 1 2019

Bibliographical note

Funding 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.

Publisher Copyright:
© 2018 IEEE.


  • Network function virtualization
  • distributed optimization
  • stochastic approximation
  • virtual machine


Dive into the research topics of 'Multi-Timescale Online Optimization of Network Function Virtualization for Service Chaining'. Together they form a unique fingerprint.

Cite this