TY - JOUR
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 Grants CNS 156019 and CCF 1655073 (Eager), and partially supported by an Amazon Grant
Publisher Copyright:
© 2020, Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2020/12/1
Y1 - 2020/12/1
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 {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.
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 {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.
KW - Approximation algorithms
KW - Coflow scheduling
KW - Concurrent open shop
UR - http://www.scopus.com/inward/record.url?scp=85087953906&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85087953906&partnerID=8YFLogxK
U2 - 10.1007/s00453-020-00741-3
DO - 10.1007/s00453-020-00741-3
M3 - Article
AN - SCOPUS:85087953906
SN - 0178-4617
VL - 82
SP - 3604
EP - 3629
JO - Algorithmica
JF - Algorithmica
IS - 12
ER -