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

8 Citations (Scopus)


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 [ε, log 2(ε)/√ε]. Numerical results show that the proposed method is able to reduce the time-average cost of NFV by 23% and reduce the queue length (or delay) by 74%, as compared to existing benchmarks.

Original languageEnglish
Pages (from-to)2899-2912
Number of pages14
JournalIEEE Transactions on Mobile Computing
Issue number12
Early online date10 Dec 2018
Publication statusPublished - 1 Dec 2019


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