Cluster schedulers that account for the network, by placing communicating tasks on nearby machines or keeping traffic off oversubscribed switches, report large wins over schedulers that ignore it. Two examples are a 26–36% average job-time reduction for Dally and 10.6% higher training throughput for Arnold. Every one of these wins is measured against a weaker heuristic, never against the best achievable schedule. Nobody knows whether today's network-aware heuristics are within 5% of optimal or within a factor of 3 of it. Theory has the tool that could answer this. An LP relaxation, the integer program with its yes/no placement decisions loosened into fractions, can be solved quickly. Its value is a hard lower bound on what any real schedule can achieve. The theoretical papers that build such relaxations for scheduling and network transfers, however, run no experiments at all.
This note proposes an LP relaxation for scheduling task graphs on a tree-shaped data-center network (servers inside racks inside pods). Data transfers are modeled the way real clusters behave: free when the two tasks share a machine, and charged against the bandwidth of every network tier the transfer crosses when they do not. The relaxation is used in two ways. First, it serves as a per-instance certificate that measures how far production-style heuristics sit from optimal on real cluster traces. Second, it seeds a schedule built by dependent rounding, a randomized way of turning fractions into decisions that never overfills a machine. The certificate is the primary contribution. The rounded scheduler is a test of whether the measured headroom can actually be recovered.
Core Claim
Placement-dependent communication can be captured in a polynomial-size LP. For a two- or three-tier tree topology, this LP is tight enough on realistic workloads to give useful lower bounds. With it, we can state for the first time how much makespan and completion time existing network-aware heuristics leave on the table. If the gap is large and concentrated in congested regimes, rounding the LP should recover a measurable part of it. If the gap is small, that is equally important, because it says the field's remaining gains must come from somewhere other than placement and ordering, for example from the temporal interleaving that CASSINI exploits.
The core modeling device is a separation variable. Let $x_{u,S}$ be the fraction of task $u$ placed inside subtree $S$ of the topology, for example a rack. For a transfer from task $u$ to task $v$ carrying $d_{uv}$ bytes, the fraction of that transfer that must leave $S$ is lower-bounded by
$$s_{uv,S} \ge x_{u,S} - x_{v,S}, \qquad s_{uv,S} \ge x_{v,S} - x_{u,S},$$
and the total $\sum_{(u,v)} d_{uv}\, s_{uv,S}$ is charged against the uplink capacity of $S$ in each time interval. At integral values this is exactly the conditional network task of Data Center Scheduling With Network Tasks: zero cost when co-located, full cost on the crossed links. Time enters through geometrically growing interval-indexed variables rather than fully time-indexed ones, which keeps the LP near-linear in size.
Research Program
Prior work plays three different roles here. The motivation comes from the systems papers. Giroire et al. prove the conditional-network-task problem NP-complete and give G-LIST (a priority list scheduler) and PARTITION (balanced graph partitioning followed by layer-by-layer scheduling). They report ratios "between 1 and 5 relative to the theoretical lower bound". Such a wide band is exactly the symptom we target: we cannot tell whether that band reflects bad schedules or a loose bound. Dally (GPU Cluster Scheduling for Network-Sensitive Deep Learning), Arnold (Efficient Pre-Training of LLMs via Topology-Aware Communication Alignment on More Than 9600 GPUs) and FlexTopo (Topology-aware Preemptive Scheduling for Co-located LLM Workloads) likewise compare only against other heuristics. Arnold solves an exact mixed-integer program for placement but reports no optimality gap at scale. It also models placement only, not ordering.
The theory papers supply the method. Nearly-Linear Time LP Solvers and Rounding Algorithms for Scheduling Problems shows that scheduling LPs with precedence constraints can be solved in near-linear time with multiplicative-weight packing/covering solvers. We reuse this solver design, adding our separation and link-capacity constraints, which are themselves packing constraints. Its machine model has no network at all. Integrality Gap of Time-Indexed Linear Programming Relaxation for Coflow Scheduling proves a worst-case gap of 4 for coflow LPs over a single abstract switch. Scheduling Distributed Clusters of Parallel Machines: Primal-Dual and LP-based Approximation Algorithms gives a 2-approximation for clusters treated as flat machine pools. Neither paper models hierarchical topology or co-location, and neither was ever run. For turning fractions into placements, we use swap or pipage rounding, which moves fractional mass between pairs of variables while keeping their sum fixed. This preserves machine slot counts exactly and preserves marginals, in the style surveyed in Symmetric Randomized Dependent Rounding. Ordering then follows each task's LP-predicted completion point.
Two papers constrain the design. A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint is a warning that asymptotically fast relaxation algorithms can carry constants that make them unusable. We therefore report wall-clock solve times against a commercial LP solver rather than asymptotic bounds. EQUATOR (Equilibrium Computation and Robust Optimization in Zero Sum Games With Submodular Structure) is encouraging precedent. Its relaxation-plus-swap-rounding pipeline carried a 0.39 worst-case guarantee yet landed within 4–8% of optimal in practice. Whether scheduling LPs behave similarly on real traces is exactly what we test.
We build three artifacts. The first is an open LP generator and solver for DAG workloads on configurable leaf-spine trees with oversubscription. The second is a rounding scheduler that plugs into an event-driven simulator. The third is a released benchmark of trace-derived instances, each annotated with its LP bound and, where solvable, its exact optimum. A formal approximation ratio for the rounding is a stretch goal, not the claim.
Baselines
The naive reference is a network-blind list scheduler that orders by longest remaining path and places greedily on any free slot. Giroire et al. show this degrades by "factors of over 50" under congestion. It anchors the scale of the problem.
The strongest existing heuristics for task DAGs with conditional transfers are G-LIST and PARTITION. We reimplement both from their published description and run them on the same Google-trace-derived workflows and topologies as our method. The only reported figure is the 1–5 ratio against their lower bound. Beating them means a lower makespan at equal instance sets, with the gap reported as a fraction of the LP bound.
For GPU job placement, the strongest competitor is Dally, which reports up to 69% makespan improvement (68% average) and 26–36% lower average job time versus Tiresias on SenseTime traces in ArtISt-sim. We run it in the same simulator on the same traces if the artifacts are available, and otherwise in our reimplemented simulator with that substitution stated. Beating it means lower average job time and makespan on identical arrivals.
An Arnold-style exact mixed-integer program, given the same wall-clock budget as our LP-plus-rounding (1 s, 10 s, 60 s), is the most important fair comparison. Arnold's code is not in our file, so we write the formulation ourselves and include its affinity weights. The comparison is scored on schedule quality per second of solver time.
Two ablations isolate the key ingredients. The first drops the separation constraints, giving the flat LP of the near-linear-time paper with network costs added only afterwards. This tests whether modeling co-location inside the relaxation matters. The second replaces dependent rounding with independent per-task coin flips followed by a repair pass. This tests whether exact capacity preservation matters.
Why not just…?
Why not just use the lower bound Giroire et al. already compute? That bound is what produced the uninformative 1–5 band. We report both bounds on every instance. If ours is not substantially tighter, the certificate contribution collapses and we will say so.
Why not just solve the exact integer program, as Arnold does? On small instances we do exactly that, because exact optima are how we calibrate the LP's real gap. At trace scale, with hundreds of tasks across hundreds of machines plus time, an integer program run under a time limit returns a feasible schedule and a bound that is typically the LP root bound or weaker. It therefore cannot certify heuristics better than our LP does, only at higher cost. This baseline is a genuine threat to the scheduler half of the proposal. If time-limited branch-and-bound beats our rounding at equal time, we will report that the LP's value is as a certificate, not as a scheduler.
Why not just tune PARTITION, or add a better graph partitioner? This may well be enough to match our rounding. The certificate is what tells us whether further tuning can possibly help: if PARTITION already sits within a few percent of the LP bound, no rounding scheme can beat it by much. The experiments are designed so that this outcome is informative rather than a failure.
Proposed Experiments
The first check establishes how tight the relaxation is. On a few hundred small instances drawn from Google-trace statistics (tens of tasks, two-tier trees with 2:3 leaf oversubscription as in the Venus/IBM Vela setup of Evaluating the Network Effects of Orchestration Strategies for AI Workloads in Modern Data Centers), we compute exact optima and report the ratio of optimum to LP bound across congestion levels. Fukunaga's worst case of 4 is the theoretical ceiling for the simpler coflow setting. If the empirical gap exceeds roughly 1.3 in congested regimes, we strengthen the LP with tier-wise cut constraints before going further.
The second, and central, measurement is a headroom audit at trace scale. On Google-derived DAG workloads and SenseTime GPU job traces, we report each baseline's makespan and average completion time divided by the LP bound, broken down by communication-to-compute ratio. For ATLAS/Alibaba PAI (ATLAS: Alibaba Dataset and Benchmark for Learning-Augmented Scheduling), the trace has no communication volumes. We attach transfer sizes from the SenseTime model mix and state this clearly as a synthetic overlay. ATLAS's compute-only result, a shortest-predicted-job-first completion ratio of 1.106 against optimum, gives a reference for how much headroom remains once the network is ignored.
The third experiment tests recovery. LP-plus-rounding is compared against G-LIST, PARTITION, Dally and the time-limited integer program at matched solver time. Success is a statistically significant reduction in makespan under high congestion, together with recovery of at least a third of the measured headroom. The two ablations show whether the gain comes from the separation constraints, from dependent rounding, or from neither.
Finally, wall-clock solve time of our multiplicative-weights LP and of a commercial solver is plotted against instance size. The proposal stands if certificates for thousand-task instances arrive in seconds to minutes. It also stands on the audit alone if every heuristic proves to be near the bound, since that result would redirect effort toward temporal interleaving and interference, which a placement-and-ordering LP does not model.
References
- Data Center Scheduling With Network Tasks
- GPU Cluster Scheduling for Network-Sensitive Deep Learning
- Efficient Pre-Training of LLMs via Topology-Aware Communication Alignment on More Than 9600 GPUs
- Topology-aware Preemptive Scheduling for Co-located LLM Workloads
- Nearly-Linear Time LP Solvers and Rounding Algorithms for Scheduling Problems
- Integrality Gap of Time-Indexed Linear Programming Relaxation for Coflow Scheduling
- Scheduling Distributed Clusters of Parallel Machines : Primal-Dual and LP-based Approximation Algorithms
- Symmetric Randomized Dependent Rounding
- A Nearly-Linear Time Algorithm for Submodular Maximization with a Knapsack Constraint
- Equilibrium Computation and Robust Optimization in Zero Sum Games With Submodular Structure
- Evaluating the Network Effects of Orchestration Strategies for AI Workloads in Modern Data Centers
- ATLAS: Alibaba Dataset and Benchmark for Learning-Augmented Scheduling