Towards Practical and Near-Optimal Coflow Scheduling for Data Center Networks
Towards Practical and Near-Optimal Coflow Scheduling for Data Center Networks
复制标题
实现数据中心网络实用且近乎最优的协流调度
DOI：
10.1109/tpds.2016.2525767
复制
发表时间：
2016-11-01
影响因子：
5.3
通讯作者：
Li, Lemin
中科院分区：
文献类型：
--
作者：
Luo, Shouxi;Yu, Hongfang;Li, Lemin
在当前的数据中心中，应用程序（例如MapReduce、Dryad、搜索平台等）通常会生成一组并行流来完成一项作业。这些流程组成了一个协同流程，只有完成它们才对应用程序有意义。因此，最小化平均协流完成时间（CCT）成为流调度的关键目标。然而，在当今的数据中心网络（DCN）中实现这一目标相当具有挑战性，不仅因为调度问题在理论上是NP困难的，而且还因为在大规模DCN中执行实际的流调度是很困难的。在本文中，我们发现最小化一组协流的平均 CCT 相当于最小化并发开放商店中的完成时间总和的众所周知的问题。由于现有的并发开放商店解决方案非常丰富，因此我们开放了多种协流调度技术。受最著名结果的启发，我们推导了协流调度的2近似算法，并进一步开发了去中心化协流调度系统D-CAS，它避免了与当前集中式建议相关的系统问题，同时解决了去中心化建议的性能挑战。跟踪驱动的模拟表明，D-CAS 的性能接近最先进的集中式方法 Varys，并且显着优于现有的唯一分散式方法 Baraat。
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.