Towards Designing Cost-Optimal Policies to Utilize IaaS Clouds with Online Learning

Xiaohu Wu, Patrick Loiseau, Esa Hyytiä

TL;DR

This paper tackles the challenge of minimizing cloud computing costs for businesses by intelligently allocating resources across self-owned, on-demand, and spot instances. They introduce novel policies that leverage online learning to adapt to dynamic cloud pricing and job arrival patterns, achieving significant cost reductions.

What Problem Does This Paper Address?

Businesses increasingly rely on cloud infrastructure (IaaS) to scale their computing power, but managing costs is a major concern. Cloud providers like AWS offer different pricing models: on-demand instances (predictable, higher cost) and spot instances (cheaper, but can be reclaimed). Many organizations also have their own "self-owned" infrastructure. The core problem is how to optimally decide which type of instance to use for incoming jobs to minimize overall expenditure while still meeting strict deadlines. This involves a complex trade-off: spot instances offer savings but introduce uncertainty, while on-demand instances are reliable but expensive. Self-owned instances are cheapest but often insufficient. Existing approaches often lack a holistic strategy for balancing these options, especially in the face of unpredictable job arrivals and fluctuating spot prices.

Methods

The authors propose a framework for designing cost-optimal instance allocation policies. Their approach involves:

  • Parametric Policies: They define policies with a small number of tunable parameters that govern the allocation of self-owned, on-demand, and spot instances.
  • Self-Owned Instance Allocation: A key contribution is a smarter policy for allocating self-owned instances. Instead of a naive approach, it prioritizes jobs that are less capable of completing using only spot instances, aiming for high utilization of self-owned resources and maximizing opportunities for spot instance usage.
  • Spot and On-Demand Instance Allocation: They develop an optimal policy for acquiring on-demand and bidding for spot instances, formulated as an integer programming problem to maximize spot instance utilization.
  • Online Learning: To adapt to the dynamic nature of cloud environments (unknown job characteristics and spot prices), they employ an online learning technique (specifically, a variant of the weighted majority algorithm) to infer the optimal values of their policy parameters. This allows the system to learn and improve its cost-efficiency over time without requiring prior statistical knowledge of workloads or prices.

Datasets

Not discussed in the paper. The authors rely on simulated data generated according to specific distributions for job arrivals, sizes, deadlines, and spot prices.

Key Insights and Ideas

  • The "Rich" vs. "Poor" Job Distinction: Not all jobs are created equal when it comes to utilizing spot instances. Some jobs are "rich" (can easily complete with spot instances), while others are "poor" (require more reliable resources). A cost-optimal strategy must differentiate between them.
  • Self-Owned Instances as a Strategic Buffer: Allocating self-owned instances strategically, rather than just filling them up, is crucial. By prioritizing "poor" jobs for self-owned resources, the system frees up "rich" jobs to leverage cheaper spot instances, leading to overall cost savings.
  • Online Learning is Key for Adaptability: The dynamic nature of cloud pricing and job arrivals makes static policies ineffective. Online learning allows the system to continuously adapt its allocation strategy, leading to better performance over time.
  • Balancing Utilization and Cost: The paper highlights that simply maximizing the utilization of any instance type isn't always cost-optimal. The goal is to maximize the effective utilization that leads to cost reduction, particularly by favoring cheaper options like spot instances when possible.

Key Results

The proposed policies demonstrated significant cost reductions in simulations:

  • Spot and On-Demand Instances: Up to a 64.51% cost reduction compared to previously proposed policies.
  • Self-Owned Instances: Up to a 43.74% cost reduction compared to naive allocation policies.
  • Combined Approach with Online Learning: Achieved a cost reduction of up to 66.71% when all three instance types and online learning were considered.

Limitations and Future Work

  • Assumptions: The paper makes certain assumptions, such as the independence of spot price changes from individual user bids and the hourly billing cycle for on-demand instances.
  • Job Types: The current framework primarily focuses on "embarrassingly parallel" or "map-only" jobs.
  • Future Work: The authors suggest extending the framework to handle more complex job dependencies, such as precedence-constrained jobs. They also mention the potential application of their approach to other cloud platforms like Microsoft Azure, noting differences in their pricing models.

Summary updated

Abstract

Many businesses possess a small infrastructure that they can use for their computing tasks, but also often buy extra computing resources from clouds. Cloud vendors such as Amazon EC2 offer two types of purchase options: on-demand and spot instances. As tenants have limited budgets to satisfy their computing needs, it is crucial for them to determine how to purchase different options and utilize them (in addition to possible self-owned instances) in a cost-effective manner while respecting their response-time targets. In this paper, we propose a framework to design policies to allocate self-owned, on-demand and spot instances to arriving jobs. In particular, we propose a near-optimal policy to determine the number of self-owned instance and an optimal policy to determine the number of on-demand instances to buy and the number of spot instances to bid for at each time unit. Our policies rely on a small number of parameters and we use an online learning technique to infer their optimal values. Through numerical simulations, we show the effectiveness of our proposed policies, in particular that they achieve a cost reduction of up to 62.85% when spot and on-demand instances are considered and of up to 44.00% when self-owned instances are considered, compared to previously proposed or intuitive policies.
BibTeX
@inproceedings{wu2017towards,
  author = {Xiaohu Wu and Patrick Loiseau and Esa Hyytiä},
  title = {{Towards Designing Cost-Optimal Policies to Utilize IaaS Clouds with Online Learning}},
  booktitle = {ICCAC},
  year = {2017},
  url = {https://openreview.net/forum?id=70yxADREgWU},
}
Figure