Combinatorial auction-based allocation of virtual machine instances in clouds

Most of the current cloud computing providers allocate virtual machine instances to their users through fixed-price allocation mechanisms. We argue that combinatorial auction-based allocation mechanisms are especially efficient over the fixed-price mechanisms since the virtual machine instances are assigned to users having the highest valuation. We formulate the problem of virtual machine allocation in clouds as a combinatorial auction problem and propose two mechanisms to solve it. The proposed mechanisms are extensions of two existing combinatorial auction mechanisms. We perform extensive simulation experiments to compare the two proposed combinatorial auction-based mechanisms with the currently used fixed-price allocation mechanism. Our experiments reveal that the combinatorial auction-based mechanisms can significantly improve the allocation efficiency while generating higher revenue for the cloud providers.

► Two combinatorial auction-based mechanisms for VM instance allocation in clouds, called CA-LP and CA-GREEDY are proposed.
► The two mechanisms improve significantly the efficiency of allocation.
► The two mechanisms generate higher revenue for the cloud provider when compared with currently used fixed-price mechanisms.
► Experimental evaluation of CA-LP and CA-GREEDY under various system configurations and user demands is carried out.