Truthful Multi Requirements Auction Mechanism for Virtual Resource Allocation of Cloud Computing
ZHANG Jixian① XIE Ning① LI Weidong② YUE Kun① ZHANG Xuejie①
①(School of Information Science and Engineering, Yunnan University, Kunming 650500, China) ②(School of Resource Environment and Earth Science, Yunnan University, Kunming 650500, China)
Abstract：Auction based resource allocation is a major challenging problem for cloud computing. However, the existing research is based on untruthful, single resource, single requirement for the premise. In this paper, a truthful auction mechanism is designed for Virtual Resource Allocation and Payment (VRAP) in cloud computing. In this mechanism, users can submit multiple requests at one time, but only one request can be satisfied, known as multi requirements single mind. It is proved that the resource providers can obtain more social welfare under this mechanism than before, and it can guarantee the users’ bids are truthful. The mechanism is still compatible with the traditional auction which the user can only submit one request. For the resource allocation problem, a heuristic algorithm is proposed to get the allocation result in a short time, through the reallocation strategy, the social welfare of the cloud resource provider can be maximized. The payment algorithm takes into account critical value to ensure that the machnism is truthful. In the experiment, it is analyzed in terms of social welfare, execution time, resource utilization and so on. Experimental results show that the proposed scheme has good effect for virtual resource action.
JAIN N, MENACHE I, NAOR J S, et al. A truthful mechanism for value-based scheduling in cloud computing[J]. Theory of Computing Systems, 2014, 54(3): 388-406. doi: 10.1007/s00224-013-9449-0.
[3]
MASHAYEKHY L, NEJAD M M, and GROSU D. A PTAS mechanism for provisioning and allocation of heterogeneous cloud resources[J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(9): 2386-2399. doi: 10.1109/ TPDS.2014.2355228.
[4]
NEJAD M M, MASHAYEKHY L, and GROSU D. Truthful greedy mechanisms for dynamic virtual machine provisioning and allocation in clouds[J]. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(2): 594-603. doi: 10.1109/ TPDS.2014.2308224.
[5]
SANDHOLM T, SURI S, GILPIN A, et al. CABOB: A fast optimal algorithm for winner determination in combinatorial auctions[J]. Management Science, 2005, 51(3): 374-390. doi: 10.1287/mnsc.1040.0336.
[6]
WU Q and HAO J K. A clique-based exact method for optimal winner determination in combinatorial auctions[J]. Information Sciences, 2016, 334(c): 103-121. doi: 10.1016/j. ins.2015.11.029.
[7]
LAI J and PARKES D. Monotone branch-and-bound search for restricted combinatorial auctions[C]. Proceedings of the 13th ACM Conference on Electronic Commerce, New York, USA, 2012: 705-722. doi: 10.1145/2229012.2229067.
[8]
KELLERER H, PFERSCHY U, and PISINGER D. Knapsack Problems [M]. Berlin: Springer, 2004: 483-493.
[9]
ZAMAN S and GROSU D. Combinatorial auction-based dynamic VM provisioning and allocation in clouds[C]. Proceedings of the 2011 IEEE Third International Conference on Cloud Computing Technology and Science (CloudCom), Athens, Greece, 2011: 107-114. doi: 10.1109/ CloudCom.2011.24.
[10]
ZAMAN S and GROSU D. Combinatorial auction-based allocation of virtual machine instances in clouds[J]. Journal of Parallel and Distributed Computing, 2013, 73(4): 495-508. doi: 10.1109/CloudCom.2010.28.
[11]
MASHAYEKHY L, FISHER N, and GROSU D. Truthful mechanisms for competitive reward-based scheduling[J]. IEEE Transactions on Computers, 2016, 65(7): 2299-2312. doi: 10.1109/TC.2015.2479598.
YIN Bo, WANG Ying, QIU Xuesong, et al. A resource provisioning mechanism for service providers in cloud[J]. Journal of Electronics & Information Technology, 2014, 36(1): 15-21. doi: 10.3724/SP.J.1146.2013.00427.
[13]
TEO Y M and MIHAILESCU M. A strategy-proof pricing scheme for multiple resource type allocations[C]. Proceedings of International Conference on Parallel Processing, Vienna, Austria, 2009: 172-179. doi: 10.1109/ ICPP.2009.23.
[14]
NISAN T, ROUGHGARDEN T, TARDOS E, et al. Algorithmic Game Theory[M]. Cambridge: Cambridge Univ. Press, 2007: 218-233.
