CS Paper Radar

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

Chi-Yeh Chen

cs.DS ·submitted 2026-10-29 08:03 UTC · v2

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

Closest papers

Nearest neighbours by meaning across the whole index.

QPS-ToR: A Parallel Iterative Switching Algorithm for Reconfigurable Optical Datacenter Switching

cs.NI ·2026-09-08 ·Dongzhao Song, Qianru Yu, Jun Xu
similarity 0.62
Abstract

Reconfigurable optical data center networks (RODCNs) have emerged as a promising solution for scaling DCN capacity, yet their scheduling mechanisms remain a performance bottleneck: traffic-oblivious schemes inherently limit throughput, while the state-of-the-art traffic-aware scheme, NegotiaToR, uses single-iteration iSLIP as its scheduling engine, which limits throughput to around 60% and treats all source-destination pairs with equal priority regardless of queue length. We propose QPS-ToR, which replaces NegotiaToR's scheduling logic with SW-QPS, a sliding-window algorithm originally proposed for crossbar scheduling that achieves around 90% throughput with a single low-complexity iteration. QPS-ToR operates within NegotiaToR's existing workflow, requiring only a revision of the scheduling cycle from three-step Request-Grant-Accept (RGA) to two-step Request-Grant (RG) with a sliding window mechanism. In flow-level simulations with 128 ToRs under realistic datacenter workloads, QPS-ToR achieves up to 36% higher throughput and 82% lower flow completion time (FCT) compared to NegotiaToR, and consistently outperforms RotorNet, a representative traffic-oblivious scheme, on the parallel network topology.

0.18

Improved Approximations for Coflow Scheduling via Iterated Rounding and Stable Matchings

cs.DS ·2026-10-12 ·Mikhail Cherniavskii, Arseni Fedorovich, Mikhail Koshelev, Andrey Kupavskii, Stanislav Moiseev +2 more
similarity 0.58
Abstract

We study Coflow Scheduling, introduced by Chowdhury, Zhong, and Stoica (2014). We give deterministic polynomial-time algorithms achieving a $2.77$-approximation without release dates and a $3.17$-approximation with integer release dates. These improve the $3.42$ and $4.36$ guarantees of Rohwedder and Schnaars (2025). Our approach combines two ideas: (1) a novel iterated rounding scheme, and (2) Galvin's list edge coloring method, which is based on the Gale--Shapley stable matching algorithm.

0.25

Flux: Optimal Scheduling of Optical Circuit Switches for LLM Training

cs.NI cs.DC ·2026-09-22 ·Arno Troch, Seyyidahmed Lahmer, Abubakr Nada, Jeroen Famaey, Michael Peeters
position similarity 0.58
Abstract

Optical Circuit Switching (OCS) offers high bandwidth density and energy efficiency for LLM training, but incurs a non-negligible reconfiguration delay. Prior work typically schedules optical circuit switches independently of compute, using aggregate traffic demand to determine which circuits to provision and when. We argue that this separation creates a fundamental inefficiency: reconfigurations that ignore the compute timeline can stall communication, resulting in low circuit utilization and large buffer requirements. In this paper, we present Flux, a scheduler that optimally schedules optical circuit switches based on the structure of the entire workload. Flux remains effective across a wide range of switching speeds by reusing circuits and amortizing reconfiguration delay behind compute and communication. We show that Flux reduces training iteration time by up to $10\times$ and peak NIC buffer requirements by more than three orders of magnitude compared to traditional periodic schedulers.

0.38

Opportunistic Optical Link Scheduling in the Scalable Matching Model

cs.NI ·2026-10-27 ·Marcos T. Henriques, Olga Goussevskaia
similarity 0.57
Abstract

The Scalable Matching Model (SMM) is a useful abstraction for reconfigurable datacenter networks. In SMM, a set of $n$ (Top-of-Rack) electrical packet switches is connected via a set of optical circuit switches (OCS), each realizing a $p \times p$ matching, where $p$ is the number of ports per switch. In the case when $p \ll n$, bounded-degree networks utilize only a small portion of the OCS infrastructure at each point in time, especially when traffic patterns are skewed and bursty. In this work, we propose the Opportunistic Optical Link Scheduling (OOLS), a set of lightweight OCS link scheduling routines, designed to augment bounded-degree reconfigurable network topologies by leveraging idle OCS resources. We evaluate the performance of OOLS in the SMM through simulations, using synthetic and real-world data-center workloads. Our simulation results show that OOLS substantially improves performance, lowering communication costs and boosting throughput.

0.14

