On scheduling coflows

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

*Corresponding author for this work

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

11 Scopus citations

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 (djio)i∈m,o∈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, Stein and Zhong [15] obtain the first constant approximation algorithms for this problem via LP rounding and give a deterministic673 -approximation and a randomized (9 +16√32) ≈ 16.54-approximation algorithm. In this paper, we give a combinatorial algorithm that yields a deterministic 5-approximation algorithm with release times, and a deterministic 4-approximation for the case without release time.

Original languageEnglish (US)
Title of host publicationInteger Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Proceedings
EditorsFriedrich Eisenbrand, Jochen Koenemann
PublisherSpringer Verlag
Pages13-24
Number of pages12
ISBN (Print)9783319592497
DOIs
StatePublished - 2017
Event19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017 - Waterloo, Canada
Duration: Jun 26 2017Jun 28 2017

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10328 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017
CountryCanada
CityWaterloo
Period6/26/176/28/17

Keywords

  • Coflow scheduling
  • Concurrent open shop

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

Cite this