Pith. sign in

REVIEW 2 major objections 5 minor 33 references

Minimum Congestion Routing of Unsplittable Flows in Data-Center Networks

T0 review · 2 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims that unsplittable-flow routing in Clos networks can be guaranteed within 9/5 of optimal congestion offline, while online routing cannot beat 2.

desk verdict A genuine step past the factor-2 barrier in unsplittable Clos routing, with solid lower bounds; one repairable proof gap in the central theorem needs fixing. read the letter →

arxiv 2505.03908 v1 pith:ABG6KTCZ submitted 2025-05-06 cs.NI cs.DScs.PF

Miguel Ferreira , Nirav Atre , Justine Sherry , Michael Dinitz , João Luís Sobrinho This is my paper · ORCID
classification cs.NIcs.DScs.PF MSC 68M1068Q1768W25
keywords minimumcongestionroutingunsplittableflowsClosnetworksapproximationalgorithmsonlinelowerboundsNP-hardnessdata-center
topics P versus NP
open problems P versus NP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tackles a concrete network-engineering question: when each data-center flow must be routed along a single path, how close to the ideal congestion 1 can a routing get? It claims the old factor-2 ceiling is not fundamental. For offline routing in Clos networks with full bisection bandwidth, it gives a polynomial-time algorithm whose worst-case congestion and approximation factor are 9/5, and proves that no polynomial-time algorithm can guarantee better than 3/2 unless P=NP. In the online setting, where flows arrive one at a time, it proves a strict separation: no online algorithm, deterministic or randomized, can approximate within a factor 2. If these results hold, operators can replace today's heuristics with a provable offline guarantee below 2, but cannot hope for the same guarantee when flows must be routed on the fly.

What carries the argument

The load-bearing mechanism is a two-phase threshold algorithm. A lower bound $L$ on the optimal congestion is computed from the largest flow demand and the average total demand at each switch; the algorithm sets $P=\frac{9}{5}L$ and $Q=3$. Phase 1 constructs copies of each input/output switch, assigns flows to copies in decreasing demand order so that three packing properties hold, and routes the selected subset through a link-disjoint matching decomposition. Phase 2 routes every remaining flow in decreasing demand order onto the path with minimum current congestion. The analysis uses properties Q1–Q3: Phase 1 congestion is bounded, every flow above one-third of the optimum is captured in Phase 1, and rejected flows force enough residual load to make the final contradiction stick. The lower-bound arguments rest on two structural gadgets: a cross gadget whose unique congestion-1 routing forces a diagonal assignment of flows, and two prefix-sharing unit-demand sequences whose unique good routings disagree, which the minimax principle converts into a randomized lower bound.

What would settle it

Simulate the proposed algorithm with $P=\frac{9}{5}L$ and $Q=3$ across all small Clos instances (for example $N=2,3$ and $R$ up to 5) and look for a returned routing with congestion strictly above $\frac{9}{5}$. The proof's key step is the per-link reading of Q3; any instance where that per-link bound fails while the sum bound holds would expose the gap. Equivalently, check whether the formal Q3 inequality implies the per-link congestion lower bound used to derive the coefficient $\frac{167}{165}$.

Watch

Extended reading notes

Core claim

The central claim is that minimum congestion routing of unsplittable flows in full-bisection Clos networks admits a 9/5 approximation computable in polynomial time, breaking the factor-2 barrier of the standard two-factor heuristics. The paper proves Theorem 2.1 by a two-phase algorithm: Phase 1 copies each top-of-rack switch, packs flows with large demands into copies so that a matching-based decomposition yields a low-congestion routing, and Phase 2 routes the remaining flows greedily on least-congested paths; the threshold is P=9/5 times a lower bound L on the optimum, with Q=3 separating large from small demands. It further proves that some sets of flows force congestion at least 3/2, that deciding whether congestion 1 is achievable is NP-complete when demands are 1 or 1/2, and hence that no polynomial-time algorithm approximates below 3/2 unless P=NP. Finally, for online routing it proves that every deterministic or randomized algorithm has a unit-demand sequence with congestion at least 2, matching the offline guarantee's worst case and separating the settings.

Load-bearing premise

