The Cloud Service Distribution Problem in Distributed Cloud Networks

The cloud service distribution problem (CSDP) is to find the placement of both content and virtual cloud service functions (vCSFs) over a distributed cloud network platform, that meets user requests, satisfies network resource capacities and minimizes overall network cost. We formulate the CSDP as a minimum cost flow problem in which cloud services are represented by a service graph that encodes the relationship between input and output information flows via the virtual functions that create them. As a result, the CSDP can be efficiently formulated using only linear constraints and solved via integer linear programming (ILP). Our solution jointly optimizes the use of compute, storage and transport resources in arbitrary cloud network topologies, and is able to capture flexible service chaining, resource consolidation savings, unicast and multicast delivery, and latency constraints. We further provide conditions for which a relaxed version of the presented ILP leads to optimal polynomial-time solutions. We finally present results for an illustrative sample of future cloud services that show the advantage of optimizing the placement of content and vCSFs over a programmable distributed cloud network.