@inproceedings{01990f4aa3b246ebb8655b24c072dd6c,
title = "Near optimal coflow scheduling in networks",
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.",
keywords = "Cloud computing, Coflow, LP relaxation, LP rounding, Network flow, Scheduling",
author = "Mosharaf Chowdhury and Samir Khuller and Manish Purohit and Sheng Yang and Jie You",
note = "Publisher Copyright: {\textcopyright} 2019 Copyright held by the owner/author(s).; 31st ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2019 ; Conference date: 22-06-2019 Through 24-06-2019",
year = "2019",
month = jun,
day = "17",
doi = "10.1145/3323165.3323179",
language = "English (US)",
series = "Annual ACM Symposium on Parallelism in Algorithms and Architectures",
publisher = "Association for Computing Machinery",
pages = "123--134",
booktitle = "SPAA 2019 - Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures",
}