More Web Proxy on the site http://driver.im/

research-article

Truthful Greedy Mechanisms for Dynamic Virtual Machine Provisioning and Allocation in Clouds

Authors:

Mahyar Movahed Nejad,

Lena Mashayekhy,

Daniel GrosuAuthors Info & Claims

IEEE Transactions on Parallel and Distributed Systems, Volume 26, Issue 2

Pages 594 - 603

https://doi.org/10.1109/TPDS.2014.2308224

Published: 01 February 2015 Publication History

Abstract

A major challenging problem for cloud providers is designing efficient mechanisms for virtual machine (VM) provisioning and allocation. Such mechanisms enable the cloud providers to effectively utilize their available resources and obtain higher profits. Recently, cloud providers have introduced auction-based models for VM provisioning and allocation which allow users to submit bids for their requested VMs. We formulate the dynamic VM provisioning and allocation problem for the auction-based model as an integer program considering multiple types of resources. We then design truthful greedy and optimal mechanisms for the problem such that the cloud provider provisions VMs based on the requests of the winning users and determines their payments. We show that the proposed mechanisms are truthful, that is, the users do not have incentives to manipulate the system by lying about their requested bundles of VM instances and their valuations. We perform extensive experiments using real workload traces in order to investigate the performance of the proposed mechanisms. Our proposed mechanisms achieve promising results in terms of revenue for the cloud provider.

References

[1]

WindowsAzure, [Online]. Available: http://www.windowsazure.com/en-us/pricing/calculator/, 2014.

[2]

Amazon EC2 Instance Types, [Online]. Available: http://aws.amazon.com/ec2/instance-types/, 2014.

[3]

N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, Algorithmic Game Theory, Cambridge Univ. Press, 2007.

[4]

G. Wei, A. Vasilakos, Y. Zheng, and N. Xiong, “A Game-Theoretic Method of Fair Resource Allocation for Cloud Computing Services,” The J. Supercomputing, vol. 54, no. 2, pp. 252–269, 2010.

Digital Library

[5]

N. Jain, I. Menache, J. Naor, and J. Yaniv, “A Truthful Mechanism for Value-Based Scheduling in Cloud Computing,” Theory of Computing Systems, pp. 1–19, 2013, [Online]. Available: https://doi.org/10.1007/s00224-013-9449-0.

[6]

Z. Kong, C.-Z. Xu, and M. Guo, “Mechanism Design for Stochastic Virtual Resource Allocation in Non-Cooperative Cloud Systems,” in Proc. IEEE Fourth Int'l Conf. Cloud Computing, 2011, pp. 614–621.

[7]

Y. Wang, A. Nakao, and A.V. Vasilakos, “Heterogeneity Playing Key Role: Modeling and Analyzing the Dynamics of Incentive Mechanisms in Autonomous Networks,” ACM Trans. Autonomous and Adaptive Systems, vol. 7, no. 3, 2012, article 31.

[8]

D. Ardagna, B. Panicucci, and M. Passacantando, “Generalized Nash Equilibria for the Service Provisioning Problem in Cloud Systems,” IEEE Trans. Services Computing, vol. 6, no. 4, pp. 429–442, Oct.-Dec. 2013.

Digital Library

[9]

V. Di Valerio, V. Cardellini, and F. Lo Presti, “Optimal Pricing and Service Provisioning Strategies in Cloud Systems: A Stackelberg Game Approach,” in Proc. IEEE Sixth Int'l Conf. Cloud Computing, 2013, pp. 115–122.

[10]

X. Zhou, S. Gandhi, S. Suri, and H. Zheng, “ebay in the Sky: Strategy-Proof Wireless Spectrum Auctions,” in Proc. ACM MobiCom, 2008, pp. 2–13.

[11]

X. Zhou and H. Zheng, “Trust: A General Framework for Truthful Double Spectrum Auctions,” in Proc. IEEE INFOCOM, 2009, pp. 999–1007.

[12]

G.S. Kasbekar and S. Sarkar, “Spectrum Auction Framework for Access Allocation in Cognitive Radio Networks,” IEEE/ACM Trans. Networking, vol. 18, no. 6, pp. 1841–1854, Dec. 2010.

Digital Library

[13]

F. Wu and N. Vaidya, “A Strategy-Proof Radio Spectrum Auction Mechanism in Noncooperative Wireless Networks,” IEEE Trans. Mobile Computing, vol. 12, no. 5, pp. 885–894, May 2013.

Digital Library

[14]

J. Jia, Q. Zhang, Q. Zhang, and M. Liu, “Revenue Generation for Truthful Spectrum Auction in Dynamic Spectrum Access,” in Proc. ACM MobiHoc, 2009, pp. 3–12.

[15]

S. Zaman and D. Grosu, “Combinatorial Auction-Based Dynamic VM Provisioning and Allocation in Clouds,” in Proc. IEEE Third Int'l Conf. Cloud Computing Technology and Science, 2011, pp. 107–114.

[16]

S. Zaman and D. Grosu, “Combinatorial Auction-Based Allocation of Virtual Machine Instances in Clouds,” J. Parallel and Distributed Computing, vol. 73, no. 4, pp. 495–508, 2013.

Digital Library

[17]

H. Kellerer, U. Pferschy, and D. Pisinger, Knapsack Problems, Springer, 2004.

[18]

A. Mu'alem and N. Nisan, “Truthful Approximation Mechanisms for Restricted Combinatorial Auctions,” in Proc. 18th Nat'l Conf. Artificial Intelligence, 2002, pp. 379–384.

[19]

D. Lehmann, L. Oćallaghan, and Y. Shoham, “Truth Revelation in Approximately Efficient Combinatorial Auctions,” J. ACM, vol. 49, no. 5, pp. 577–602, 2002.

