Managing deadline-constrained bag-of-tasks jobs on hybrid clouds

Bo Wang, Ying Song, Yuzhong Sun, Jun Liu

TL;DR

This paper introduces a smart way to manage "Bag-of-Tasks" (BoT) jobs—large groups of independent, CPU-heavy tasks—across hybrid clouds. By modeling the problem as binary nonlinear programming and solving it with a custom heuristic, the researchers achieved up to 76% cost savings and nearly tripled resource utilization compared to standard scheduling methods.

What Problem Does This Paper Address?

Many organizations operate on a hybrid cloud model: they own a local "private" cloud (fixed capacity, already paid for) but can "burst" into a public cloud (like AWS) when demand spikes. The headache for engineers is scheduling Bag-of-Tasks (BoT) jobs—think image rendering, software testing, or massive data analysis—where hundreds of independent tasks must finish by a specific deadline.

The challenge is two-fold:

  1. Cost: Public cloud resources are expensive. You want to use your local hardware as much as possible because it's essentially a "sunk cost."
  2. Deadlines: If you stay entirely local to save money, you might miss your deadlines. If you move everything to the public cloud, you waste money.

Most existing solutions treat all hardware as identical or fail to account for how local physical machines are actually provisioned. This paper tackles the complexity of heterogeneous local hardware and the need to minimize rental costs while strictly respecting time constraints.

Methods

The authors first formalize the problem using Binary Nonlinear Programming (BNP). Because BNP is "NP-hard" (meaning it's computationally impossible to find the perfect solution quickly for large problems), they developed a Heuristic Algorithm (HA) to find a "good enough" solution in polynomial time.

Key features of their algorithm include:

  • Deadline-First Assignment: It prioritizes tasks that are closest to their deadlines.
  • Smart Resource Expansion: If local cores are full, the algorithm doesn't just rent a VM immediately. It first checks if there are idle local physical machines (PMs) with high capacity.
  • Cost-Performance Awareness: When it must rent from the public cloud, it selects VM instances based on the best cost-performance ratio rather than just the cheapest or fastest option.
  • Sequential Packing: Tasks assigned to the same core are run in order of their deadlines to ensure maximum throughput without violations.

Datasets

The researchers evaluated their algorithm using two well-known real-world traces from the Parallel Workloads Archive:

  1. UniLu Gaia log: A 3-month trace from the University of Luxembourg’s Gaia cluster.
  2. NASA Ames iPSC/860 log: A 2-month trace from NASA.

They simulated these tasks against a local environment of 15 physical machines with varying CPU configurations and a public cloud environment modeled after Amazon EC2 (specifically c3.large instances).

Key Insights and Ideas

  • The "Small Task" Trap: A major insight is why traditional "First Fit Decreasing" (FFD) algorithms fail in hybrid clouds. FFD schedules the longest tasks first. This often leaves a "tail" of small tasks at the end. To meet the deadlines for these final tiny tasks, the system is forced to rent expensive public VMs that end up mostly idle, leading to high costs and low utilization.
  • Tight Packing via Deadlines: By focusing on the task closest to its deadline, the proposed HA "packs" tasks more efficiently. This delays the need to rent public resources and ensures that when a VM is rented, it is used to its full capacity.
  • Local Priority: The model treats local resource utilization as a negative cost. This mathematically forces the solver to exhaust every local core before spending a single cent on the public cloud.

Key Results

The Heuristic Algorithm (HA) significantly outperformed the industry-standard First Fit Decreasing (FFD) approach:

  • Rent Cost Savings: HA saved between 16.2% and 76% in public cloud rental costs.
  • Resource Utilization: HA improved local and rented resource utilization by 47.3% to 182.8%.
  • Scalability: The algorithm showed "quadratically increasing" time complexity relative to the number of tasks, meaning it remains practical even as job sizes grow to tens of thousands of tasks.
  • Trade-off: While HA saved money, it resulted in longer "makespans" (the total time to finish everything) compared to FFD. However, since all tasks still finished before their deadlines, this is considered a successful optimization for cost-conscious providers.

Limitations and Future Work

  • Task Independence: The model assumes "Bag-of-Tasks" jobs where tasks don't depend on each other. It may not apply directly to complex workflows where Task B cannot start until Task A finishes.
  • Data Transfer Costs: The paper focuses heavily on CPU-intensive tasks. In data-heavy applications, the cost and time required to move terabytes of data to the public cloud might outweigh the CPU rental savings.
  • Homogeneous Public VMs: While the paper accounts for heterogeneous local hardware, it primarily uses one type of public VM for the simulation. Future work could explore more complex public cloud markets with "Spot Instances" or a wider variety of VM types.

Summary updated

Abstract

Outsourcing jobs to a public cloud is a cost-effective way to address the problem of satisfying the peak resource demand when the local cloud has insufficient resources. In this paper, we study on managing deadline-constrained bag-of-tasks jobs on hybrid clouds. We present a binary nonlinear programming (BNP) problem to model the hybrid cloud management where the utilization of physical machines (PMs) in the local cloud/cluster is maximized when the local resources are enough to satisfy the deadline constraints of jobs, while when not, the rent cost from the public cloud is minimized. To solve the BNP problem in polynomial time, we propose the heuristic algorithm whose main idea is assigning a task to a core of a used PM (in local cloud) or a rented virtual machine (VM) (in public cloud) such that the difference between the finish time of the task and its deadline is minimal in all of assignments. If none of unassigned tasks can be completed within its deadline, the algorithm adds an available PM with most capacity or rents a new VM with highest cost-performance ratio and assigns tasks to the new PM/VM as previous step. Extensive experimental results show that our heuristic algorithm saves 16.2%-76% cost and improves 47.3%-182.8% resource utilizations for finishing jobs within their respective deadlines with comparable overheads, compared with first fit decreasing algorithm.
BibTeX
@inproceedings{wang2016managing,
  author = {Bo Wang and Ying Song and Yuzhong Sun and Jun Liu},
  title = {{Managing deadline-constrained bag-of-tasks jobs on hybrid clouds}},
  booktitle = {SpringSim (HPS)},
  year = {2016},
  url = {https://openreview.net/forum?id=tNLu8wn53jsN},
}

Loading related content...

Figure