Cloud computing has recently emerged as a popular paradigm for harnessing a large number of commodity machines. In this paradigm, users acquire computational and storage resources based on a pricing scheme similar to the economic exchanges in the utility market place: users can lease the resources they need in a pay-as-you-go manner [1]. For example, the Amazon Simple Storage Service (S3) is using a pricing scheme based on data size/transfer per Gigabyte (e.g., $0.095 per GB for the rst terabyte and $0.020 per GB inter-region transfer [2]) and the Amazon Elastic Compute Cloud (EC2) service is using a pricing scheme based on virtual machine (VM) hours (e.g., $0.065 per small instance hour [3]).