Scheduling dependent coflows to minimize the total weighted job completion time in datacenters

摘要

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. 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) in general case, and 3 in special case, where M is the number of hosts. Evaluation results demonstrate that, the largest gap between our algorithm and the lower bound is only 9.14%. In testbeds, we reduce the JCT by up to 81.65% comparing with pure DCTCP. In simulations, we reduce the average JCT by up to 33.48% comparing with Aalo, a heuristic multi-stage coflow scheduler; we reduce the total weighted JCT by up to 83.58% comparing with LP-OV-LS, the state-of-the-art approximation algorithm of coflow scheduling. (C) 2019 Elsevier B.V. All rights reserved.