Scheduling Coflows Of Multi-stage Jobs To Minimize The Total Weighted Job Completion Time

Authors:
Bingchuan Tian Nanjing University, P.R. China
Chen Tian Nanjing University, P.R. China
Haipeng Dai Nanjing University & State Key Laboratory for Novel Software Technology, P.R. China
Bingquan Wang Nanjing University, P.R. China

Abstract:

Datacenter networks are critical to Cloud computing. The coflow abstraction is a major leap forward of application-aware network scheduling. In the context of multi-stage jobs, there are dependencies among coflows. As a result, there is a large divergence between coflow-completion-time (CCT) and job-completion-time (JCT). To our best knowledge, this is the first work that systematically studies: how to schedule dependent coflows of multi-stage jobs, so that the total weighted job completion time can be minimized. We present a formal mathematical formulation. We also prove that this problem is strongly NP-hard. Inspired by the optimal solution of the relaxed linear programming, we design an algorithm that runs in polynomial time to solve this problem with an approximation ratio of (2M + 1), where M is the number of machines. Evaluation results demonstrate that, the largest gap between our algorithm and the lower bound is only 9.14%. We reduce the average JCT by up to 33.48% compared with Aalo, a heuristic multi-stage coflow scheduler. We reduce the total weighted JCT by up to 83.31% compared with LP-OV-LS, the state-of-the-art approximation algorithm of coflow scheduling.

You may want to know: