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

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 $τ$ 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\τ, 3\, 2min\τ, 3\, and 4min\τ, 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 8min\τ, 4\, 16min\τ, 4\, and 32min\τ, 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 4min\τ,3\≤ 12 and 32min\τ,4\≤ 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 $τ$. We also show that the integrality gap of the underlying linear program is at least $2$.