Near optimal coflow scheduling in networks

Mosharaf Chowdhury, Samir Khuller, Manish Purohit, Sheng Yang, Jie You

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

The coflow scheduling problem has emerged as a popular abstraction in the last few years to study data communication problems within a data center [6]. In this basic framework, each coflow has a set of communication demands and the goal is to schedule many coflows in a manner that minimizes the total weighted completion time. A coflow is said to complete when all its communication needs are met. This problem has been extremely well studied for the case of complete bipartite graphs that model a data center with full bisection bandwidth and several approximation algorithms and effective heuristics have been proposed recently [1, 2, 29]. In this work, we study a slightly different model of coflow scheduling in general graphs (to capture traffic between data centers [15, 29]) and develop practical and efficient approximation algorithms for it. Our main result is a randomized 2 approximation algorithm for the single path and free path model, significantly improving prior work. In addition, we demonstrate via extensive experiments that the algorithm is practical, easy to implement and performs well in practice.

Original languageEnglish (US)
Title of host publicationSPAA 2019 - Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures
PublisherAssociation for Computing Machinery
Pages123-134
Number of pages12
ISBN (Electronic)9781450361842
DOIs
StatePublished - Jun 17 2019
Event31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2019 - Phoenix, United States
Duration: Jun 22 2019Jun 24 2019

Publication series

NameAnnual ACM Symposium on Parallelism in Algorithms and Architectures

Conference

Conference31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2019
CountryUnited States
CityPhoenix
Period6/22/196/24/19

Keywords

  • Cloud computing
  • Coflow
  • LP relaxation
  • LP rounding
  • Network flow
  • Scheduling

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Fingerprint Dive into the research topics of 'Near optimal coflow scheduling in networks'. Together they form a unique fingerprint.

Cite this