Optimal Resource Allocation in Clouds

Cloud platforms enable enterprises to lease computing power in the form of virtual machines. An important problem for such enterprise users is to understand how many and what kinds of virtual machines will be needed from clouds. We formulate demand for computing power and other resources as a resource allocation problem with multiplicity, where computations that have to be performed concurrently are represented as tasks and a later task can reuse resources released by an earlier task. We show that finding a minimized allocation is NP-complete. This paper presents an approximation algorithm with a proof of its approximation bound that can yield close to optimum solutions in polynomial time. Enterprise users can exploit the solution to reduce the leasing cost and amortize the administration overhead (e.g., setting up VPNs or configuring a cluster). Cloud providers may utilize the solution to share their resources among a larger number of users.