Reservation schemes for IaaS cloud broker: A time-multiplexing way for different rental time

Infrastructure-as-a-Service cloud providers always charge users in 2 ways: on-demand billing and reservation billing with different discounts. On-demand billing is more flexible for short-term use but with higher cost, while reservation billing is much cheaper for long renting period but may cause inefficiency because of underutilized capacity. As middle agent, cloud broker always tries to reserve a large number of virtual machine (VM) instances from cloud providers to meet the requirement of all users, while making high profit through reducing its cost by leveraging long-term reservations and time-multiplexing of instances. Different from existing work, we believe that the rental time of each user's request should be served consecutively in one VM instance, rather than partitioned into different VM instances by cloud broker to enhance time-multiplexing ratio. In this paper, we first try to smooth users' unordered and time-overlapping requests using demand graph, based on which we propose two reservation algorithms for cloud broker, one for off-line and the other for online. We also consider cloud broker with multiple service providers, finding that much more cost can be saved by leveraging the various reservation discounts of those providers. Extensive simulations have been done on the traces from real cloud platforms. Experiment results show that the broker cost can be substantially saved using our off-line and online algorithms.