×

A combinatorial double auction resource allocation model in cloud computing. (English) Zbl 1429.91177

Summary: Users and providers have different requirements and objectives in an investment market. Users will pay the lowest price possible with certain guaranteed levels of service at a minimum and providers would follow the strategy of achieving the highest return on their investment. Designing an optimal market-based resource allocation that considers the benefits for both the users and providers is a fundamental criterion of resource management in distributed systems, especially in cloud computing services. Most of the current market-based resource allocation models are biased in favor of the provider over the buyer in an unregulated trading environment. In this study, the problem was addressed by proposing a new market model called the combinatorial double auction resource allocation (CDARA), which is applicable in cloud computing environments. The CDARA was prototyped and simulated using CloudSim, a Java-based simulator for simulating cloud computing environments, to evaluate its efficiency from an economic perspective. The results proved that the combinatorial double auction-based resource allocation model is an appropriate market-based model for cloud computing because it allows double-sided competition and bidding on an unrestricted number of items, which causes it to be economically efficient. Furthermore, the proposed model is incentive-compatible, which motivates the participants to reveal their true valuation during bidding.

MSC:

91B26 Auctions, bargaining, bidding and selling, and other market models
91B32 Resource and cost allocation (including fair division, apportionment, etc.)
68M11 Internet topics

Software:

