|
|
|
| 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.
|
|
Received: 19 April 2017
Published: 28 August 2017
|
|
|
| Fund:The National Natural Science Foundation of China (61472345, 61402398, 11663007), The Project of Natural Science Foundation of Yunnan Province (2014FA023, 2015FB115, 2014FB114), The Scientific Research Foundation of Yunnan Provincial Department of Education (2017ZZX228) |
|
Corresponding Authors:
LI Weidong
E-mail: weidong@ynu.edu.cn
|
|
|
|
| [1] |
Amazon EC2 Instance Types[OL]. http://aws.amazon.Com /ec2/instance-types/. 2016.11.
|
| [2] |
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.
|
| [12] |
殷波, 王颖, 邱雪松, 等. 一种面向云服务提供商的资源分配机制[J]. 电子与信息学报, 2014, 36(1): 15-21. doi: 10.3724/ SP.J.1146.2013.00427.
|
|
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.
|
| [15] |
Grid Workloads Archives[OL]. http://gwa.ewi. tudelft.nl. 2016.11.
|
|
|
|
