Optimal Dynamic Cloud Network Control

Distributed cloud networking enables the deployment of network services in the form of interconnected virtual network functions instantiated over general purpose hardware at multiple cloud locations distributed across the network. The service distribution problem is to find the placement of virtual functions and the routing of network flows that meet a given set of demands with minimum cost. In this paper, we address the design of distributed online solutions that drive local routing, processing, and resource allocation decisions while providing global objective guarantees. We present a distributed joint transmission- processing flow scheduling and resource allocation algorithm that stabilizes the underlying cloud network queuing system, while achieving arbitrarily close to minimum average network cost (with a tradeoff in network delay) with probability one. We further enhance our algorithm with a shortest transmission-plus- processing distance bias that improves the delay performance without compromising throughput or overall cloud network cost. We provide simulation results that confirm our theoretical analysis, illustrate the effect of the shortest transmission-plus-processing distance bias, and demonstrate remarkably good convergence to the optimal cloud network configuration.