CloudSim
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Foster, I.; Kesselman, C., The Grid: Blueprint for a New Computing Infrastructure (2004), Morgan Kaufmann
[2] J. McCarthy, Life in the Cloud, Living with Cloud Computing, in, 1961.; J. McCarthy, Life in the Cloud, Living with Cloud Computing, in, 1961.
[3] P. Samimi, A. Patel, Review of pricing models for grid & cloud computing, in: IEEE Symposium on Computers & Informatics (ISCI), 2011, pp. 634-639.; P. Samimi, A. Patel, Review of pricing models for grid & cloud computing, in: IEEE Symposium on Computers & Informatics (ISCI), 2011, pp. 634-639.
[4] Izakian, H.; Abraham, A.; Ladani, B. T., An auction method for resource allocation in computational grids, Future Gener. Comput. Syst., 26, 228-235 (2010)
[5] Buyya, R.; Stockinger, H.; Giddy, J.; Abrams, D., Economic models for management of resources in grid computing, J. Concurr. Computat., 14, 1507-1542 (2002) · Zbl 1007.68612
[6] B. Stiller, D. Hausheer, Design of Economic Grid Traffic Management and Security Mechanisms, Rn, 1, 2008, R1.; B. Stiller, D. Hausheer, Design of Economic Grid Traffic Management and Security Mechanisms, Rn, 1, 2008, R1.
[7] B. Pourebrahimi, K. Bertels, G.M. Kandru, S. Vassiliadis, Market-based resource allocation in grids, in: Second IEEE International Conference on e-Science and Grid Computing e-Science, 2006.; B. Pourebrahimi, K. Bertels, G.M. Kandru, S. Vassiliadis, Market-based resource allocation in grids, in: Second IEEE International Conference on e-Science and Grid Computing e-Science, 2006.
[8] M. Schwind, O. Gujo, T. Stockheim, Dynamic resource prices in a combinatorial grid system, in: 8th IEEE International Conference on and Enterprise Computing, E-Commerce, and E-Services, 2006, 49p.; M. Schwind, O. Gujo, T. Stockheim, Dynamic resource prices in a combinatorial grid system, in: 8th IEEE International Conference on and Enterprise Computing, E-Commerce, and E-Services, 2006, 49p.
[9] Li, L.; Liu, Y.-A.; Liu, K.-M.; Ma, X.-L.; Yang, M., Pricing in combinatorial double auction-based grid allocation model, J. China Univer. Posts Telecommun., 16, 59-65 (2009)
[10] W.-Y. Lin, G.-Y. Lin, H.-Y. Wei, Dynamic auction mechanism for cloud resource allocation, in: 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing (CCGrid), 2010, pp. 591-592.; W.-Y. Lin, G.-Y. Lin, H.-Y. Wei, Dynamic auction mechanism for cloud resource allocation, in: 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing (CCGrid), 2010, pp. 591-592.
[11] T. Yong Meng, M. Mihailescu, A strategy-proof pricing scheme for multiple resource type allocations, in: International Conference on Parallel Processing (ICPP), 2009, pp. 172-179.; T. Yong Meng, M. Mihailescu, A strategy-proof pricing scheme for multiple resource type allocations, in: International Conference on Parallel Processing (ICPP), 2009, pp. 172-179.
[12] Shang, S.; Jiang, J.; Wu, Y.; Huang, Z.; Yang, G.; Zheng, W., DABGPM: a double auction bayesian game-based pricing model in cloud market, Netw. Parall. Comput., 155-164 (2010)
[13] S. Zaman, D. Grosu, Combinatorial auction-based allocation of virtual machine instances in clouds, in: Second IEEE International Conference on Cloud Computing Technology and Science (CloudCom), 2010, pp. 127-134.; S. Zaman, D. Grosu, Combinatorial auction-based allocation of virtual machine instances in clouds, in: Second IEEE International Conference on Cloud Computing Technology and Science (CloudCom), 2010, pp. 127-134.
[14] Jiang, C.; Duan, L.; Liu, C.; Wan, J.; Zhou, L., VRAA: virtualized resource auction and allocation based on incentive and penalty, Cluster Comput., 1-12 (2012)
[15] X. Wang, J. Sun, M. Huang, C. Wu, A resource auction based allocation mechanism in the cloud computing environment, in: 26th IEEE International Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), 2012, pp. 2111-2115.; X. Wang, J. Sun, M. Huang, C. Wu, A resource auction based allocation mechanism in the cloud computing environment, in: 26th IEEE International Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), 2012, pp. 2111-2115.
[16] X.-W. Wang, X.-Y. Wang, M. Huang, A resource allocation method based on the limited English combinatorial auction under cloud computing environment, in: 9th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD), 2012, pp. 905-909.; X.-W. Wang, X.-Y. Wang, M. Huang, A resource allocation method based on the limited English combinatorial auction under cloud computing environment, in: 9th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD), 2012, pp. 905-909.
[17] Li, Y.; Zhang, W.; Zhang, Y.; Zhang, X.; Xiong, X., Calibration of the agent-based continuous double auction stock market by scaling analysis, Inf. Sci. (2012)
[18] Rothkopf, M., Thirteen reasons why the Vickrey-Clarke-Groves process is not practical, Oper. Res., 55, 191-197 (2007) · Zbl 1167.91358
[19] H. Fu-Shiung, H. Chung-Wei, Combinatorial double auctions based on subgradient algorithm, in: IET International Conference on Frontier Computing. Theory, Technologies and Applications, 2010, pp. 247-252.; H. Fu-Shiung, H. Chung-Wei, Combinatorial double auctions based on subgradient algorithm, in: IET International Conference on Frontier Computing. Theory, Technologies and Applications, 2010, pp. 247-252.
[20] Son, S.; Jung, G.; Jun, S., An SLA-based cloud computing that facilitates resource allocation in the distributed data centers of a cloud provider, J. Supercomput., 64, 606-637 (2013)
[21] Hsu, C.-H.; Slagter, K. D.; Chen, S.-C.; Chung, Y.-C., Optimizing energy consumption with task consolidation in clouds, Inf. Sci., 258, 452-462 (2014)
[22] Lehmann, D.; O allaghan, L. I.; Shoham, Y., Truth revelation in approximately efficient combinatorial auctions, J. ACM (JACM), 49, 577-602 (2002) · Zbl 1326.91011
[23] Gustedt, J.; Jeannot, E.; Quinson, M., Experimental validation in large-scale systems: a survey of methodologies, Parall. Process. Lett., 19, 399-418 (2009)
[24] B. Wickremasinghe, R.N. Calheiros, R. Buyya, CloudAnalyst: a CloudSim-based visual modeller for analysing cloud computing environments and applications, in: 24th IEEE International Conference on Advanced Information Networking and Applications (AINA), 2010, pp. 446-452.; B. Wickremasinghe, R.N. Calheiros, R. Buyya, CloudAnalyst: a CloudSim-based visual modeller for analysing cloud computing environments and applications, in: 24th IEEE International Conference on Advanced Information Networking and Applications (AINA), 2010, pp. 446-452.
[25] Calheiros, R. N.; Ranjan, R.; Beloglazov, A.; De Rose, C. A.F.; Buyya, R., CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms, Softw. Pract. Exper., 41, 23-50 (2011)
[26] L. Seung-Hwan, B. Sharma, N. Gunwoo, K. Eun Kyoung, C.R. Das, MDCSim: A multi-tier data center simulation, platform, in: IEEE International Conference on Cluster Computing and Workshops, 2009, pp. 1-9.; L. Seung-Hwan, B. Sharma, N. Gunwoo, K. Eun Kyoung, C.R. Das, MDCSim: A multi-tier data center simulation, platform, in: IEEE International Conference on Cluster Computing and Workshops, 2009, pp. 1-9.
[27] D. Kliazovich, P. Bouvry, Y. Audzevich, S.U. Khan, GreenCloud: a packet-level simulator of energy-aware cloud computing data centers, in: IEEE Global Telecommunications Conference (GLOBECOM 2010), 2010, pp. 1-5.; D. Kliazovich, P. Bouvry, Y. Audzevich, S.U. Khan, GreenCloud: a packet-level simulator of energy-aware cloud computing data centers, in: IEEE Global Telecommunications Conference (GLOBECOM 2010), 2010, pp. 1-5.
[28] S.K. Garg, R. Buyya, NetworkCloudSim: modelling parallel applications in cloud simulations, in: Fourth IEEE International Conference on Utility and Cloud Computing (UCC), 2011, pp. 105-113.; S.K. Garg, R. Buyya, NetworkCloudSim: modelling parallel applications in cloud simulations, in: Fourth IEEE International Conference on Utility and Cloud Computing (UCC), 2011, pp. 105-113.
[29] R. Buyya, R. Ranjan, R.N. Calheiros, Modeling and simulation of scalable cloud computing environments and the CloudSim toolkit: challenges and opportunities, in: International Conference on High Performance Computing & Simulation, HPCS’09, IEEE, 2009, pp. 1-11.; R. Buyya, R. Ranjan, R.N. Calheiros, Modeling and simulation of scalable cloud computing environments and the CloudSim toolkit: challenges and opportunities, in: International Conference on High Performance Computing & Simulation, HPCS’09, IEEE, 2009, pp. 1-11.
[30] Xia, M.; Koehler, G. J.; Whinston, A. B., Pricing combinatorial auctions, Eur. J. Oper. Res., 154, 251-270 (2004) · Zbl 1099.91054
[31] Mas-Colell, A.; Whinston, M. D.; Green, J. R., U.P.F.F.d.C.E.i. Empresarials, Microeconomic Theory (1995), Oxford university press: Oxford university press NY · Zbl 1256.91002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.