I. Introduction
Cloud computing, a recently emerged computing paradigm, enables convenient and on-demand access to a virtually unlimited pool of computing resources, such as CPU, RAM and disk storage. Cloud providers exemplified by Amazon EC2 [1] and Microsoft Azure [2] manage the resources by assembling them into virtual machines (VMs), and pursue maximized revenue through properly pricing and allocating these VMs to cloud users. Cloud users enjoy the convenience, scalability and flexibility of the cloud service, and pay the provider a monetary remuneration that is usually a fraction of their utility gained from the cloud services.