Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Heterogeneous Cloud Resources Management: Truthful Mechanism Design in Shared Multi-minded Users

  • Conference paper
  • First Online:

Part of the book series:Lecture Notes in Computer Science ((LNISA,volume 11063))

Included in the following conference series:

  • 1697Accesses

Abstract

We address the problem of dynamic virtual machine provisioning and allocation of heterogeneous cloud resources. Existing works consider each user requests single bundle (single-minded), but a user may request multiple bundles (multi-minded). Thus, our object is to provide and allocate efficiently multiple VMs considering multi-minded setting to maximize social welfare. We formulate this problem in an auction-based setting and design optimal and approximation mechanisms. In addition, we show the approximation is\(\frac{a_{max}}{a_{min}}\sqrt{R\frac{c_{max}}{c_{min}}}+2\), where\(c_{max}\)/\(c_{min}\) is the maximum/minimum available resources, and\(a_{max}\)/\(a_{min}\) is the maximum/minimum requested resources. Furthermore, we show our proposed mechanisms are truthful, that is, they drive the system into an equilibrium where any user does not have incentives to maximize her own profit by untruthful value. Experimental results demonstrate that our proposed approximation mechanism gets the near-optimal allocation within a reasonable time whiling to giving the users incentives to report their true declarations.

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Similar content being viewed by others

References

  1. Amazon EC2 Instances.http://aws.amazon.com/cn/ec2

  2. Nisan, N., Ronen, A.: Algorithmic mechanism design. Games Econ. Behav.35, 166–196 (2001)

    Article MathSciNet  Google Scholar 

  3. Mu’Alem, A., Nisanb, N.: Truthful approximation mechanisms for restricted combinatorial auctions. Games Econ. Behav.64(2), 612–631 (2008)

    Article MathSciNet  Google Scholar 

  4. Dobzinski, S., Nisan, N.: Mechanisms for multi-unit auctions. J. Artif. Intell. Res.37, 85–95 (2010)

    Article MathSciNet  Google Scholar 

  5. Babaioff, M., Lavi, R., Pavlov, E.: Mechanism design for single-value domains. In: Proceedings of the 20th National Conference on Artificial Intelligence, vol. 1, pp. 241–247 (2005)

    Google Scholar 

  6. Vickrey, W.: Counterspeculation, auctions, and competitive sealed tenders. J. Finance16(1), 8–37 (1961)

    Article MathSciNet  Google Scholar 

  7. Clarke, E.H.: Multipart pricing of public goods. Public Choice11(1), 17–33 (1971)

    Article  Google Scholar 

  8. Groves, T.: Incentives in teams. Econometrica41(4), 617–631 (1973)

    Article MathSciNet  Google Scholar 

  9. Sandholm, T.: Algorithm for optimal winner determination in combinatorial auctions. Artif. Intell.135(1–2), 1–54 (2002)

    Article MathSciNet  Google Scholar 

  10. Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Heidelberg (2004).https://doi.org/10.1007/978-3-540-24777-7

    Book MATH  Google Scholar 

  11. Hajiesmaili, M.H., Deng, L., Chen, M., Li, Z.: Incentivizing device-to-device load balancing for cellular networks: an online auction design. IEEE J. Selected Areas Commun.35(2), 265–279 (2017)

    Article  Google Scholar 

  12. Zhu, Y., Fu, S., Liu, J., Cui, Y.: Truthful online auction for cloud instance subletting. In: Proceedings of the IEEE 37th International Conference on Distributed Computing Systems (2017)

    Google Scholar 

  13. Lehmann, D., Ita O’Callaghan, L., Shoham, Y.: Truth revelation in approximately efficient combinatorial auctions. J. ACM49(5), 577–602 (2002)

    Article MathSciNet  Google Scholar 

  14. Zaman, S., Grosu, D.: A combinatorial auction-based mechanism for dynamic VM provisioning and allocation in clouds. IEEE Trans. Cloud Comput.1(2), 129–141 (2013)

    Article  Google Scholar 

  15. Bonacquisto, P., Di, G., Modica, G.P., Tomarchio, O.: A procurement auction market to trade residual cloud computing capacity. IEEE Trans. Cloud Comput.3(3), 345–357 (2015)

    Article  Google Scholar 

  16. Zhou, R., Li, Z., Wu, C., Huang, Z.: An efficient cloud market mechanism for computing jobs with soft deadlines. IEEE/ACM Trans. Network.25(2), 793–805 (2016)

    Article  Google Scholar 

  17. Fu, H., Li, Z., Wu, C., Chu, X.: Core-selecting auctions for dynamically allocating heterogeneous VMs in cloud computing. In: Proceedings of the 2014 IEEE International Conference on Cloud Computing, pp. 152–159 (2014)

    Google Scholar 

  18. Zhang, H., Li, B., Jiang, H., Liu, F., Vasilakos, A.V., Liu, J.: A framework for truthful online auctions in cloud computing with heterogeneous user demands. IEEE Trans. Cloud Comput.65(3), 805–818 (2016)

    Article MathSciNet  Google Scholar 

  19. Shi, W., Zhang, L., Wu, C., Li, Z., Lau, F.C.M.: An online auction framework for dynamic resource provisioning in cloud computing. IEEE/ACM Trans. Network.24(4), 2060–2073 (2016)

    Article  Google Scholar 

  20. Mashayekhy, L., Nejad, M.M., Grosu, D.: A PTAS mechanism for provisioning and allocation of heterogeneous cloud resources. IEEE Trans. Parallel Distrib. Syst.26, 2386–2399 (2015)

    Article  Google Scholar 

  21. Nejad, M.M., Mashayekhy, L., Grosu, D.: Truthful greedy mechanisms for dynamic virtual machine provisioning and allocation in clouds. IEEE Trans. Parallel Distrib. Syst.26(2), 594–603 (2015)

    Article  Google Scholar 

  22. Krysta, P.: Greedy approximation via duality for packing, combinatorial auctions and routing. In: Jȩdrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol. 3618, pp. 615–627. Springer, Heidelberg (2005).https://doi.org/10.1007/11549345_53

    Chapter  Google Scholar 

  23. Ibm, ILOG CPLEX Optimizer.http://www-01.ibm.com/software/commerce/optimization/cplex-optimizer/

  24. Titan.http://www.olcf.ornl.gov/titan/

  25. Top 500 Supercomputers.http://www.top500.org