The 9/5 guarantee stands on reading Lemma 4.2's property Q3 as saying that every individual link incident to a switch that rejects a flow carries more than the baseline load, whereas the lemma's stated inequality only proves the total across that switch's copies exceeds the baseline.

Editorial extensions

If this is right

  • Offline, operators can route unsplittable flows with a provable worst-case congestion of 9/5 instead of 2, without splitting any flow.
  • No polynomial-time offline algorithm can improve the guarantee to below 3/2 unless P=NP, so the remaining gap to close is between 9/5 and 3/2.
  • Online routing is strictly harder: every online algorithm, even randomized, has a unit-demand sequence with congestion 2, so the offline improvement cannot be carried over online without re-routing or batching.
  • For unit-demand flows the offline problem remains easy: a congestion-1 routing is found by matching decomposition, and the 3/2 obstruction appears only once half-unit demands are allowed.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The 9/5-to-3/2 gap is the paper's own open question; a natural next design is a finer threshold or a third phase that could push the two-phase scheme toward 3/2, or a stronger gadget that raises the lower bound.
  • The online lower bound is proven for unit demands, while the paper notes an upper bound of 3 from an unsorted greedy argument for general demands; pinning down the exact online factor for arbitrary demands is an adjacent problem this paper leaves open.
  • The cross-gadget construction isolates exactly the packing constraints that make unsplittable routing hard, so it could serve as a benchmark family for testing practical traffic-engineering heuristics and load balancers.
  • If future transport protocols allow a limited number of split paths per flow, the threshold design suggests a trade-off curve between split path count and achievable congestion, with 9/5 and 3/2 as natural anchor points.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper studies minimum-congestion routing of unsplittable flows in unfolded Clos networks. It claims three main results: (i) an offline polynomial-time algorithm that both guarantees congestion at most 9/5 and approximates the optimum congestion within factor 9/5 (Theorem 2.1, proved as Theorems 4.1 and 4.6); (ii) offline lower bounds showing that some instances have optimum congestion at least 3/2 and that it is NP-hard to approximate within any factor below 3/2 even for demands 1 and 1/2 (Theorems 2.2, 2.3, and Corollary 2.4); and (iii) an online lower bound of 2 for deterministic and randomized algorithms, even with unit demands, giving a strict offline/online separation (Theorems 2.5 and 2.6, proved in Section 6). The offline algorithm routes a demand-dependent subset of flows in a first phase using a Melen--Turner-style matching decomposition and routes the remaining flows greedily in a second phase, with a threshold set to 9/5 times a lower bound L on the optimum.

Significance. If the proofs are correct, the paper's main contribution is substantial: it breaks the factor-2 barrier that was previously the best known worst-case congestion and approximation for unsplittable routing in Clos networks, and it shows a clean separation between offline and online settings. The lower-bound parts of the paper are particularly solid: the cross-gadget construction in Section 5 is elegant, the reduction from 3-edge-coloring in Theorem 5.3 is standard but carefully executed, and the online lower bound in Section 6 correctly uses Yao's principle modulo a notational slip about powers of two. The paper also gives a useful survey of the relationship to the multirate rearrangeability literature. The main risk to the central claim is a gap in the proof of Theorem 4.1 concerning the interpretation of property Q3 in Lemma 4.2; this gap appears repairable from the surrounding properties, but it must be fixed in the written proof.

