Towards Practical and Near-Optimal Coflow Scheduling for Data Center Networks
Lists
Only you see this
Abstract
In current data centers, an application (e.g., MapReduce, Dryad, search platform, etc.) usually generates a group of parallel flows to complete a job. These flows compose a coflow and only completing them all is meaningful to the application. Accordingly, minimizing the average Coflow Completion Time (CCT) becomes a critical objective of flow scheduling. However, achieving this goal in today's Data Center Networks (DCNs) is quite challenging, not only because the schedule problem is theoretically NP-hard, but also because it is tough to perform practical flow scheduling in large-scale DCNs. In this paper, we find that minimizing the average CCT of a set of coflows is equivalent to the well-known problem of minimizing the sum of completion times in a concurrent open shop. As there are abundant existing solutions for concurrent open shop, we open up a variety of techniques for coflow scheduling. Inspired by the best known result, we derive a 2-approximation algorithm for coflow scheduling, and further develop a decentralized coflow scheduling system, D-CAS, which avoids the system problems associated with current centralized proposals while addressing the performance challenges of decentralized suggestions. Trace-driven simulations indicate that D-CAS achieves a performance close to Varys, the state-of-the-art centralized method, and outperforms Baraat, the only existing decentralized method, significantly.
BibTeX
@article{luo2016towards,
author = {Shouxi Luo and Hongfang Yu and Yangming Zhao and Sheng Wang and Shui Yu and Lemin Li},
title = {{Towards Practical and Near-Optimal Coflow Scheduling for Data Center Networks}},
journal = {IEEE Trans. Parallel Distributed Syst.},
year = {2016},
url = {https://openreview.net/forum?id=7zGBsX-Nj2c},
}Loading related content...