An Improved Bound for Minimizing the Total Weighted Completion Time of Coflows in Datacenters
An Improved Bound for Minimizing the Total Weighted Completion Time of Coflows in Datacenters
复制标题
DOI：
10.1109/tnet.2018.2845852
复制
发表时间：
2017-04
期刊：
影响因子：
--
通讯作者：
Mehrnoosh Shafiee;Javad Ghaderi
中科院分区：
文献类型：
--
作者：
Mehrnoosh Shafiee;Javad Ghaderi
在数据并行计算框架中，中间并行数据通常在各个阶段产生，需要在数据中心网络中的服务器之间传输（例如，MapReduce 中的 shuffle 阶段）。除非收到前一阶段的所有所需数据片段，否则阶段通常无法启动或完成。 Coflow 是最近提出的一种网络抽象，用于捕获此类通信模式。我们考虑在共享数据中心网络中有效调度具有发布日期的协同流的问题，以最小化协同流的总加权完成时间。最近提出了几种启发式方法来解决这个问题，以及一些具有可证明性能保证的多项式时间近似算法。我们在本文中的主要成果是改进了先验已知结果的多项式时间确定性算法。具体来说，我们提出了一种近似率为 5 的确定性算法，这将先验最佳已知比率提高到 12。对于所有协同流在时间为零时释放的特殊情况，我们的确定性算法获得近似比率为 4，这将先验最佳已知比率提高到 8。我们方法的关键要素是改进的线性程序公式，用于对协同流进行排序，然后采用简单的列表调度策略。使用合成和真实流量轨迹的广泛模拟结果验证了我们的算法的性能并显示了相对于先前方法的改进。
In data-parallel computing frameworks, intermediate parallel data is often produced at various stages which needs to be transferred among servers in the datacenter network (e.g., the shuffle phase in MapReduce). A stage often cannot start or be completed unless all the required data pieces from the preceding stage are received. Coflow is a recently proposed networking abstraction to capture such communication patterns. We consider the problem of efficiently scheduling coflows with release dates in a shared datacenter network so as to minimize the total weighted completion time of coflows. Several heuristics have been proposed recently to address this problem, as well as a few polynomial-time approximation algorithms with provable performance guarantees. Our main result in this paper is a polynomial-time deterministic algorithm that improves the prior known results. Specifically, we propose a deterministic algorithm with approximation ratio of 5, which improves the prior best known ratio of 12. For the special case when all coflows are released at time zero, our deterministic algorithm obtains approximation ratio of 4 which improves the prior best known ratio of 8. The key ingredient of our approach is an improved linear program formulation for sorting the coflows followed by a simple list scheduling policy. Extensive simulation results, using both synthetic and real traffic traces, are presented that verify the performance of our algorithm and show improvement over the prior approaches.