major comments (2)
  1. [§4.2, Lemma 4.2 and Theorem 4.1] The proof of Theorem 4.1 uses a per-link consequence of property Q3, but Lemma 4.2 only proves an aggregate inequality. Specifically, the final contradiction lower-bounds the total demand on links leaving I_i(f) by C·D + (N−C)(p−1)L, where the term (N−C)(p−1)L is justified only if every non-congested link leaving I_i(f) carries more than (p−1)L. The formal statement of Q3, however, proves only that Σ_{k∈[K]} +d^k_i > (p−1)L, and an aggregate sum does not control an individual link. The gap is repairable: if I_i rejected f at copy x, then copies 1,...,x−1 are full, and in the link-disjoint Phase 1 routing each full copy contributes exactly one flow to every middle switch, so every link I_iM_m carries at least Σ_{k=1}^{x−1} +d^k_i. Using P2 and the rejection inequality, this per-link load is at least S + max{+D^x_i, dem(f)} − +D^1_i > pL − L = (p−1)L, where S = Σ_{k=1}^{x−1} +D^k_i and L ≥ max demand leaving I_i. The manuscript should state this per-link version of Q3 explicitly and use it in Theorem 4.1; as written, the step is a genuine logical gap in the central proof.
  2. [§4.2, Theorem 4.6] The claimed absolute congestion bound of 9/5 is presented only as a 'straightforward generalization' of the proof of Theorem 4.1, with the remark that Claim 4.5 and the replacement of OPT by min{OPT,1} suffice. This is a central advertised result (Theorem 2.1 states congestion at most 9/5), and the modification is not fully written out: the proof of Lemma 4.2, the definition of D, and the final coefficient calculation all need to be checked in the min{OPT,1} variant. I ask the authors to include the complete modified proof, or at least the modified statements of Lemma 4.2 and the key inequalities, so that the reader can verify that the parameter choice 9/5 survives the change.
minor comments (5)
  1. [§4.2, proof of Theorem 4.1] The line 'By setting p ≜ 9/5 and q ≜ 1/3' should read q ≜ 3; the value q=1/3 is inconsistent with the theorem statement and makes expressions such as (p − 1/q) meaningless.
  2. [§6.2, Theorem 6.3 and Corollary 6.6] The number of sequences is 2^S, not 2S, and the notation '2S' is used both as the exponent and as a denominator; the expected congestion should be 2 − 1/2^S. Also, Theorem 6.3 uses S=⌊R/3⌋ while Corollary 6.6 uses S=⌈R/3⌉; the two should be reconciled.
  3. [§4.2, proof of Lemma 4.2, property Q3] In the last step of the Q3 proof, the inequality +D^1_i ≤ L is attributed to P3, but it follows from the definition of L as the maximum demand leaving I_i; the citation should be corrected.
  4. [§4.1] The sentence 'Let 1/Q be a flow demand, p be an approximation factor' is confusing because the parameter used in the algorithm and analysis is q, not Q; please clarify whether Q and q are the same parameter and use one symbol consistently.
  5. [Throughout] There are several typographical slips: 'It not hard to show' should be 'It is not hard to show', 'plausive' should be 'plausible', and the reference to 'John Hopkins University' should be 'Johns Hopkins University'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the offline and online bounds are proven from independent lower bounds and external classical theorems, with no fitted parameter renamed as a prediction.

full rationale

The derivation chain is self-contained in the sense required for this pass. The algorithm's threshold P is set to (9/5)*L, where L is an explicit demand-based lower bound on OPT (Section 4.2), not a quantity derived from the algorithm's own output; OPT appears only as a benchmark in the analysis. Phase 1 relies on the external bipartite matching decomposition theorem (Theorem 3.1, citing Hwang 1983 and Lovász–Plummer 2009), Phase 2 is the standard Sorted Greedy argument, and the lower bounds use the cross gadget with elementary counting plus the NP-completeness of 3-edge-coloring (Karp). No self-citation is load-bearing; the paper's citations are to prior independent work. Two issues noted in the manuscript are correctness risks, not circularity: Section 3.2 omits the 'easy proof' of the reduction of arbitrary demands to the hose-model assumption, and the proof of Theorem 4.1 uses the per-link reading of Lemma 4.2(Q3) although the lemma states only an aggregate sum; the aggregate bound does not by itself control individual links. That is a repairable proof gap, not an instance of deriving a conclusion from an input that already contains it. There is no fitted parameter, no uniqueness theorem imported from the authors, and no ansatz smuggled in via self-citation.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The central claim rests on two manually chosen constants (p = 9/5, q = 3), standard combinatorial theorems, and the hose-model input assumption. No invented entities are introduced. The constants are not fitted to data but are tuned to make the proof's final inequality exactly exceed 1, which is a hand-tuning of the analysis rather than a free parameter in the usual sense.

free parameters (2)
  • p = 9/5
    Approximation and congestion factor chosen by hand; the proof's contradiction requires p >= 3/2 and the coefficient 167/165 > 1 relies on p = 9/5.
  • q = 3
    Demand threshold (flows with demand > OPT/q go to Phase 1). The proof of Q2 and the final algebra use q = 3, and require p >= sum_{k=1}^{q-1} 1/k.
