Non-Splitting Coflow Scheduling with Provable Guarantees in Heterogeneous Parallel Networks

Abstract

As a prominent network abstraction, coflow models efficiently capture communication patterns in data centers. Since coflow scheduling in large-scale data centers is $\mathcal{NP}$-hard, the existing literature has predominantly focused on limited environments with $m=2$ network cores, relying on flow splitting, which introduces substantial operational overhead. Crucially, no approximation algorithm with provable performance guarantees has been proposed for the more practical, non-splitting coflow scheduling problem, even for the $m=2$ case, let alone for general hybrid architectures. To bridge this critical gap, this paper investigates the non-splitting problem within a hybrid, heterogeneous parallel network featuring multiple network cores ($m\ge 2$) composed of Electronic Packet Switches (EPS), not-all-stop Optical Circuit Switches (OCS), and all-stop OCS. We propose three unified polynomial-time approximation algorithms that minimize the makespan and the total weighted coflow completion time across this hybrid environment without incurring any splitting overhead. Let $\ddot{I}„$ denote the maximum flow degree across all ports in the network, and let $m$ be the number of network cores. To minimize the makespan, our algorithm achieves an approximation ratio of $2\min \left\{2\ddot{I}„-1,m+\ddot{I}„-1\right\}$ in the hybrid architecture. To minimize the total weighted coflow completion time, our algorithm achieves an approximation ratio of $16\min \left\{2\ddot{I}„-1,2m+\ddot{I}„-1\right\}$ in the hybrid architecture. Moreover, we characterize the approximation ratios of our algorithm under different architectural combinations.