When Does Distributed AI Inference Need More Wide-Area Bandwidth? A Co-Design Evaluation of Optical, Packet, and Software Levers

cs.DC cs.NI ·2026-08-15 ·Prasanna C
similarity 0.55
Abstract · 10 pages, 4 figures, 3 tables

Wide-area bandwidth per unit of GPU compute falls every hardware generation: in compute-intensity-ratio terms (CIR, bytes per FLOP), the gap between on-package memory and the conventional WAN is four to five orders of magnitude, widening at roughly 12-19% per year. Position papers - including our own - argued this makes elastic optical wide-area capacity necessary for cross-site AI inference. Reviewers correctly objected that such arguments show more bandwidth helps, not that it beats the alternatives: KV recomputation, cache compression, locality-aware routing, scheduling, or an overprovisioned packet backbone. This paper does the comparison. We derive a workload model predicting when moving inference state across sites beats recomputing it - a context-independent crossover at 74-111 Gbps per stream for a 70B multi-head-attention model, falling to 9-14 Gbps under grouped-query attention at 1/8 KV heads - and quantify five sensitivity axes: context length, attention architecture, queueing, agentic compounding, and loss/jitter-induced bandwidth collapse. On economics: at list GPU prices recomputation is cheaper; transfer wins when GPU scarcity and KV reuse multiply effective GPU cost by roughly 5-20x, and modern attention moves the breakeven an order of magnitude in transfer's favour. We position the network levers correctly rather than adversarially: packet networks allocate lit capacity at millisecond timescales; optical fungibility changes how much capacity is lit, at minute timescales, substituting for overprovisioning economically rather than functionally. Finally we specify a ten-metric measurement plan on a three-site production-fibre testbed, framed as an open ecosystem exercise: no single company can - or should - assemble this evidence alone. Every claim is bounded by the regime in which it holds; several findings weaken the naive version of our own thesis, and we state them.

0.10

Pipelining vs. Combining in Aggregation Tasks

cs.DC cs.DS ·2026-10-22 ·Gabriel Marques Domingues, Claire Mathieu, Boaz Patt-Shamir
similarity 0.54
Abstract · 22 pages; 7 figures

We study the aggregation task (convergecast) in networks in the case that the values to be aggregated do not fit in a single message. We assume that every node starts with an input value, and there is an aggregation operator that is commutative, associative, and length-preserving, i.e., the result of aggregating two values has the same length as each of the input values. Since values do not fit in a message, they are transferred in a ``train'' of pipelined messages, which must be terminated whenever we want to aggregate values. The goal is to minimize the makespan time of aggregating all values. We present general lower bounds on the problem and optimal algorithms for several prevalent parallel computing architectures, including the hypercube and complete bipartite graphs, under both the splittable and unsplittable flows models. We also present an $O(\log n)$ approximation for general graphs in the unsplittable flows model.

0.40

Workload-Static Optical Circuit Switching For Scalable LLM Inference Decode

cs.DC cs.AIcs.ARcs.NI ·2026-11-03 ·Maximilian Thürmer, Nicolas Scotto di Perto, Eloise Stein, Natanijel Vasic, Mikaeil Bagherli +4 more
similarity 0.54
Abstract · 39 pages, 10 main text, 29 appendix, 28 figures

LLM inference decode executes fine-grained collectives whose latency directly limits per-user interactivity, yet scale-up fabrics are still built from electronic packet switches designed for training. We observe that, for a given model deployment and parallelization, the communication structure of decode is fixed, and propose workload-static optical circuit switching (OCS): circuits are configured once per deployment, co-designed with model parallelism and with topology-aware collective schedules that turn spare accelerator ports into fewer communication phases or higher bandwidth. We evaluate this design with GXNET, a graph-based workload emulator coupled to analytical and flit-level network models grounded in hardware measurements. In a 576-accelerator scale-up domain serving 5T-parameter MoE models with up to 5M tokens of context, all-OCS fabrics improve interactivity by up to 65% and energy efficiency by up to 119% over 4:1 oversubscribed packet-switched fabrics.

0.25

A Family of Well-Behaved Multiflow Instances

cs.DS cs.DM ·2026-11-02 ·Joseph Poremba, F. Bruce Shepherd
published similarity 0.53
Abstract · To appear in SOSA 2027. 10 pages, 2 figures

We introduce a family of cut-sufficient instances for undirected multiflow that generalizes single-source planar and fully-planar instances. We also show the family has an additive $6 d_{\max}$ error for converting a fractional flow into an unsplittable one.

0.35