Skip to content
Preprint

Constant-Factor Approximation for Non-Splitting Coflow Scheduling in Heterogeneous Parallel Networks via Iterative Relaxation

Oct 2026 · 0 citations · 35 references
Computer Science

Abstract

Coflows capture the collective communication requirements of data-parallel applications, and scheduling them well is essential to the performance of modern data centers. We study non-splitting coflow scheduling in a heterogeneous parallel network whose $m$ network cores may be Electronic Packet Switches (EPS), not-all-stop Optical Circuit Switches (OCS), or all-stop OCS, where every flow must be transmitted entirely through a single core. Previous approximation algorithms for this setting have guarantees that grow linearly with the number of cores $m$ or with the maximum flow degree $\tau$ of a port, and therefore become weak as data centers deploy more cores. The source of this dependence is the rounding step: rounding each flow to the core holding its largest fractional value can inflate the load of a port by a factor of $m$. We replace this step with an iterative relaxation rounding scheme that handles the input-port and output-port capacity constraints simultaneously. For minimizing the makespan, this yields approximation ratios of $\min\{\tau, 3\}$, $2\min\{\tau, 3\}$, and $4\min\{\tau, 3\}$ for pure EPS, pure not-all-stop OCS, and pure all-stop OCS networks, respectively. For minimizing the total weighted coflow completion time, we obtain approximation ratios of $8\min\{\tau, 4\}$, $16\min\{\tau, 4\}$, and $32\min\{\tau, 4\}$ for the same three architectures. In a hybrid network, the guarantee is governed by the weakest architecture present, so the overall ratios are at most $4\min\{\tau,3\}\le 12$ and $32\min\{\tau,4\}\le 128$, respectively. Unlike all previous guarantees for non-splitting coflow scheduling in heterogeneous parallel networks, these bounds are absolute constants that do not grow with the number of cores $m$ or with the flow degree $\tau$. We also show that the integrality gap of the underlying linear program is at least $2$.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.