Scheduling Coflows for Minimizing the Maximum Completion Time in Heterogeneous Parallel Networks
For data center operators managing heterogeneous networks, this work provides the first polynomial-time approximation algorithm with provable performance bounds for coflow scheduling across multiple switch architectures.
This paper addresses the NP-hard problem of coflow scheduling in heterogeneous parallel networks with multiple network cores, proposing a polynomial-time approximation algorithm to minimize makespan. The algorithm achieves approximation guarantees of 2 for EPS and 4 for not-all-stop OCS when m=2, and 2τ+2 for all-stop OCS when m=2.
Coflow is a prominent network abstraction for modeling communication patterns in data centers. Since coflow scheduling in large-scale data centers is $\mathcal{NP}$-hard, this paper investigates this problem within heterogeneous parallel networks featuring multiple network cores. We propose a polynomial-time approximation algorithm to minimize the makespan (maximum completion time). We consider three distinct switch architectures: Electronic Packet Switches (EPS), not-all-stop Optical Circuit Switches (OCS), and all-stop OCS. Under a deployment where all switches are EPS, the proposed algorithm achieves an approximation guarantee of $\min\left\{τ, 2Nm+1\right\}$, which reduces to $2$ when $m=2$ where $τ$ is the maximum number of flows of each port of switch, $N$ is the number of input/output ports and $m$ is the number of network cores. In environments entirely composed of not-all-stop OCS, the algorithm guarantees an approximation ratio of $2\min\left\{τ, 2Nm+1\right\}$, and $4$ when $m=2$. For setups consisting solely of all-stop OCS, the approximation guarantee becomes $2\min\left\{2τ-1, 2Nm+τ\right\}$, and $2τ+2$ when $m=2$. Furthermore, in a hybrid network architecture, we show that the overall performance guarantee of our algorithm is dominated by the least performant switch architecture in the system.