Experimental Analysis of Algorithms for Coflow Scheduling

Zhen Qiu, Cliff Stein, Yuan Zhong

Abstract

Datacenter applications like MapReduce rely on massive parallel data transfers, modeled as "coflows." This paper experimentally evaluates scheduling algorithms for minimizing coflow completion times, comparing simple heuristics against a theoretically sound LP-based approximation. Findings indicate that combining intelligent ordering with grouping and balanced backfilling yields near-optimal performance in both offline and online settings.

Introduction

Modern data-parallel frameworks such as Hadoop, Spark, and MapReduce process jobs in alternating stages of computation and communication. During communication, massive amounts of intermediate data are shuffled across the datacenter network. Traditional network scheduling focuses on individual data flows, but a computation stage often cannot start until all parallel flows from the preceding communication stage have finished. Consequently, the completion time of the entire collection of related flows—the coflow—is the critical metric.

Scheduling coflows across a network switch under matching constraints (where each port processes one unit at a time) to minimize total weighted completion time is a strongly NP-hard problem. This study evaluates the practical performance of various scheduling algorithms and heuristics on real and simulated datacenter workloads.

Methodology

The authors evaluate a two-stage approach to coflow scheduling:

  1. Ordering: Determining the sequence of coflows. Five greedy heuristics (e.g., Shortest Total Processing Time [STPT], Earliest Completion Time [ECT], FIFO) are tested against a sophisticated LP-based ordering that solves a time-interval relaxation to establish a mathematically guaranteed baseline.
  2. Scheduling: Assigning data transfers to network ports. Key enhancements include:
  3. Backfilling: Utilizing idle ports for subsequent coflows.
  4. Balanced Backfilling: A novel augmentation technique that spreads out coflow matrix unevenness before decomposition.
  5. Grouping: Aggregating multiple skewed coflows into a single balanced coflow.
Algorithm 1: Balanced Coflow Augmentation for efficient port matching.

The offline algorithms are adapted for online use by re-solving the ordering whenever a new coflow arrives.

Experimental Setup

The evaluation uses two primary data sources:

  • Real-World Data: A Hive/MapReduce trace from a Facebook production cluster (3,000 machines, 150 racks, modeled as a 150x150 switch).
  • Synthetic Data: Simulated instances (160 coflows on a 16x16 network) with varying sparsity and inter-arrival distributions.

Key Insights

  • Backfilling and Grouping are Crucial: Intelligent ordering alone is insufficient. Grouping and balanced backfilling drastically reduce unforced idle time by smoothing out "spiky" job demands.
  • Impact of Release Times: Simple heuristics like ECT perform well when jobs start simultaneously but struggle with staggered release times, as they may wait for preceding coflows, negating backfilling benefits.
  • The "Cost of Matching": Comparing standard coflows to "diagonal" ones (no port contention) revealed that matching constraints can more than double total completion time.
  • Convergence to FIFO: When inter-arrival times are large relative to coflow size, the network clears quickly, and all heuristics eventually perform similarly to FIFO.

Results

The experimental results demonstrate significant performance improvements over baseline methods.

Comparison of scheduling orderings and the impact of grouping/backfilling on completion times.
  • Massive Gains: Smart ordering heuristics reduced total weighted completion times by 7.88x to 9.11x on the Facebook trace compared to FIFO.
  • Cumulative Enhancements: On Facebook data, grouping reduced completion time by up to 24.27%, with balanced backfilling adding another 20.31% improvement.
  • LP-based Dominance: The LP-based algorithm consistently achieved the best results across scenarios. Its online version performed within 91% to 97% of the theoretical optimal lower bound.

Conclusion

While the LP-based approach is highly effective, its computational overhead (up to 90 seconds for large batches) may limit its use in ultra-low-latency environments. Future work should explore user-oriented metrics like flow time and the development of distributed algorithms for easier hardware implementation.

Summary updated

BibTeX
@inproceedings{qiu2016experimental,
  author = {Zhen Qiu and Cliff Stein and Yuan Zhong},
  title = {{Experimental Analysis of Algorithms for Coflow Scheduling}},
  booktitle = {SEA},
  year = {2016},
  doi = {10.1007/978-3-319-38851-9\_18},
}
Figure