Decentralized Deadline-Aware Coflow Scheduling for Datacenter Networks

This paper presents D-2-CAS, a novel decentralized coflow scheduling system, to minimize the rate of deadline missed coflow for datacenter networks. To design D-2-CAS, we first formulate the deadline-missed coflow minimization problem and show its equivalence with the well-known problem of minimizing the late jobs in a concurrent open shop, which is NP-hard in ordinary sense. Inspired by Moore-Hodgso's algorithm (MHA), the optimal solution for minimizing late jobs on a single machine, we design an efficient coflow schedule algorithm, CS-MHA, and further propose its decentralized implementation, D-2-CAS. Basically, each sender in D-2-CAS periodically runs a part of CS-MHA to get a local suggestion for flow priority assignment, and then multiple senders of a coflow negotiate for an orchestrated priority by leveraging their common data receivers. Via delivering each coflow's packets with its negotiated priority, senders finally carry out efficient deadline-aware coflow scheduling in a decentralized fashion. To the best of our knowledge, this is the first paper that theoretically investigates the deadline-aware coflow scheduling problem, while D-2-CAS is the first decentralized solution. Real parameter driven simulations imply that, with the simple yet efficient mechanism, D-2-CAS greatly outperforms all existing solutions on reducing the deadline-missed coflows (e.g., outperforms Varys more than 2x).