Scheduling Coflows with Dependency Graph

Mehrnoosh Shafiee, Javad Ghaderi

Abstract

Applications in data-parallel computing typically consist of multiple stages. In each stage, a set of intermediate parallel data flows (Coflow) is produced and transferred between servers to enable starting of next stage. While there has been much research on scheduling isolated coflows, the dependency between coflows in multi-stage jobs has been largely ignored. In this paper, we consider scheduling coflows of multi-stage jobs represented by general DAGs (Directed Acyclic Graphs) in a shared data center network, so as to minimize the total weighted completion time of jobs. This problem is significantly more challenging than the traditional coflow scheduling, as scheduling even a single multi-stage job to minimize its completion time is shown to be NP-hard. In this paper, we propose a polynomial-time algorithm with approximation ratio of $O(\mu\log(m)/\log(\log(m)))$, where $\mu$ is the maximum number of coflows in a job and $m$ is the number of servers. For the special case that the jobs' underlying dependency graphs are rooted trees, we modify the algorithm and improve its approximation ratio. To verify the performance of our algorithms, we present simulation results using real traffic traces that show up to $53 \%$ improvement over the prior approach. We conclude the paper by providing a result concerning an optimality gap for scheduling coflows with general DAGs.

Introduction

In modern data centers, applications like Spark or MapReduce operate in distinct stages. A "coflow" is a collection of parallel data flows between servers that must all finish before the next computation stage can begin. While optimizing single coflows is well-studied, real-world jobs are usually sequences of coflows with complex dependencies represented as a Directed Acyclic Graph (DAG). For example, Coflow B might not be able to start until Coflow A finishes. Scheduling even a single multi-stage job to minimize completion time is NP-hard, and previous solutions relied on Linear Programming (LP) models that scaled poorly with the number of servers ($m$), leading to a massive $O(m)$ error margin.

A multi-stage job represented as a Directed Acyclic Graph (DAG) of coflows mapped to network switches.

Proposed Methods

We introduce a suite of combinatorial algorithms that avoid the computational overhead of solving explicit LPs. Our approach rests on three main pillars:

  1. Delay-and-Merge Algorithm (DMA): For jobs with general DAG dependencies, the algorithm creates an isolated schedule for each job and applies a random delay to each job's start time before merging them. This randomness prevents multiple jobs from saturating the same network links simultaneously.
  2. Birkhoff-von Neumann Algorithm (BNA): To handle bandwidth allocation, we use BNA to decompose demand matrices into a series of matchings, ensuring no server's capacity is exceeded.
  3. Grouping-Delay-Merge (G-DM): To minimize total weighted completion time, we use a combinatorial primal-dual ordering to group jobs. High-priority jobs are scheduled first to ensure they aren't delayed by lower-priority traffic bottlenecks.

For rooted tree dependencies, we refined the algorithm (DMA-SRT) to provide even tighter performance guarantees.

Experimental Evaluation

We evaluated our algorithms using a real-world workload trace from a Facebook cluster running Hive/MapReduce, involving 150 racks and 267 coflows. To test multi-stage scenarios, we randomly partitioned these coflows into jobs with synthetic dependency trees and DAGs.

Total completion time comparison across different algorithms and average number of coflows.

Key Results

  • Performance Gains: In simulations with general dependency graphs, the G-DM algorithm outperformed the previous state-of-the-art $O(m)$-algorithm by up to 36%. For rooted trees, the improvement reached 53%.
  • Scalability: Unlike LP-based methods, our combinatorial algorithms remain efficient as the number of servers ($m$) increases. We moved the theoretical approximation ratio from linear $O(m)$ to essentially logarithmic $O(\mu \log(m) / \log \log(m))$.
  • Interleaving Efficiency: Our results show that allowing flows from different coflows or jobs to share the network simultaneously ("interleaving") is significantly more efficient than scheduling them one at a time.

Conclusion

This work demonstrates that a combinatorial "delay-and-merge" approach significantly improves the efficiency of multi-stage data center jobs. While we identified an optimality gap for highly complex DAG structures, our algorithms provide a scalable and robust framework for modern big data applications. Future work will explore more aggressive backfilling strategies to utilize idle network capacity without violating dependency constraints.

Summary updated

Abstract

Applications in data-parallel computing typically consist of multiple stages. In each stage, a set of intermediate parallel data flows (Coflow) is produced and transferred between servers to enable starting of next stage. While there has been much research on scheduling isolated coflows, the dependency between coflows in multi-stage jobs has been largely ignored. In this paper, we consider scheduling coflows of multi-stage jobs represented by general DAGs (Directed Acyclic Graphs) in a shared data center network, so as to minimize the total weighted completion time of jobs. This problem is significantly more challenging than the traditional coflow scheduling, as scheduling even a single multi-stage job to minimize its completion time is shown to be NP-hard. In this paper, we propose a polynomial-time algorithm with approximation ratio of $O(\mu\log(m)/\log(\log(m)))$, where $\mu$ is the maximum number of coflows in a job and $m$ is the number of servers. For the special case that the jobs' underlying dependency graphs are rooted trees, we modify the algorithm and improve its approximation ratio. To verify the performance of our algorithms, we present simulation results using real traffic traces that show up to $53 \%$ improvement over the prior approach. We conclude the paper by providing a result concerning an optimality gap for scheduling coflows with general DAGs.
BibTeX
@article{shafiee2022scheduling,
  author = {Mehrnoosh Shafiee and Javad Ghaderi},
  title = {{Scheduling Coflows with Dependency Graph}},
  journal = {IEEE/ACM Trans. Networking},
  year = {2022},
  url = {https://openreview.net/forum?id=JFBsCMGqRb},
}
Figure