Optimal Dynamic Cloud Network Control

Distributed cloud networking enables the deployment of a wide range of services in the form of interconnected software functions instantiated over general purpose hardware at multiple cloud locations distributed throughout the network. We consider the problem of optimal service delivery over a distributed cloud network, in which nodes are equipped with both communication and computation resources. We address the design of distributed online solutions that drive flow processing and routing decisions, along with the associated allocation of cloud and network resources. For a given set of services, each described by a chain of service functions, we characterize the cloud network capacity region and design a family of dynamic cloud network control (DCNC) algorithms that stabilize any service input rate inside the capacity region, while achieving arbitrarily close to minimum resource cost. The proposed DCNC algorithms are derived by extending Lyapunov drift-plus-penalty control to a novel multi-commodity-chain (MCC) queuing system, resulting in the first throughput and cost optimal algorithms for a general class of MCC flow problems that generalizes traditional multi-commodity flow by including flow chaining, flow scaling, and joint communication/computation resource allocation. We provide throughput and cost optimality guarantees, convergence time analysis, and extensive simulations in representative cloud network scenarios.