Cloud Cost Optimization : Model, Bounds, and Asymptotics

Motivated by the rapid growth of the Cloud Cost Management and Optimization (CCMO) industry to support the exploding cloud-computing market, we study an infinite-horizon, stochastic optimization problem from the viewpoint of a firm that employs cloud resources to process incoming orders (or jobs) over time. We model the following vital practical features of CCMO in our problem. There are several types of resources that differ in their costs and performance attributes (e.g., processor speed, memory, storage). For each type of resource, capacity can either be reserved over the long term at a discounted price or used on-demand at a relatively higher price. Orders of several types arrive stochastically through time -- orders differ in their completion-time deadlines and in their resource-specific processing-time distributions. Moreover, the progress of an order can be observed periodically and, if required, the order can be moved from one resource-type to another. Penalty costs are incurred for orders not completed by their deadlines. The firm's goal is to minimize the long-run average expected cost per period, taking into account reserved-capacity costs, on-demand capacity costs, and order-delay costs. We derive a lower bound on the optimal cost by considering a set of decoupled problems, one for each order. The solutions of these problems are then used to construct a feasible policy for the original problem and derive an upper bound on that policy's optimality gap. Importantly, we show that our policy is {\em asymptotically optimal}: when the demand-rates of the orders are scaled by a factor~$\theta > 0$, the policy's optimality gap scales proportional to $1 / \sqrt{\theta}$. We also report results of a comprehensive numerical study -- on a test-bed informed by capacity and pricing data from Amazon Web Services~-- to demonstrate the impressive performance of our policy