TL;DR
This paper introduces a new algorithmic framework for scheduling "multi-stage" data center jobs where data transfers (coflows) depend on one another in complex patterns. By moving away from slow Linear Programming (LP) solvers and using a clever "delay-and-merge" combinatorial approach, the authors achieved up to a 53% improvement in job completion times compared to previous state-of-the-art methods.
What Problem Does This Paper Address?
In modern data centers, applications like Spark or MapReduce don't just perform one big data transfer; they operate in stages. A "coflow" is a collection of parallel data flows between servers that must all finish before the next computation stage can begin.
While researchers have spent years optimizing how to schedule a single coflow, real-world jobs are usually a sequence of coflows with dependencies—represented as a Directed Acyclic Graph (DAG). For example, Coflow B might not be able to start until Coflow A finishes.
The challenge is that scheduling even a single multi-stage job to minimize its completion time is NP-hard. Previous attempts to solve this for multiple jobs relied on Linear Programming models that scaled poorly with the number of servers ($m$), leading to an approximation ratio of $O(m)$. In a data center with thousands of servers, an $O(m)$ error margin is massive. This paper aims to shrink that gap significantly.
Methods
The authors propose a suite of combinatorial algorithms that avoid the computational overhead of solving explicit LPs. Their approach rests on three main pillars:
- DMA (Delay-and-Merge Algorithm): For jobs with general DAG dependencies, the algorithm first creates an "isolated" schedule for each job. It then applies a random delay to each job's start time before merging them. This randomness helps prevent multiple jobs from trying to saturate the same network links simultaneously.
- BNA (Birkhoff-von Neumann Algorithm): To handle the actual bandwidth allocation, they use the BNA to decompose demand matrices into a series of matchings, ensuring that no server's input or output capacity is exceeded.
- G-DM (Grouping-Delay-Merge): To minimize total weighted completion time (where some jobs are more important than others), they use a combinatorial primal-dual ordering to group jobs. They then schedule these groups one by one, ensuring that high-priority jobs aren't stuck behind a "bottleneck" of lower-priority traffic.
For the specific case where dependencies form a rooted tree (a common structure in many data processing tasks), they refined the algorithm (DMA-SRT) to provide even tighter performance guarantees.
Datasets
The researchers evaluated their algorithms using a real-world workload trace from a Facebook cluster running Hive/MapReduce.
- Scale: The trace originally involved 150 racks.
- Complexity: It contained 267 coflows with a wide range of sizes (from 10 to over 21,000 flows per coflow).
- Synthetic Extension: To test multi-stage scenarios, they randomly partitioned these coflows into multi-stage jobs and generated dependency trees/DAGs to simulate complex application logic.
Key Insights and Ideas
- Interleaving is King: Previous state-of-the-art algorithms often scheduled coflows one at a time. This paper shows that "interleaving"—allowing flows from different coflows or different jobs to share the network at the same time—is much more efficient.
- The Power of Randomness: By simply adding a random "jitter" or delay to when a job starts, the algorithm naturally smooths out traffic bursts. This reduces the probability of server "collisions" where too many flows try to hit one receiver at once.
- Exponential Theoretical Leap: The most striking insight is the theoretical improvement. They moved the approximation ratio from $O(m)$ (linear in the number of servers) to $O(\mu \log(m) / \log \log(m))$ (essentially logarithmic). Since the number of coflows per job ($\mu$) is usually much smaller than the number of servers ($m$), this is a massive win for scalability.
Key Results
- General DAGs: In simulations with general dependency graphs, the proposed G-DM algorithm outperformed the previous state-of-the-art (the $O(m)$-algorithm) by up to 36%.
- Rooted Trees: When jobs followed a tree-based dependency structure, the improvement was even more dramatic, reaching up to 53%.
- Scalability: Unlike LP-based methods that become sluggish as the network grows, the combinatorial nature of these algorithms allows them to remain efficient even as the number of servers ($m$) increases.
- Robustness: The "Relative Standard Deviation" of their results was less than 1%, meaning the random delay strategy is highly reliable and doesn't require multiple runs to find a good schedule.
Limitations and Future Work
The authors identify a specific "optimality gap" for general DAGs. They proved that for certain complex DAG structures, the optimal makespan can be $\sqrt{\mu}$ times larger than the simple lower bounds used for scheduling. This suggests that while their current algorithms are a huge step forward, there is still room to refine how we handle the most "tangled" dependency graphs.
Additionally, while the paper discusses an online scenario (jobs arriving over time), further research could explore more sophisticated "backfilling" strategies to use idle network capacity even more aggressively without violating dependency constraints.
Summary updated