assumptions (4)
  • standard math Every set of flows with at most one flow per source and per destination admits a link-disjoint routing in a Clos network, findable in polynomial time (Theorem 3.1, citing Hwang 1983 and Lovasz-Plummer 2009).
    Used in Phase 1.b to route the subset F1 in the expanded network; the paper applies it without proof.
  • domain assumption Total demand leaving each source and entering each destination is at most 1 (hose model).
    Stated in Section 3.2 as an assumption on the input; it ensures a splittable routing of congestion 1 exists and is used in Claim 4.5 and in the lower-bound constructions.
  • standard math Bipartite multigraphs with maximum degree N have an N-edge-coloring (König's line coloring theorem), used implicitly in the matching decomposition.
    The link-disjoint routing in Theorem 3.1 is based on this decomposition; the paper relies on it when routing F1.
  • standard math The 3-edge coloring problem for graphs of maximum degree 3 is NP-complete (Karp 1972).
    Used in the reduction for Theorem 5.3 (NP-completeness of deciding congestion at most 1).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Minimum Congestion Routing of Unsplittable Flows in Data-Center Networks." pith.science (2026). https://pith.science/paper/ABG6KTCZ

@misc{pith2026250503908,
  author       = {Pith},
  title        = {Pith review of: Minimum Congestion Routing of Unsplittable Flows in Data-Center Networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ABG6KTCZ}},
  note         = {Machine review of arXiv:2505.03908}
}
abstract

Millions of flows are routed concurrently through a modern data-center. These networks are often built as Clos topologies, and flow demands are constrained only by the link capacities at the ingress and egress points. The minimum congestion routing problem seeks to route a set of flows through a data center while minimizing the maximum flow demand on any link. This is easily achieved by splitting flow demands along all available paths. However, arbitrary flow splitting is unrealistic. Instead, network operators rely on heuristics for routing unsplittable flows, the best of which results in a worst-case congestion of $2$ (twice the uniform link capacities). But is $2$ the lowest possible congestion? If not, can an efficient routing algorithm attain congestion below $2$? Guided by these questions, we investigate the minimum congestion routing problem in Clos networks with unsplittable flows. First, we show that for some sets of flows the minimum congestion is at least $\nicefrac{3}{2}$, and that it is $NP$-hard to approximate a minimum congestion routing by a factor less than $\nicefrac{3}{2}$. Second, addressing the motivating questions directly, we present a polynomial-time algorithm that guarantees a congestion of at most $\nicefrac{9}{5}$ for any set of flows, while also providing a $\nicefrac{9}{5}$ approximation of a minimum congestion routing. Last, shifting to the online setting, we demonstrate that no online algorithm (even randomized) can approximate a minimum congestion routing by a factor less than $2$, providing a strict separation between the online and the offline setting.

Figures

Figures reproduced from arXiv: 2505.03908 by the authors.

