  In distributed computing frameworks like MapReduce, Spark, and Dyrad, a
coflow is a set of flows transferring data between two stages of a job. The job
cannot start its next stage unless all flows in the coflow finish. To improve
the execution performance of such a job, it is crucial to reduce the completion
time of a coflow which can contribute more than 50% of the job completion time.
While several schedulers have been proposed, we observe that routing, as a
factor greatly impacting the Coflow Completion Time (CCT), has not been well
considered. In this paper, we focus on the coflow scheduling problem and
jointly consider routing and bandwidth allocation. We first provide an
analytical solution to the problem of optimal bandwidth allocation with
pre-determined routes. We then formulate the coflow scheduling problem as a
Mixed Integer Non-linear Programming problem and present its relaxed convex
optimization problem. We further propose two algorithms, CoRBA and its
simplified version: CoRBA-fast, that jointly perform routing and bandwidth
allocation for a given coflow while minimizes the CCT. Through both offline and
online simulations, we demonstrate that CoRBA reduces the CCT by 40%-500%
compared to the state-of-the-art algorithms. Simulation results also show that
CoRBA-fast can be tens of times faster than all other algorithms with around
10% performance degradation compared to CoRBA, which makes the use of
CoRBA-fast very applicable in practice.