Download references

Acknowledgement

The work was supported in part by the National Natural Science Foundation of China [Nos. 61662088,11301466,11361048], the Natural Science Foundation of Yunnan Province of China [No. 2014FB114], and Program for Excellent Young Talents, Yunnan University.

Author information

Authors and Affiliations

  1. School of Information Science and Engineering, Yunnan University, Kunming, People’s Republic of China

    Xi Liu, Jing Zhang, Xiaolu Zhang & Xuejie Zhang

Authors
  1. Xi Liu

    You can also search for this author inPubMed Google Scholar

  2. Jing Zhang

    You can also search for this author inPubMed Google Scholar

  3. Xiaolu Zhang

    You can also search for this author inPubMed Google Scholar

  4. Xuejie Zhang

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toXuejie Zhang.

Editor information

Editors and Affiliations

  1. Nanjing University of Information Science and Technology, Nanjing, China

    Xingming Sun

  2. Nanjing University of Information Science and Technology, Nanjing, China

    Zhaoqing Pan

  3. Department of Computer Science, Purdue University, West Lafayette, IN, USA

    Elisa Bertino

Rights and permissions

Copyright information

© 2018 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Liu, X., Zhang, J., Zhang, X., Zhang, X. (2018). Heterogeneous Cloud Resources Management: Truthful Mechanism Design in Shared Multi-minded Users. In: Sun, X., Pan, Z., Bertino, E. (eds) Cloud Computing and Security. ICCCS 2018. Lecture Notes in Computer Science(), vol 11063. Springer, Cham. https://doi.org/10.1007/978-3-030-00006-6_49

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

[8]ページ先頭
©2009-2025 Movatter.jp