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:
- Cost: Public cloud resources are expensive. You want to use your local hardware as much as possible because it's essentially a "sunk cost."
- 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:
- UniLu Gaia log: A 3-month trace from the University of Luxembourg’s Gaia cluster.
- 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