一种支持云计算虚拟资源分配的可信多需求拍卖机制

张骥先; 谢宁; 李伟东; 岳昆; 张学杰

doi:10.11999/JEIT170353

一种支持云计算虚拟资源分配的可信多需求拍卖机制

doi: 10.11999/JEIT170353

1.
(云南大学信息学院昆明 650500) ②(云南大学资源环境与地球科学学院昆明 650500)

基金项目:

国家自然科学基金项目(61472345, 61402398, 11663007)，云南省应用基础研究计划项目(2014FA023, 2015FB115, 2014 FB114)，云南省教育厅科学研究基金项目(2017ZZX228)

计量
- 文章访问数: 1379
- HTML全文浏览量: 222
- PDF下载量: 240
- 被引次数: 0
出版历程
- 收稿日期: 2017-04-19
- 修回日期: 2017-07-17
- 刊出日期: 2018-01-19

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

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)

摘要

摘要: 使用拍卖方式来进行资源分配可以使得资源提供商获得更大的收益，是云计算领域近年来研究的重点。但现有研究多是基于非可信、单资源、单需求的前提。该文提出一种基于拍卖方式的云计算虚拟资源分配和定价机制(VRAP)。这种机制的特点在于，用户在一次拍卖中可以提出多个资源需求。证明了在这种机制下，资源提供商可以获得较以往拍卖机制更大的收益，同时能够保证用户出价是可信的。进而在具体资源分配问题上，提出一种单调的启发式算法能够在很短时间内计算出分配结果，通过资源稀有度概念设计了再分配策略，可以保证云资源提供商的收益极大化；在支付价格计算算法设计中，基于临界值理论计算支付价格，从而保证机制的公平可信。在社会福利、执行时间、资源利用率等多个方面对VRAP进行了测试分析，取得了很好的效果。
- 云计算 /
- 虚拟资源分配 /
- 多需求拍卖机制 /
- 社会福利 /
- 可信启发式算法
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

HTML全文

参考文献(14)

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.

施引文献

资源附件(0)

访问统计