1. Scheduling coflows for minimizing the total weighted completion time in heterogeneous parallel networks.
- Author
-
Chen, Chi-Yeh
- Subjects
- *
APPROXIMATION algorithms , *HEURISTIC algorithms , *SCHEDULING , *SERVER farms (Computer network management) , *COMMUNICATION patterns , *DATA transmission systems - Abstract
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. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF