Scheduling coflows for minimizing the total weighted completion time in heterogeneous parallel networks

• Published in: Journal of parallel and distributed computing 2023-12, Vol.182, p.104752, Article 104752
• Main Author: Chen, Chi-Yeh
• Format: Article
• Language: English
• Subjects: Approximation algorithms; Coflow; Datacenter network; Heterogeneous parallel network; Scheduling algorithms
• ISSN: 0743-7315; 1096-0848
• DOI: 10.1016/j.jpdc.2023.104752

Coflow is a network abstraction used to represent communication patterns in data centers. The coflow scheduling problem encountered in large data centers is a challenging NP-hard problem. Many previous studies on coflow scheduling mainly focus on the single-core model. However, with the growth of data centers, this single-core model is no longer sufficient. This paper addresses the coflow scheduling problem within heterogeneous parallel networks, which feature an architecture consisting of multiple network cores running in parallel. In this paper, two polynomial-time approximation algorithms are developed for the flow-level scheduling problem and the coflow-level scheduling problem in heterogeneous parallel networks, respectively. For the flow-level scheduling problem, the proposed algorithm achieves an approximation ratio of O(log⁡m/log⁡log⁡m) when all coflows are released at arbitrary times, where m represents the number of network cores. On the other hand, in the coflow-level scheduling problem, the proposed algorithm achieves an approximation ratio of O(m(log⁡m/log⁡log⁡m)2) when all coflows are released at arbitrary times. Moreover, we propose a heuristic algorithm for the flow-level scheduling problem. Simulation results using synthetic traffic traces validate the performance of our algorithms and show improvements over the previous algorithm. •Algorithm achieves O(log⁡m/log⁡log⁡m) approximation ratio for flow-level scheduling, where m is network cores.•For coflow-level scheduling, algorithm achieves O(m(log⁡m/log⁡log⁡m)2) approximation ratio.•Moreover, this paper proposes a heuristic algorithm for the flow-level scheduling problem.