Since the inception of coflow in 2012, the abstraction and works surrounding it are growing at a fast pace. In addition to systems building, we have seen a rise of theoretical analyses of the coflow scheduling problem. One of the most recent ones to this end has even received a Best Student Paper Award in SIGCOMM’2018.
Today I want to share a recent development in theoretical analysis of coflow scheduling in the context of general graphs. While datacenter networks can be abstracted out as a non-blocking switch, under failures and load imbalance this simplistic model does not hold any more. More importantly, inter-datacenter wide-area networks (WANs) are never non-blocking anyway. Naturally, we need a new analytical framework that allows for a broader variety of network topologies. In our recent work with our colleagues at University of Maryland and Google, we provide a randomized 2-approximation algorithm for single path and free path models of coflow scheduling over the WAN, significantly improving over the state-of-the-art.
The Coflow scheduling problem has emerged as a popular abstraction in the last few years to study data communication problems within a data center [5]. In this basic framework, each coflow has a set of communication demands and the goal is to schedule many coflows in a manner that minimizes the total weighted completion time. A coflow is said to complete when all its communication needs are met. This problem has been extremely well studied for the case of complete bipartite graphs that model a data center with full bisection bandwidth and several approximation algorithms and effective heuristics have been proposed recently [1, 2, 29].
In this work, we study a slightly different model of coflow scheduling in general graphs (to capture traffic between datacenters [15, 29]) and develop practical and efficient approximation algorithms for it. Our main result is a randomized 2 approximation algorithm for the single path and free path model, significantly improving prior work. In addition, we demonstrate via extensive experiments that the algorithm is practical, easy to implement and performs well in practice.
This is my first paper in SPAA, but all thanks go to Sheng Yang at UMD whose dissertation will include this work and his advisor Samir and collaborator Manish at Google. My student Jie You (Jimmy) did the evaluation for this work to compare it against existing works on different WAN topologies and workloads. It was a pleasant experience with the theory folks and helping them in better understanding the constraints. I look forward to many more future collaborations!