Automated Function Placement and Online Optimization of Network Functions Virtualization

This paper proposes a new fully decentralized approach to online placement and optimization of virtual machines (VMs) for network functions virtualization (NFV). The approach is of practical value, as network services comprising a chain of virtual network functions (VNFs) are proposed to be queued on the basis of leading unexecuted VNFs at every server, rather than on the typical basis of services, reducing queues per server and facilitating queue management and signaling. It is also non-trivial because the VNFs of network services must be executed correctly in order at different VMs, coupling the optimal decisions of VMs on processing or offloading. Exploiting Lyapunov optimization techniques, we decouple the optimal decisions by deriving and minimizing the instantaneous upper bound of the 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, achieving stable redeployment of VNFs, 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 with existing approaches.