2018/12/17 by Li Shi, Shi, Li, Junwei Zhang +6
Computer Science · #Cloud Computing and Resource Management #Distributed and Parallel Computing Systems #FOS: Computer and information sciences #IoT and Edge/Fog Computing #Networking and Internet Architecture (cs.NI) #cs.NI
paper · pdf · doi:10.48550/arxiv.1812.06898
10 pages, 5 figures
arxiv created 2018/12/17 · openalex publication_date 2018/12/17 · arxiv updated 2018/12/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.