2013/05/23 by Wei Wang, Wang, Wei, Baochun Li +3
Computer Science · Decision Sciences · #Auction Theory and Applications #Cloud Computing and Resource Management #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #IoT and Edge/Fog Computing #Mobile Crowdsensing and Crowdsourcing #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC) #cs.DC
paper · pdf · doi:10.48550/arxiv.1305.5608
Part of this paper has appeared in USENIX ICAC 2013
openalex publication_date 2013/05/23 · arxiv created 2013/05/24 · arxiv updated 2013/05/27 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
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-alpha (resp., e/(e-1+alpha)) times the minimum cost obtained by an optimal offline algorithm that knows the exact future a priori, where alpha 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.