一種支持云計(jì)算虛擬資源分配的可信多需求拍賣機(jī)制

張驥先; 謝寧; 李偉東; 岳昆; 張學(xué)杰

doi:10.11999/JEIT170353

一種支持云計(jì)算虛擬資源分配的可信多需求拍賣機(jī)制

doi: 10.11999/JEIT170353

1.
(云南大學(xué)信息學(xué)院昆明 650500) ②(云南大學(xué)資源環(huán)境與地球科學(xué)學(xué)院昆明 650500)

基金項(xiàng)目:

國家自然科學(xué)基金項(xiàng)目(61472345, 61402398, 11663007)，云南省應(yīng)用基礎(chǔ)研究計(jì)劃項(xiàng)目(2014FA023, 2015FB115, 2014 FB114)，云南省教育廳科學(xué)研究基金項(xiàng)目(2017ZZX228)

計(jì)量
- 文章訪問數(shù): 1414
- HTML全文瀏覽量: 229
- PDF下載量: 240
- 被引次數(shù): 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)

摘要

摘要: 使用拍賣方式來進(jìn)行資源分配可以使得資源提供商獲得更大的收益，是云計(jì)算領(lǐng)域近年來研究的重點(diǎn)。但現(xiàn)有研究多是基于非可信、單資源、單需求的前提。該文提出一種基于拍賣方式的云計(jì)算虛擬資源分配和定價機(jī)制(VRAP)。這種機(jī)制的特點(diǎn)在于，用戶在一次拍賣中可以提出多個資源需求。證明了在這種機(jī)制下，資源提供商可以獲得較以往拍賣機(jī)制更大的收益，同時能夠保證用戶出價是可信的。進(jìn)而在具體資源分配問題上，提出一種單調(diào)的啟發(fā)式算法能夠在很短時間內(nèi)計(jì)算出分配結(jié)果，通過資源稀有度概念設(shè)計(jì)了再分配策略，可以保證云資源提供商的收益極大化；在支付價格計(jì)算算法設(shè)計(jì)中，基于臨界值理論計(jì)算支付價格，從而保證機(jī)制的公平可信。在社會福利、執(zhí)行時間、資源利用率等多個方面對VRAP進(jìn)行了測試分析，取得了很好的效果。
- 云計(jì)算 /
- 虛擬資源分配 /
- 多需求拍賣機(jī)制 /
- 社會福利 /
- 可信啟發(fā)式算法
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全文

參考文獻(xiàn)(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.

殷波, 王穎, 邱雪松, 等. 一種面向云服務(wù)提供商的資源分配機(jī)制[J]. 電子與信息學(xué)報, 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.

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪問統(tǒng)計(jì)