Scheduling coflows of multi-stage jobs under network resource constraints

Abstract As an emerging network abstraction, coflow greatly improves the communication performance of data-parallel computing jobs. Many existing studies have focused on the design of coflow scheduling to minimize the completion time of jobs. However, they treat the underlying network as a large non-blocking switch without considering the constraints of network resources, which may increase network bottlenecks, reduce link capacity utilization, and extend job completion time. In this paper, we take network resource constraints into account and study how to schedule coflows in multi-stage jobs with the objective of minimizing the total weighted job completion time. We first formalize this multi-stage job scheduling problem as nonlinear programming and prove its NP-hardness. By introducing a priority order of jobs using a linear programming relaxation-based approach, we propose a polynomial-time algorithm with a performance guarantee, which can achieve a constant approximation ratio in many typical scenarios. Simulation results based on a Facebook trace show that, compared with a state-of-the-art approach, our algorithm can shorten the average weighted job completion time by up to 48.46% and run faster by up to 19.12 × .