Multi-Timescale Online Optimization of Network Function Virtualization for Service Chaining
This work addresses the challenge of decentralized, real-time VNF management for NFV providers, offering a scalable solution with provable optimality and significant performance gains.
The paper tackles the problem of optimal placement and operations of virtual network functions (VNFs) in network function virtualization (NFV) for service chaining. It proposes a fully decentralized online approach that asymptotically minimizes time-average cost with a cost-backlog tradeoff of [ε, 1/ε], achieving 30% cost reduction and 83% queue length reduction compared to benchmarks.
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(ε)/{\sqrtε}]$. Numerical results show that the proposed method is able to reduce the time-average cost of NFV by 30\% and reduce the queue length (or delay) by 83\%, as compared to existing benchmarks.