Dynamic Resource Provisioning in Cloud
Computing: A Randomized Auction Approach
∗ Department

Linquan Zhang∗ , Zongpeng Li∗ , Chuan Wu†

of Computer Science, University of Calgary, {linqzhan,zongpeng}@ucalgary.ca of Computer Science, The University of Hong Kong, cwu@cs.hku.hk

† Department

Abstract—This work studies resource allocation in a cloud market through the auction of Virtual Machine (VM) instances.
It generalizes the existing literature by introducing combinatorial auctions of heterogeneous VMs, and models dynamic VM provisioning. Social welfare maximization under dynamic resource provisioning is proven NP-hard, and modeled with a linear integer program. An efficient α-approximation algorithm is designed, with α ∼ 2.72 in typical scenarios. We then employ this algorithm as a building block for designing a randomized combinatorial auction that is computationally efficient, truthful in expectation, and guarantees the same social welfare approximation factor α. A key technique in the design is to utilize a pair of tailored primal and dual LPs for exploiting the underlying packing structure of the social welfare maximization problem, to decompose its fractional solution into a convex combination of integral solutions.
Empirical studies driven by Google Cluster traces verify the efficacy of the randomized auction.

I.

INTRODUCTION

The cloud computing paradigm offers users rapid ondemand access to computing resources such as CPU, RAM and storage, with minimal management overhead. Recent commercial cloud platforms, exemplified by Amazon EC2 [1],
Microsoft Azure and Linode [2], organize a shared resource pool for serving their users. Virtualization technologies help cloud providers pack their resources into different types of virtual machines (VMs), for allocation to cloud users. For example, Tab. I illustrates a number of VMs