On Scheduling Coflows

Saba Ahmadi*, Samir Khuller, Manish Purohit, Sheng Yang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

Applications designed for data-parallel computation frameworks such as MapReduce usually alternate between computation and communication stages. Coflow scheduling is a recent popular networking abstraction introduced to capture such application-level communication patterns in datacenters. In this framework, a datacenter is modeled as a single non-blocking switch with m input ports and m output ports. A coflow j is a collection of flow demands {dioj}i∈{1,…,m},o∈{1,…,m} that is said to be complete once all of its requisite flows have been scheduled. We consider the offline coflow scheduling problem with and without release times to minimize the total weighted completion time. Coflow scheduling generalizes the well studied concurrent open shop scheduling problem and is thus NP-hard. Qiu et al. (in: ACM Symposium on parallelism in algorithms and architectures. ACM, New York, pp 294–303, 2015) obtain the first constant approximation algorithms for this problem via LP rounding and give a deterministic 673-approximation and a randomized (9+1623)≈16.54-approximation algorithm. In this paper, we give a combinatorial algorithm that yields a deterministic 5-approximation algorithm for coflow scheduling with release times, and a deterministic 4-approximation for the case without release times. As for concurrent open shop problem with release times, we give a combinatorial 3-approximation algorithm.

Original languageEnglish (US)
Pages (from-to)3604-3629
Number of pages26
JournalAlgorithmica
Volume82
Issue number12
DOIs
StatePublished - Dec 1 2020

Keywords

  • Approximation algorithms
  • Coflow scheduling
  • Concurrent open shop

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'On Scheduling Coflows'. Together they form a unique fingerprint.

Cite this