Optimal Online Multi-Instance Acquisition in IaaS Clouds
Authors:
- 23 December 2014
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 26 (12) , 3407-3419
Abstract
Infrastructure-as-a-service (IaaS) clouds offer diverse instance purchasing options. A user can either run instances on demand and pay only for what it uses, or it can prepay to reserve instances for a long period, during which a usage discount is entitled. An important problem facing a user is how these two instance options can be dynamically combined to serve time-varying demands at minimum cost. Existing strategies in the literature, however, require either exact knowledge or the distribution of demands in the long-term future, which significantly limits their use in practice. Unlike existing works, we propose two practical online algorithms, one deterministic and another randomized, that dynamically combine the two instance options online without any knowledge of the future. We show that the proposed deterministic (resp., randomized) algorithm incurs no more than 2 - α (resp., e/(e-1 + α)) times the minimum cost obtained by an optimal offline algorithm that knows the exact future a priori, where a is the entitled discount after reservation. Our online algorithms achieve the best possible competitive ratios in both the deterministic and randomized cases, and can be easily extended to cases when short-term predictions are reliable. Simulations driven by a large volume of real-world traces show that significant cost savings can be achieved with prevalent IaaS prices.Keywords
This publication has 18 references indexed in Scilit:
- The constrained Ski-Rental problem and its application to online cloud cost optimization2013
- A framework for truthful online auctions in cloud computing with heterogeneous user demands2013
- GreenHadoop2012
- Rent, Lease, or Buy: Randomized Algorithms for Multislope Ski RentalSIAM Journal on Discrete Mathematics, 2012
- Approximate Dynamic Programming2011
- Autonomic mix-aware provisioning for non-stationary data center workloads2010
- Capacity Management and Demand Prediction for Next Generation Data Centers2007
- Exploiting nonstationarity for performance predictionACM SIGOPS Operating Systems Review, 2007
- Dynamic Provisioning of Multi-tier Internet Applications2005
- Generalized autoregressive conditional heteroskedasticityJournal of Econometrics, 1986