Truthful Virtual Machine Allocation in Clouds Based on LP-relaxation

An auction mechanism is said to be truthful if every bidder can maximize her profit by declaring the true valuation of requested items. In this paper, we propose a truthful auction-based scheme to allocate virtual machine (VM) instances of various types to the users in clouds so that the total amount of valuations attained by the allocation is maximized. The proposed scheme is an extension of the greedy allocation scheme proposed by Lehmann et al. so that it solves the corresponding winner determination problem by using LP (linear programming) relaxation. The performance of the proposed scheme is evaluated by simulation. The simulation results indicate that it outperforms conventional schemes including fixed-price scheme with respect to the resource utilization, revenue generation, and the allocation efficiency.