Figure 1
Figure 1. The minimum congestion routing problem in Clos networks. Circles symbolize servers, and squares symbolize switches. Lines symbolize flows from source to destination. Flows are represented without and with routing, with middle switches omitted from the former. Figure 1a shows a set of flows in a Clos network with 2 middle switches and 3 input (output) ToR switches: flows (I1, O1), (I2, O1), and (I3, O2) have demand 1… view at source ↗
Figure 2
Figure 2. Worst-case flows for the Melen-Turner algorithm. Figure 2a shows a set of flows in a Clos network with N middle switches composed of two types of flows: one type 1 flow with demand 1 (in blue) and (N−1)/ϵ type 2 flows each with demand ϵ (in orange), for some small ϵ > 0 (only the first input and output switches are shown). The minimum congestion routing has congestion 1, with the type 1 flow assigned to some middle … view at source ↗
Figure 3
Figure 3. The cross gadget underlying Theorems 2.2 and 2.3 in a Clos network with 3 middle switches. Theorem 2.1. There is a polynomial-time algorithm that returns a routing with congestion at most 9/5 and approximates a minimum congestion routing by a factor at most 9/5. Offline: Lower Bounds on Congestion and Approximation. We present lower bounds that show that, despite the special structure of Clos networks, a minimum con… view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: The sequences of flows underlying Theorem 2.5 in a Clos network with 3 middle switches, [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]
Figure 5
Figure 5. Figure 5: Algorithm 1 with Q = 3 and P = 5/3 for a set of flows in the Clos network C4,3. Flow f1 has demand 1 (in blue), flows f2 through f5 have demand 1/2 (in green), and flows f6 through f9 have demand 1/4 (in orange). While the subset of the flows in the new instance satisf…
Figure 6
Figure 6. Figure 6: The cross gadget of size N = 3. 5.1 Limits to Congestion If all flows have demand 1, in which case there is at most one flow per source and per destination, then for every set of flows there is a routing with congestion 1. (This is a corollary of Theorem 3.1.) In contr…
Figure 7
Figure 7. Figure 7: The set of flows underlying the proof of Theorem 5.2 for N = 3 and R = 4. • The type 3 flow is assigned to MN . Every edge except for MN ON is traversed by at most one flow, and thus has congestion at most 1. Edge MN ON is traversed by both the type 2 flow leaving I1 a…
Figure 8
Figure 8. Figure 8: The reduction underlying the proof of Theorem 5.3 for a particular input graph. The vertex flows in the 2’nd, 3’rd, and 4’th vertex blocks are not shown. The coloring of the different types of flows in F(G) is unrelated to the edge coloring in G. If there is a routing …
Figure 9
Figure 9. Figure 9: The sequences of flows underlying Theorem 6.1 for N = 4. of one subsequence followed by another, with the sequences agreeing on the prefix, X1 = Y1, and disagreeing on suffix, X2 ̸= Y2. The arrival order among the flows within a subsequence is arbitrary, and each flow …

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

33 extracted references · 32 canonical work pages

  1. [1]

    CONGA: Distributed Congestion-Aware Load Balancing for Data Centers

    Mohammad Alizadeh, Tom Edsall, Sarang Dharmapurikar, Ramanan Vaidyanathan, Kevin Chu, Andy Fingerhut, Vinh The Lam, Francis Matus, Rong Pan, Navindra Yadav, and George Varghese. CONGA: Distributed Congestion-Aware Load Balancing for Data Centers . ACM SIGCOMM Computer Communication Review , 44(4):503–514, 2014

    work page 2014

  2. [2]

    A Scalable, Commodity Data Center Network Architecture

    Mohammad Al-Fares, Alexander Loukissas, and Amin Vahdat. A Scalable, Commodity Data Center Network Architecture . ACM SIGCOMM Computer Communication Review , 38(4):63--74, 2008

    work page 2008

  3. [3]

    Hedera: Dynamic Flow Scheduling for Data Center Networks

    Mohammad Al-Fares, Sivasankar Radhakrishnan, Barath Raghavan, Nelson Huang, and Amin Vahdat. Hedera: Dynamic Flow Scheduling for Data Center Networks . In Proceedings of the USENIX Conference on Networked Systems Design and Implementation , pages 89--92, 2010

    work page 2010

  4. [4]

    Network Traffic Characteristics of Data Centers in the Wild

    Theophilus Benson, Aditya Akella, and David A Maltz. Network Traffic Characteristics of Data Centers in the Wild . In Proceedings of the ACM Internet Measurement Conference , pages 267--280, 2010

    work page 2010

  5. [5]

    Intel® Omni-Path Architecture: Enabling Scalable, High Performance Fabrics

    Mark Birrittella, Mark Debbage, Ram Huggahalli, James Kunz, Tom Lovett, Todd Rimmer, Keith Underwood, and Robert Zak. Intel® Omni-Path Architecture: Enabling Scalable, High Performance Fabrics . In Proceedings of the IEEE Symposium on High-Performance Interconnects , pages 1--9, 2015

    work page 2015

  6. [6]

    Approximation Algorithms for the Unsplittable Flow Problem

    Amit Chakrabarti, Chandra Chekuri, Anupam Gupta, and Amit Kumar. Approximation Algorithms for the Unsplittable Flow Problem . Algorithmica , 47(1):53--78, 2007

    work page 2007

  7. [7]

    Hardness of Routing with Congestion in Directed Graphs

    Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, and Kunal Talwar. Hardness of Routing with Congestion in Directed Graphs . In Proceedings of the ACM Symposium on Theory of Computing , page 165–178, 2007

    work page 2007

  8. [8]

    Traffic Engineering With Equal-Cost-MultiPath: An Algorithmic Perspective

    Marco Chiesa, Guy Kindler, and Michael Schapira. Traffic Engineering With Equal-Cost-MultiPath: An Algorithmic Perspective . IEEE/ACM Transactions on Networking , 25(2):779–792, 2017

    work page 2017

