Truthful Multi Requirements Auction Mechanism for Virtual Resource Allocation of Cloud Computing

ZHANG Jixian; XIE Ning; LI Weidong; YUE Kun; ZHANG Xuejie

doi:10.11999/JEIT170353

Volume 40 Issue 1

Jan. 2018

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2018 > 40(1): 25-34

ZHANG Jixian, XIE Ning, LI Weidong, YUE Kun, ZHANG Xuejie. Truthful Multi Requirements Auction Mechanism for Virtual Resource Allocation of Cloud Computing[J]. Journal of Electronics & Information Technology, 2018, 40(1): 25-34. doi: 10.11999/JEIT170353

Citation:

ZHANG Jixian, XIE Ning, LI Weidong, YUE Kun, ZHANG Xuejie. Truthful Multi Requirements Auction Mechanism for Virtual Resource Allocation of Cloud Computing[J]. Journal of Electronics & Information Technology, 2018, 40(1): 25-34. doi: 10.11999/JEIT170353

Citation:

PDF( 5039 KB)

Truthful Multi Requirements Auction Mechanism for Virtual Resource Allocation of Cloud Computing

doi: 10.11999/JEIT170353

1.
(School of Information Science and Engineering, Yunnan University, Kunming 650500, China)
2.
(School of Resource Environment and Earth Science, Yunnan University, Kunming 650500, China)

Funds:

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)

Received Date: 2017-04-19
Rev Recd Date: 2017-07-17
Publish Date: 2018-01-19

Abstract

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.
- Cloud computing,
- Virtual resource allocation,
- Multi-mind auction based mechanism,
- Social welfare,
- Truthful heuristic algorithm

FullText(HTML)

References(14)

References

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.

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.

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.

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.

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.

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.

KELLERER H, PFERSCHY U, and PISINGER D. Knapsack Problems [M]. Berlin: Springer, 2004: 483-493.

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.

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.

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.

殷波, 王颖, 邱雪松, 等. 一种面向云服务提供商的资源分配机制[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.

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.

NISAN T, ROUGHGARDEN T, TARDOS E, et al. Algorithmic Game Theory[M]. Cambridge: Cambridge Univ. Press, 2007: 218-233.

Relative Articles

Supplements(0)

Cited By

Proportional views