Supervised Learning Based Truthful Auction Mechanism Design in Cloud Computing

Jixian ZHANG; Ning XIE; Xuejie ZHANG; Weidong LI

doi:10.11999/JEIT180587

Volume 41 Issue 5

Apr. 2019

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2019 > 41(5): 1243-1250

Jixian ZHANG, Ning XIE, Xuejie ZHANG, Weidong LI. Supervised Learning Based Truthful Auction Mechanism Design in Cloud Computing[J]. Journal of Electronics & Information Technology, 2019, 41(5): 1243-1250. doi: 10.11999/JEIT180587

Citation:

Jixian ZHANG, Ning XIE, Xuejie ZHANG, Weidong LI. Supervised Learning Based Truthful Auction Mechanism Design in Cloud Computing[J]. Journal of Electronics & Information Technology, 2019, 41(5): 1243-1250. doi: 10.11999/JEIT180587

Citation:

PDF( 1937 KB)

Supervised Learning Based Truthful Auction Mechanism Design in Cloud Computing

doi: 10.11999/JEIT180587 cstr: 32379.14.JEIT180587

1.
School of Information Science and Engineering, Yunnan University, Kunming 650500, China
2.
School of Mathematics and Statistics, Yunnan University, Kunming 650500, China

Funds: The National Natural Science Foundation of China (61472345, 61762091, 11663007), The Scientific Research Foundation of Department of Education of Yunnan Province (2017ZZX228)

Received Date: 2018-06-13
Rev Recd Date: 2018-12-24

Available Online: 2019-01-02

Publish Date: 2019-05-01

Abstract

Abstract

Auction based resource allocation can make resource provider get more profit, which is a major challenging problem for cloud computing. However, the resource allocation problem is NP-hard and can not be solved in polynomial time. Existing studies mainly use approximate algorithms or heuristic algorithms to implement resource allocation in auction, but these algorithms have the disadvantages of low computational efficiency or low allocate accuracy. In this paper, the classification and regression of supervised learning is used to model and analyze multi-dimensional cloud resource allocation, for the different scale of problem, three resource allocation predict algorithms based on linear regression, logistic regression and Support Vector Machine (SVM) are proposed. Through the learning of the small-scale training set, the predict model can guarantee that the social welfare, allocation accuracy, and resource utilization in the feasible solution are very close to the optimal allocation solution. The payment price algorithm based on the critical value theory is proposed which ensure the truthful property of the auction mechanism design. Final experimental results show that the proposed scheme has good effect for resource allocation in cloud computing.
- Cloud computing,
- Resource allocation,
- Mechanism design,
- Supervised learning

FullText(HTML)

References(17)

References

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

LEHMANN D, O’CALLAGHAN L, and SHOHAM Y. Truth revelation in approximately efficient combinatorial auctions[J]. Journal of the ACM, 2002, 49(5): 577–602. doi: 10.1145/585265.585266

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

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

WU Qinghua and HAO Jinkao. 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, Valencia, Spain, 2012: 705–722.

BANSAL N, FRIGGSTAD Z, KHANDEKAR R, et al. A logarithmic approximation for unsplittable flow on line graphs[C]. Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, New York, USA, 2009: 702–709.

CHAKRABARTI A, CHEKURI C, GUPTA A, et al. Approximation algorithms for the unsplittable flow problem[J]. Algorithmica, 2007, 47(1): 53–78. doi: 10.1007/s00453-006-1210-5

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

SHI Weijie, ZHANG Linquan, WU Chuan, et al. An online auction framework for dynamic resource provisioning in cloud computing[J]. IEEE/ACM Transactions on Networking, 2016, 24(4): 2060–2073. doi: 10.1109/TNET.2015.2444657

LIU Xi, LI Weidong, and ZHANG Xuejie. Strategy-proof mechanism for provisioning and allocation virtual machines in heterogeneous clouds[J]. IEEE Transactions on Parallel and Distributed Systems, 2018, 29(7): 1650–1663. doi: 10.1109/TPDS.2017.2785815

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.

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

ZHANG Jixian, XIE Ning, ZHANG Xuejie, et al. An online auction mechanism for cloud computing resource allocation and pricing based on user evaluation and cost[J]. Future Generation Computer Systems, 2018, 89: 286–299. doi: 10.1016/j.future.2018.06.034

张骥先, 谢宁, 李伟东, 等. 一种支持云计算虚拟资源分配的可信多需求拍卖机制[J]. 电子与信息学报, 2018, 40(1): 25–34. doi: 10.11999/JEIT170353

ZHANG Jixian, XIE Ning, LI Weidong, et al. 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

ZHANG Jixian, XIE Ning, ZHANG Xuejie, et al. Machine learning based resource allocation of cloud computing in auction[J]. Computers Materials & Continua, 2018, 56(1): 123–135. doi: 10.3970/cmc.2018.03728

Grid Workloads Archives[OL]. http://gwa.ewi.tudelft.nl,2018.2.

Relative Articles

Supplements(0)

Cited By

Proportional views