Show all 33 references
  1. [9]

    A Study of Non-Blocking Switching Networks

    Charles Clos. A Study of Non-Blocking Switching Networks . The Bell System Technical Journal , 32(2):406--424, 1953

    1953

  2. [10]

    DevoFlow: scaling flow management for high-performance networks

    Andrew Curtis, Jeffrey Mogul, Jean Tourrilhes, Praveen Yalagandula, Puneet Sharma, and Sujata Banerjee. DevoFlow: scaling flow management for high-performance networks . ACM SIGCOMM Computer Communication Review , 41(4):254–265, 2011

    2011

  3. [11]

    RFC 4338: Transmission of IPv6, IPv4, and Address Resolution Protocol (ARP) Packets over Fibre Channel , 2006

    Claudio Desanti, Craig Carlson, and Robert Nixon. RFC 4338: Transmission of IPv6, IPv4, and Address Resolution Protocol (ARP) Packets over Fibre Channel , 2006

    2006

  4. [12]

    A Flexible Model for Resource Management in Virtual Private Networks

    Nick Duffield, Pawan Goyal, Albert Greenberg, Partho Mishra, Kadangode Ramakrishnan, and Jacobus van der Merive. A Flexible Model for Resource Management in Virtual Private Networks . ACM SIGCOMM Computer Communication Review , 29(4):95–108, 1999

    1999

  5. [13]

    IEEE Std 802.3-2022 (Revision of IEEE Std 802.3-2018) , pages 1--7025, 2022

    IEEE Standard for Ethernet . IEEE Std 802.3-2022 (Revision of IEEE Std 802.3-2018) , pages 1--7025, 2022

    2022

  6. [14]

    VL2: A Scalable and Flexible Data Center Network

    Albert Greenberg, James Hamilton, Navendu Jain, Srikanth Kandula, Changhoon Kim, Parantap Lahiri, David Maltz, Parveen Patel, and Sudipta Sengupta. VL2: A Scalable and Flexible Data Center Network . ACM SIGCOMM Computer Communication Review , 39(4):51–62, 2009

    2009

  7. [15]

    RDMA Over Ethernet for Distributed Training at Meta Scale

    Adithya Gangidi, Rui Miao, Shengbao Zheng, Sai Jayesh Bondu, Guilherme Goes, Hany Morsy, Rohit Puri, Mohammad Riftadi, Ashmitha Jeevaraj Shetty, and Jingyi Yang. RDMA Over Ethernet for Distributed Training at Meta Scale . In Proceedings of the ACM SIGCOMM Conference , pages 57...

    2024

  8. [16]

    Contra: A Programmable System for Performance-Aware Routing

    Kuo-Feng Hsu, Ryan Beckett, Ang Chen, Jennifer Rexford, and David Walker. Contra: A Programmable System for Performance-Aware Routing . In Proceedings of the USENIX Symposium on Networked Systems Design and Implementation , pages 701--721, 2020

    2020

  9. [17]

    Control Algorithms for Rearrangeable Clos Networks

    Frank Hwang. Control Algorithms for Rearrangeable Clos Networks . IEEE Transactions on Communications , 31(8):952--954, 1983

    1983

  10. [18]

    Reducibility Among Combinatorial Problems

    Richard Karp. Reducibility Among Combinatorial Problems . In Proceedings of a Symposium on the Complexity of Computer Computations , page 85–103, 1972

    1972

  11. [19]

    Improved Bounds for the Unsplittable Flow Problem

    Petr Kolman and Christian Scheideler. Improved Bounds for the Unsplittable Flow Problem . Journal of Algorithms , 61(1):20--44, 2006

    2006

  12. [20]

    On Weighted Bipartite Edge Coloring

    Arindam Khan and Mohit Singh. On Weighted Bipartite Edge Coloring . In Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science , 2015

    2015

  13. [21]

    Matching Theory

    László Lov \'a sz and Michael Plummer. Matching Theory . American Mathematical Society, 2009

    2009

  14. [22]

    Randomized Algorithms

    Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms . Cambridge University Press, 1995

    1995

  15. [23]

    Nonblocking Multirate Networks

    Riccardo Melen and Jonathan Turner. Nonblocking Multirate Networks . SIAM Journal on Computing , 18(2):301--313, 1989

    1989

  16. [24]

    A Throughput-Centric View of the Performance of Datacenter Topologies

    Pooria Namyar, Sucha Supittayapornpong, Mingyang Zhang, Minlan Yu, and Ramesh Govindan. A Throughput-Centric View of the Performance of Datacenter Topologies . In Proceedings of the ACM SIGCOMM Conference , page 349–369, 2021

    2021

  17. [25]

    Multirate Rearrangeable Clos networks and a Generalized Edge-Coloring Problem on Bipartite Graphs

    Hung Ngo and Van Vu. Multirate Rearrangeable Clos networks and a Generalized Edge-Coloring Problem on Bipartite Graphs . SIAM Journal on Computing , 32(4):1040--1049, 2003

    2003

  18. [26]

    An Introduction to the Infiniband Architecture

    Gregory Pfister. An Introduction to the Infiniband Architecture . High Performance Mass Storage and Parallel I/O , 42(617--632), 2001

    2001

  19. [27]

    PLB: Congestion Signals are Simple and Effective for Network Load Balancing

    Mubashir Qureshi, Yuchung Cheng, Qianwen Yin, Qiaobin Fu, Gautam Kumar, Masoud Moshref, Junhua Yan, Van Jacobson, David Wetherall, and Abdul Kabbani. PLB: Congestion Signals are Simple and Effective for Network Load Balancing . In Proceedings of the ACM SIGCOMM Conference , pa...

    2022

  20. [28]

    Alibaba HPN: A Data Center Network for Large Language Model Training

    Kun Qian, Yongqing Xi, Jiamin Cao, Jiaqi Gao, Yichi Xu, Yu Guan, Binzhang Fu, Xuemei Shi, Fangbo Zhu, and Rui Miao. Alibaba HPN: A Data Center Network for Large Language Model Training . In Proceedings of the ACM SIGCOMM Conference , pages 691--706, 2024

    2024

  21. [29]

    Randomized Rounding: A Technique for Provably Good Algorithms and Algorithmic Proofs

    Prabhakar Raghavan and Clark Tompson. Randomized Rounding: A Technique for Provably Good Algorithms and Algorithmic Proofs . Combinatorica , 7(4):365--374, 1987

    1987

  22. [30]

    Inside the Social Network's (Datacenter) Network

    Arjun Roy, Hongyi Zeng, Jasmeet Bagga, George Porter, and Alex Snoeren. Inside the Social Network's (Datacenter) Network . ACM SIGCOMM Computer Communication Review , 45(4):123–137, 2015

    2015

  23. [31]

    High Throughput Data Center Topology Design

    Ankit Singla, Philip Brighten Godfrey, and Alexandra Kolla. High Throughput Data Center Topology Design . In Proceedings of the USENIX Symposium on Networked Systems Design and Implementation , pages 29--41, 2014

    2014

  24. [32]

    Jupiter Rising: A Decade of Clos Topologies and Centralized Control in Google's Datacenter Network

    Arjun Singh, Joon Ong, Amit Agarwal, Glen Anderson, Ashby Armistead, Roy Bannon, Seb Boving, Gaurav Desai, Bob Felderman, Paulie Germano, Anand Kanagala, Jeff Provost, Jason Simmons, Eiichi Tanda, Jim Wanderer, Urs H\" o lzle, Stephen Stuart, and Amin Vahdat. Jupiter Rising: A...

    2015

  25. [33]

    Probabilistic Computations: Towards a Unified Measure of Complexity

    Andrew Yao. Probabilistic Computations: Towards a Unified Measure of Complexity . In Proceedings of the IEEE Symposium on Foundations of Computer Science , pages 222--227, 1977

    1977

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.