Efficient online coflow routing and scheduling

Yupeng Li, Shaofeng H.C. Jiang, Haisheng Tan*, Chenzi Zhang, Guihai Chen, Jipeng Zhou, Francis C.M. Lau

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

46 Citations (Scopus)

Abstract

A coflow is a collection of related parallel flows that occur typically between two stages of a multi-stage compute task in a network, such as shuffle flows in MapReduce. The coflow abstraction allows applications to convey their semantics to the network so that application-level requirements (e.g., minimizing the completion time of the slowest flow) can be better satisfied. In this paper, we study the routing and scheduling of multiple coflows to minimize the average coflow completion time (CCT). We first propose a rounding-based randomized approximation algorithm, called OneCoflow, for single coflow routing and scheduling. The multiple coflow problem is more challenging as coexisting coflows will compete for the same network resources such as link bandwidths. To minimize the average CCT, we derive an online multiple coflow routing and scheduling algorithm, called OMCoflow, and prove that it has a reasonably good competitive ratio. To the best of our knowledge, this is the first online algorithm with theoretical performance guarantees which considers routing and scheduling simultaneously for multi-coflows. Compared with existing methods, OMCoflow runs more efficiently, and it avoids the problem of frequently rerouting the flows. Extensive simulations on a Facebook data trace show that OM Coflow outperforms the state-of-the-art heuristic schemes significantly (e.g., reducing the average CCT by up to 41.8% and the execution time by up to 99.2% against RAPIER [28]).

Original languageEnglish
Title of host publicationMobiHoc 2016 - Proceedings of the 17th ACM International Symposium on Mobile Ad Hoc Networking and Computing
PublisherAssociation for Computing Machinery (ACM)
Pages161-170
Number of pages10
ISBN (Electronic)9781450341844
DOIs
Publication statusPublished - 5 Jul 2016
MoE publication typeA4 Article in a conference publication
EventACM International Symposium on Mobile Ad Hoc Networking and Computing - Paderborn, Germany
Duration: 5 Jul 20168 Jul 2016
Conference number: 17

Publication series

NameProceedings of the International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc)
Volume05-08-July-2016

Conference

ConferenceACM International Symposium on Mobile Ad Hoc Networking and Computing
Abbreviated titleMobiHoc
Country/TerritoryGermany
CityPaderborn
Period05/07/201608/07/2016

Keywords

  • Coflow
  • Data center networks
  • Online algorithm
  • Routing and scheduling

Fingerprint

Dive into the research topics of 'Efficient online coflow routing and scheduling'. Together they form a unique fingerprint.

Cite this