Fair Coflow Scheduling via Controlled Slowdown

The average coflow completion time (CCT) is the
standard performance metric in coflow scheduling. However,
standard CCT minimization may introduce unfairness between
the data transfer phase of different computing jobs. Thus, while
progress guarantees have been introduced in the literature to
mitigate this fairness issue, the trade-off between fairness and
efficiency of data transfer is hard to control.
This paper introduces a fairness framework for coflow scheduling based on the concept of slowdown, i.e., the performance loss
of a coflow compared to isolation. By controlling the slowdown it
is possible to enforce a target coflow progress while minimizing
the average CCT. In the proposed framework, the minimum
slowdown for a batch of coflows can be determined in polynomial
time. By showing the equivalence with Gaussian elimination,
slowdown constraints are introduced into primal-dual iterations
of the CoFair algorithm. The algorithm extends the class of the
σ-order schedulers to solve the fair coflow scheduling problem
in polynomial time. It provides a 4-approximation of the average
CCT w.r.t. an optimal scheduler. Extensive numerical results
demonstrate that this approach can trade off average CCT
for slowdown more efficiently than existing state of the art
schedulers.