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 instances 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 64.51 percent when spot and on-demand instances are considered and of up to 43.74 percent when self-owned instances are considered, compared to previously proposed or intuitive policies.
Introduction
Managing compute resources for "embarrassingly parallel" workloads—tasks like 3D rendering or large-scale data processing—presents a complex optimization challenge. Organizations typically balance three resource tiers: local self-owned servers, cheap but volatile cloud spot instances, and expensive but guaranteed on-demand instances. The primary goal is to minimize total expenditure while ensuring every job meets its strict completion deadline.
Problem Formulation
The core difficulty lies in the differing cost and reliability profiles of available resources. Self-owned instances are essentially free but finite. On-demand instances provide reliability at a high unit price $p$. Spot instances offer significant discounts but can be terminated abruptly if the market spot price exceeds the user's bid price $b$.
A common pitfall in resource allocation is the "first-come, first-served" approach. By assigning free local servers to the first available jobs, organizations often waste reliable resources on flexible tasks that could have safely utilized spot instances. This leaves later, more urgent jobs with no choice but to use expensive on-demand instances.
Proposed Methodology
This research introduces a parameterized policy framework that optimizes allocation across all three tiers using online learning.
1. Strategic Self-Owned Allocation
Rather than simple priority, the policy evaluates a job's "capability to utilize spot instances" based on its deadline and size. It strategically denies free local servers to jobs with loose deadlines, forcing them toward the spot market and reserving reliable local capacity for jobs with tight deadlines.
2. Two-Phase Cloud Purchasing
Cloud resource acquisition is split into two distinct phases:
- Flexibility Phase: The scheduler aggressively utilizes spot instances as long as the job maintains sufficient "slack" (a time buffer allowing for potential interruptions).
- Guaranteed Phase: Once a job's slack is exhausted due to spot terminations, the system immediately transitions to on-demand instances to ensure the deadline is met.
3. Online Learning for Parameter Tuning
Because spot prices are unpredictable, the framework avoids complex stochastic forecasting. Instead, it employs a Weighted Majority online learning algorithm (TOLA). The system runs multiple policies with different parameters in parallel, tracks their performance against real-time market data, and dynamically shifts its actual routing to the most cost-effective policy.
Key Insights and Results
The study demonstrates that treating all jobs equally is economically inefficient. By forcing flexible jobs to ride the volatile spot market for as long as mathematically possible, organizations can drastically reduce on-demand spending.
Numerical simulations using standard statistical distributions for job arrivals and sizes revealed significant improvements over baseline policies:
- Cloud-only optimization: Achieved cost reductions of up to 64.51%.
- Hybrid (Self-owned + Cloud) optimization: Reduced costs by up to 43.74% compared to intuitive allocation.
- Overall Performance: The integrated online learning system achieved total cost reductions of up to 66.71%.
Conclusion
This framework proves that near-optimal cost efficiency in the cloud does not require perfect price prediction. By combining strategic resource reservation with late-stage on-demand purchasing and adaptive online learning, organizations can significantly lower their infrastructure costs. Future work will focus on extending these policies to more complex workloads with precedence constraints, such as MapReduce DAGs.
Summary updated