Distributed Placement and Online Optimization of Virtual Machines for Network Service Chains

This paper proposes a new fully decentralized approach for online placement and optimization of virtual machines (VMs) for network functions virtualization (NFV). The approach is non-trivial as the virtual network functions (VNFs) constituting network services must be executed correctly in order at different VMs, coupling the optimal decisions of VMs on processing or forwarding. Leveraging Lyapunov optimization techniques, we decouple the optimal decisions by minimizing the instantaneous NFV cost in a distributed fashion, and achieve the asymptotically minimum time-average cost. We also reduce the queue length by allowing individual VMs to (un)install VNFs based on local knowledge, adapting to the network topology and the temporal and spatial variations of services. Simulations show that the proposed approach is able to reduce the time-average cost of NFV by 71% and reduce the queue length (or delay) by 74%, as compared to existing approaches.