On scheduling coflows

Saba Ahmadi; Samir Khuller; Manish Purohit; Sheng Yang

doi:10.1007/978-3-319-59250-3_2

On scheduling coflows

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

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

13 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 (d^j_io)_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 deterministic⁶⁷₃ -approximation and a randomized (9 +^16√₃²) ≈ 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 language	English (US)
Title of host publication	Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Proceedings
Editors	Friedrich Eisenbrand, Jochen Koenemann
Publisher	Springer Verlag
Pages	13-24
Number of pages	12
ISBN (Print)	9783319592497
DOIs	https://doi.org/10.1007/978-3-319-59250-3_2
State	Published - 2017
Event	19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017 - Waterloo, Canada Duration: Jun 26 2017 → Jun 28 2017

Publication series

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

Conference

Conference	19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017
Country/Territory	Canada
City	Waterloo
Period	6/26/17 → 6/28/17

Funding

This work is supported by NSF grant CNS 156019.

Keywords

Coflow scheduling
Concurrent open shop

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-59250-3_2

Cite this

Ahmadi, S., Khuller, S., Purohit, M., & Yang, S. (2017). On scheduling coflows. In F. Eisenbrand, & J. Koenemann (Eds.), Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Proceedings (pp. 13-24). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10328 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-59250-3_2

Ahmadi, Saba ; Khuller, Samir ; Purohit, Manish et al. / On scheduling coflows. Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Proceedings. editor / Friedrich Eisenbrand ; Jochen Koenemann. Springer Verlag, 2017. pp. 13-24 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{686bd2b7f06046adb00af30abafbfc88,

title = "On scheduling coflows",

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.",

keywords = "Coflow scheduling, Concurrent open shop",

author = "Saba Ahmadi and Samir Khuller and Manish Purohit and Sheng Yang",

note = "Funding Information: This work is supported by NSF grant CNS 156019. Publisher Copyright: {\textcopyright} Springer International Publishing AG 2017.; 19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017 ; Conference date: 26-06-2017 Through 28-06-2017",

year = "2017",

doi = "10.1007/978-3-319-59250-3_2",

language = "English (US)",

isbn = "9783319592497",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "13--24",

editor = "Friedrich Eisenbrand and Jochen Koenemann",

booktitle = "Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Proceedings",

}

Ahmadi, S, Khuller, S, Purohit, M & Yang, S 2017, On scheduling coflows. in F Eisenbrand & J Koenemann (eds), Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10328 LNCS, Springer Verlag, pp. 13-24, 19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017, Waterloo, Canada, 6/26/17. https://doi.org/10.1007/978-3-319-59250-3_2

On scheduling coflows. / Ahmadi, Saba; Khuller, Samir; Purohit, Manish et al.
Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Proceedings. ed. / Friedrich Eisenbrand; Jochen Koenemann. Springer Verlag, 2017. p. 13-24 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10328 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - On scheduling coflows

AU - Ahmadi, Saba

AU - Khuller, Samir

AU - Purohit, Manish

AU - Yang, Sheng

N1 - Funding Information: This work is supported by NSF grant CNS 156019. Publisher Copyright: © Springer International Publishing AG 2017.

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

KW - Coflow scheduling

KW - Concurrent open shop

UR - http://www.scopus.com/inward/record.url?scp=85020535183&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85020535183&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-59250-3_2

DO - 10.1007/978-3-319-59250-3_2

M3 - Conference contribution

AN - SCOPUS:85020535183

SN - 9783319592497

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 13

EP - 24

BT - Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Proceedings

A2 - Eisenbrand, Friedrich

A2 - Koenemann, Jochen

PB - Springer Verlag

T2 - 19th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2017

Y2 - 26 June 2017 through 28 June 2017

ER -

Ahmadi S, Khuller S, Purohit M, Yang S. On scheduling coflows. In Eisenbrand F, Koenemann J, editors, Integer Programming and Combinatorial Optimization - 19th International Conference, IPCO 2017, Proceedings. Springer Verlag. 2017. p. 13-24. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-59250-3_2

On scheduling coflows

Abstract

Publication series

Conference

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this