Abstract
Dynamic forms of resource pricing have recently been introduced by cloud providers that offer Infrastructure as a Service (IaaS) capabilities in order to maximize profits and balance resource supply and demand. The design of a mechanism that efficiently prices perishable cloud resources in line with a provider’s profit maximization goal remains an open research challenge, however. In this article, we propose the Online Extended Consensus Revenue Estimate mechanism in the setting of a recurrent, multiunit and single price auction for IaaS cloud resources. The mechanism is envy-free, has a high probability of being truthful, and generates a near optimal profit for the provider. We combine the proposed auction design with a scheme for dynamically calculating reserve prices based on data center Power Usage Effectiveness (PUE) and electricity costs. Our simulation-based evaluation of the mechanism demonstrates its effectiveness under a broad variety of market conditions. In particular, we show how it improves on the classical uniform price auction, and we investigate the value of prior knowledge on the execution time of virtual machines for maximizing profit. We also developed a system prototype and conducted a small-scale experimental study with a group of 10 users that confirms the truthfulness property of the mechanism in a real test environment.
- Michael Armbrust, Armando Fox, Rean Griffith, Anthony D. Joseph, Randy H. Katz, Andrew Konwinski, Gunho Lee, David A. Patterson, Ariel Rabkin, Ion Stoica, and Matei Zaharia. 2010. A view of cloud computing. Communications of the ACM 53, 4 (2010), 50--58. Google ScholarDigital Library
- Lawrence M. Ausubel and Paul Milgrom. 2006. The lovely but lonely Vickrey auction. Combinatorial Auctions 17 (2006), 22--26.Google Scholar
- Orna Agmon Ben-Yehuda, Muli Ben-Yehuda, Assaf Schuster, and Dan Tsafrir. 2013. Deconstructing Amazon EC2 spot instance pricing. ACM Transactions on Economy Computing 1, 3, Article 16 (Sept. 2013), 20 pages. Google ScholarDigital Library
- Rodrigo N. Calheiros, Rajiv Ranjan, Anton Beloglazov, César A. F. De Rose, and Rajkumar Buyya. 2011. CloudSim: A toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms. Software: Practice and Experience 41, 1 (Jan. 2011), 23--50. DOI:http://dx.doi.org/10.1002/spe.995 Google ScholarDigital Library
- Gaylon S. Campbell and John M. Norman. 2012. An Introduction to Environmental Biophysics. Springer Science & Business Media.Google Scholar
- Navraj Chohan, Claris Castillo, Mike Spreitzer, Malgorzata Steinder, Asser Tantawi, and Chandra Krintz. 2010. See spot run: Using spot instances for mapreduce workflows. In Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing. USENIX Association. Google ScholarDigital Library
- Amir Danak and Shie Mannor. 2010. Resource allocation with supply adjustment in distributed computing systems. In Proceedings of the 30th International Conference on Distributed Computing Systems (ICDCS’10). 498--506. DOI:http://dx.doi.org/10.1109/ICDCS.2010.60 Google ScholarDigital Library
- Ínigo Goiri, Kien Le, Jordi Guitart, Jordi Torres, and Ricardo Bianchini. 2011. Intelligent placement of datacenters for internet services. In Proceedings of the 31st IEEE International Conference on Distributed Computing Systems (ICDCS’11). 131--142. DOI:http://dx.doi.org/10.1109/ICDCS.2011.19 Google ScholarDigital Library
- Andrew V. Goldberg and Jason D. Hartline. 2003a. Competitiveness via consensus. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’03). 215--222. Google ScholarDigital Library
- Andrew V. Goldberg and Jason D. Hartline. 2003b. Envy-free auctions for digital goods. In Proceedings of the 4th ACM Conference on Electronic Commerce (EC’03). 29--35. DOI:http://dx.doi.org/10.1145/779928.779932 Google ScholarDigital Library
- Andrew V. Goldberg and Jason D. Hartline. 2005. Collusion-resistant mechanisms for single-parameter agents. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’05). Society for Industrial and Applied Mathematics, Vancouver, British Columbia, 620--629. Google ScholarDigital Library
- Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Michael Saks, and Andrew Wright. 2006. Competitive auctions. Games and Economic Behavior 55, 2 (2006), 242--269. DOI:http://dx.doi.org/10.1016/j.geb.2006.02.003Google ScholarCross Ref
- Jerry R. Green and Jean-Jacques Laffont. 1986. Partially verifiable information and mechanism design. Review of Economic Studies 53, 3 (1986), 447--456. http://restud.oxfordjournals.org/content/53/3/447.abstract.Google ScholarCross Ref
- Albert Greenberg, James Hamilton, David A. Maltz, and Parveen Patel. 2008. The cost of a cloud: Research problems in data center networks. SIGCOMM Computing Communication Review 39, 1 (2008), 68--73. DOI:http://dx.doi.org/10.1145/1496091.1496103 Google ScholarDigital Library
- Steve Greenberg, Evan Mills, Bill Tschudi, Peter Rumsey, and Bruce Myat. 2006. Best practices for data centers: Lessons learned from benchmarking 22 data centers. ACEEE Summer Study on Energy Efficiency in Buildings in Asilomar, CA 3 (2006), 76--87.Google Scholar
- Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe, Claire Kenyon, and Frank McSherry. 2005. On profit-maximizing envy-free pricing. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms. 1164--1173. Google ScholarDigital Library
- Leonid Hurwicz. 1975. On the existence of allocation systems whose manipulative Nash equilibria are pareto-optimal. Presented at the 3rd World Congress of the Econometric Society. Toronto, Canada.Google Scholar
- Bahman Javadi, Ruppa K. Thulasiram, and Rajkumar Buyya. 2011. Statistical modeling of spot instance prices in public cloud environments. In Proceedings of the 4th IEEE International Conference on Utility and Cloud Computing (UCC’11). 219--228. Google ScholarDigital Library
- Kien Le, Richardo Bianchini, Jingru Zhang, Yogesh Jaluria, Jiandong Meng, and Thu D. Nguyen. 2011. Reducing electricity cost through virtual machine placement in high performance computing clouds. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC’11). Article 22, 22:1--22:12 pages. DOI:http://dx.doi.org/10.1145/2063384.2063413 Google ScholarDigital Library
- Juong-Sik Lee and B. K. Szymanski. 2005. A novel auction mechanism for selling time-sensitive e-services. In Proceedings of 7th IEEE International Conference on E-Commerce Technology, (CEC’05). Hong Kong, 75--82. DOI:http://dx.doi.org/10.1109/ICECT.2005.7 Google ScholarDigital Library
- Mario Macías and Jordi Guitart. 2011. A genetic model for pricing in cloud computing markets. In Proceedings of the 2011 ACM Symposium on Applied Computing. 113--118. DOI:http://dx.doi.org/10.1145/1982185.1982216 Google ScholarDigital Library
- Mario Macías and Jordi Guitart. 2014. SLA negotiation and enforcement policies for revenue maximization and client classification in cloud providers. Future Generation Computer Systems 41 (2014), 19--31. Google ScholarDigital Library
- M. Mihailescu and Yong-Meng Teo. 2012. The impact of user rationality in federated clouds. In Proceedings of the 12th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid’12). Ottawa, Canada, 620--627. DOI:http://dx.doi.org/10.1109/CCGrid.2012.127 Google ScholarDigital Library
- Kevin Mills, James Filliben, and Chris Dabrowski. 2011. Comparing VM-placement algorithms for on-demand clouds. In Proceedings of 3rd International Conference on Cloud Computing Technology and Science (CloudCom’12). 91--98. DOI:http://dx.doi.org/10.1109/CloudCom.2011.22 Google ScholarDigital Library
- Hervé Moulin and Scott Shenker. 2001. Strategyproof sharing of submodular costs: Budget balance versus efficiency. Economic Theory 18, 3 (2001), 511--533. DOI:http://dx.doi.org/10.1007/PL00004200Google ScholarCross Ref
- Roger B. Myerson. 1981. Optimal auction design. Mathematics of Operations Research 6, 1 (1981), 58--73. DOI:http://dx.doi.org/10.1287/moor.6.1.58 Google ScholarDigital Library
- Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani. 2007. Algorithmic Game Theory. Cambridge University Press. Google ScholarDigital Library
- Michael K. Patterson. 2008. The effect of data center temperature on energy efficiency. In Proceedings of 11th Intersociety Conference on Thermal and Thermomechanical Phenomena in Electronic Systems (ITHERM’08). Orlando, FL, 1167--1174. DOI:http://dx.doi.org/10.1109/ITHERM.2008.4544393Google ScholarCross Ref
- Steven Pelley, David Meisner, Thomas F. Wenisch, and James W. VanGilder. 2009. Understanding and abstracting total data center power. In Proceedings of the Workshop on Energy-Efficient Design (WEED’09) held in Conjunction with the 36th International Symposium on Computer Architecture (ISCA'09). Austin, Texas, USA.Google Scholar
- Neil Rasmussen. 2011. Electrical efficiency measurement for data centers. White Paper by Schneider Electric - Data Center Science Center 154 revision 2 (2011).Google Scholar
- Yang Song, Murtaza Zafer, and Kang-Won Lee. 2012. Optimal bidding in spot instance market. In Proceedings of the 31st International Conference on Computer Communications (INFOCOM’12). Orlando, Florida, USA, 190--198. DOI:http://dx.doi.org/10.1109/INFCOM.2012.6195567Google ScholarCross Ref
- Murray Stokely, Jim Winget, Ed Keyes, Carrie Grimes, and Benjamin Yolken. 2009. Using a market economy to provision compute resources across planet-wide clusters. In Proceedings of IEEE International Symposium on Parallel Distributed Processing (IPDPS’09). 1--8. DOI:http://dx.doi.org/10.1109/IPDPS.2009.5160966 Google ScholarDigital Library
- Adel Nadjaran Toosi, Farzad Khodadadi, and Rajkumar Buyya. 2015. SipaaS: Spot instance pricing as a Service framework and its implementation in OpenStack. Concurrency Computation: Practice and Experiences. DOI:http://dx.doi.org/10.1002/cpe.3749Google Scholar
- Adel Nadjaran Toosi, Rodrigo N. Calheiros, Ruppa K. Thulasiram, and Rajkumar Buyya. 2011. Resource provisioning policies to increase IaaS provider’s profit in a federated cloud environment. In Proceedings of the 13th IEEE International Conference on High Performance Computing and Communications (HPCC’11). Banff, Canada, 279--287. DOI:http://dx.doi.org/10.1109/HPCC.2011.44 Google ScholarDigital Library
- William Vickrey. 1961. Counterspeculation, auctions, and competitive sealed tenders. Journal of Finance 16, 1 (1961), 8--37.Google ScholarCross Ref
- William Voorsluys and Rajkumar Buyya. 2012. Reliable provisioning of spot instances for compute-intensive applications. In Proceedings of 26th International Conference on Advanced Information Networking and Applications (AINA’12). Fukuoka, Japan, 542--549. DOI:http://dx.doi.org/10.1109/AINA.2012.106 Google ScholarDigital Library
- Wei Wang, Baochun Li, and Ben Liang. 2012. Towards optimal capacity segmentation with hybrid cloud pricing. In Proceedings of the 32nd IEEE International Conference on Distributed Computing Systems (ICDCS’12). 425--434. DOI:http://dx.doi.org/10.1109/ICDCS.2012.52 Google ScholarDigital Library
- Wei Wang, Ben Liang, and Baochun Li. 2013. Revenue maximization with dynamic auctions in IaaS cloud markets. In Proceedings of the 21st IEEE/ACM International Symposium on Quality of Service (IWQoS). 1--6. DOI:http://dx.doi.org/10.1109/IWQoS.2013.6550265Google ScholarCross Ref
- Hong Xu and Baochun Li. 2013. Dynamic cloud pricing for revenue maximization. IEEE Transactions on Cloud Computing 1, 2 (July 2013), 158--171. Google ScholarDigital Library
- Sangho Yi, Derrick Kondo, and Artur Andrzejak. 2010. Reducing costs of spot instances via checkpointing in the amazon elastic compute cloud. In Proceedings of the 2010 IEEE 3rd International Conference on Cloud Computing (Cloud’10). 236--243. DOI:http://dx.doi.org/10.1109/Cloud.2010.35http://dx.doi.org/10.1109/Cloud.2010.35 Google ScholarDigital Library
- Sharrukh Zaman and Daniel Grosu. 2012. An online mechanism for dynamic VM provisioning and allocation in clouds. In 5th IEEE International Conference on Cloud Computing (CLOUD’12). 253--260. Google ScholarDigital Library
- Sharrukh Zaman and Daniel Grosu. 2013. Combinatorial auction-based allocation of virtual machine instances in clouds. Journal of Parallel and Distributed Computing 73, 4 (2013), 495--508. DOI:http://dx.doi.org/10.1016/j.jpdc.2012.12.006 Google ScholarDigital Library
- Linquan Zhang, Zongpeng Li, and Chuan Wu. 2014. Dynamic resource provisioning in cloud computing: A randomized auction approach. In Proceedings of IEEE INFOCOM. Toronto, Canada, 433--441. DOI:http://dx.doi.org/10.1109/INFOCOM.2014.6847966Google ScholarCross Ref
- Qi Zhang, Quanyan Zhu, and R. Boutaba. 2011. Dynamic resource allocation for spot markets in cloud computing environments. In Proceedings of the 4th IEEE International Conference on Utility and Cloud Computing (UCC’11). Melbourne, Australia, 178--185. DOI:http://dx.doi.org/10.1109/UCC.2011.33 Google ScholarDigital Library
Index Terms
- An Auction Mechanism for Cloud Spot Markets
Recommendations
Mixed-bundling auctions with reserve prices
AAMAS '12: Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 2Revenue maximization in multi-item settings is notoriously elusive. This paper studies a class of two-item auctions which we call a mixed-bundling auction with reserve prices (MBARP). It calls VCG on an enlarged set of agents by adding the seller---who ...
Robust combinatorial auction protocol against false-name bids.
This paper presents a new combinatorial auction protocol that is robust against false-name bids. Internet auctions have become an integral part of Electronic Commerce (EC) and a promising field for applying agent and Artificial Intelligence ...
Implications of a Reserve Price in an Agent-Based Common-Value Auction
Auction sellers can use a reserve price to require a minimum bid before items are sold. Theoretical and experimental research has tested the influence of a reserve price in an independent private values auction, but little focus has been given to the ...
Comments