  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.