Digital Library

[20]

M.M. Nejad, L. Mashayekhy, and D. Grosu, “A Family of Truthful Greedy Mechanisms for Dynamic Virtual Machine Provisioning and Allocation in Clouds,” in Proc. IEEE Sixth Int'l Conf. Cloud Computing, 2013, pp. 188–195.

[21]

IBM ILOG CPLEX V12.1 User's Manual, [Online]. Available: ftp://ftp.software.ibm.com/software/websphere/ilog/docs/, 2014.

[22]

Grid Workloads Archive, [Online]. Available: http://gwa.ewi.tudelft.nl, 2014.

[23]

Parallel Workloads Archive, [Online]. Available: http://www.cs.h-uji.ac.il/labs/parallel/workload/, 2014.

Cited By

Zhang JWang ZVasilakos ALi W(2024)A resource competition-based truthful mechanism for IoV edge computing resource allocation with a lowest revenue limitJournal of Cloud Computing: Advances, Systems and Applications10.1186/s13677-023-00572-x13:1Online publication date: 10-Jan-2024
https://dl.acm.org/doi/10.1186/s13677-023-00572-x
Guo JSu LLiu JDing JLiu XHuang BLi L(2024)Auction-based client selection for online Federated LearningInformation Fusion10.1016/j.inffus.2024.102549112:COnline publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1016/j.inffus.2024.102549
Zhang JSun HLi W(2024)Lowest revenue limit-based truthful auction mechanism for cloud resource allocationThe Journal of Supercomputing10.1007/s11227-023-05839-380:8(10637-10666)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1007/s11227-023-05839-3
Show More Cited By

Index Terms

Truthful Greedy Mechanisms for Dynamic Virtual Machine Provisioning and Allocation in Clouds

Index terms have been assigned to the content through auto-classification.

Recommendations

A Family of Truthful Greedy Mechanisms for Dynamic Virtual Machine Provisioning and Allocation in Clouds
CLOUD '13: Proceedings of the 2013 IEEE Sixth International Conference on Cloud Computing

Designing efficient mechanisms for Virtual Machine (VM) provisioning and allocation is a major challenging problem that needs to be solved by cloud providers. We formulate the VM provisioning and allocation problem in clouds as an integer program and ...
Combinatorial auction-based virtual machine provisioning and allocation in clouds
Combinatorial Auction-Based Mechanisms for VM Provisioning and Allocation in Clouds
CCGRID '12: Proceedings of the 2012 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (ccgrid 2012)

Current cloud providers use fixed-price based mechanisms to allocate Virtual Machine (VM) instances to their users. The fixed-price based mechanisms do not provide an efficient allocation of resources and do not maximize the revenue of the cloud ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Parallel and Distributed Systems

IEEE Transactions on Parallel and Distributed Systems Volume 26, Issue 2

Feb. 2015

292 pages

ISSN:1045-9219

Issue’s Table of Contents

Copyright © 2014.

Publisher

IEEE Press

Publication History

Published: 01 February 2015

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhang JWang ZVasilakos ALi W(2024)A resource competition-based truthful mechanism for IoV edge computing resource allocation with a lowest revenue limitJournal of Cloud Computing: Advances, Systems and Applications10.1186/s13677-023-00572-x13:1Online publication date: 10-Jan-2024
https://dl.acm.org/doi/10.1186/s13677-023-00572-x
Guo JSu LLiu JDing JLiu XHuang BLi L(2024)Auction-based client selection for online Federated LearningInformation Fusion10.1016/j.inffus.2024.102549112:COnline publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1016/j.inffus.2024.102549
Zhang JSun HLi W(2024)Lowest revenue limit-based truthful auction mechanism for cloud resource allocationThe Journal of Supercomputing10.1007/s11227-023-05839-380:8(10637-10666)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1007/s11227-023-05839-3
Zhang JSun HWang ZSu QLi W(2024)A Novel Clinching Auction Mechanism for Edge Computing Resource Allocation With Budget LimitsTransactions on Emerging Telecommunications Technologies10.1002/ett.7000535:11Online publication date: 25-Oct-2024
https://dl.acm.org/doi/10.1002/ett.70005
Zuo H(2023)Towards optimal virtual machine placement methods in cloud environmentsJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.3233/JIFS-22289644:5(8663-8696)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.3233/JIFS-222896
Li QJia XHuang C(2023)A truthful dynamic combinatorial double auction model for cloud resource allocationJournal of Cloud Computing: Advances, Systems and Applications10.1186/s13677-023-00479-712:1Online publication date: 18-Jul-2023
https://dl.acm.org/doi/10.1186/s13677-023-00479-7
Gao GHuang SHuang HXiao MWu JSun YZhang S(2023)Combination of Auction Theory and Multi-Armed Bandits: Model, Algorithm, and ApplicationIEEE Transactions on Mobile Computing10.1109/TMC.2022.319745922:11(6343-6357)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1109/TMC.2022.3197459
Mishra PMoustafa A(2023)Reinforcement learning based monotonic policy for online resource allocationFuture Generation Computer Systems10.1016/j.future.2021.09.023138:C(313-327)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1016/j.future.2021.09.023
Zhang JLou WSun HSu QLi W(2022)Truthful auction mechanisms for resource allocation in the Internet of Vehicles with public blockchain networksFuture Generation Computer Systems10.1016/j.future.2022.02.002132:C(11-24)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1016/j.future.2022.02.002
Baranwal GVidyarthi D(2022)TRAPPY: a truthfulness and reliability aware application placement policy in fog computingThe Journal of Supercomputing10.1007/s11227-021-04187-478:6(7861-7887)Online publication date: 1-Apr-2022
https://dl.acm.org/doi/10.1007/s11227-021-04187-4
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents