pith. machine review for the scientific record. sign in

arxiv: 2605.04699 · v1 · submitted 2026-05-06 · 💻 cs.NI · cs.DM

Recognition: unknown

A Separation Between Optimal Demand-Oblivious and Demand-Aware Network Throughput

Chen Avin, Matthias Bentert, Stefan Schmid

Pith reviewed 2026-05-08 16:41 UTC · model grok-4.3

classification 💻 cs.NI cs.DM
keywords demand-aware networksnetwork throughputdemand-obliviousreconfigurable topologyrouting modelsNP-hardnessdatacenter interconnects
0
0 comments X

The pith

Demand-aware network topologies achieve at least 5/8 asymptotic throughput, outperforming the roughly 1/2 limit of demand-oblivious topologies.

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

The paper studies how much faster data can move across a network when the topology is allowed to adapt to the specific communication demands between nodes. It defines four combinations of throughput measures and routing rules to compare adaptive networks against fixed ones. The central finding is that adaptation yields a strictly better guaranteed performance even against the worst possible demand pattern. This matters for datacenters that can use reconfigurable optical links to reshape their interconnects on the fly.

Core claim

The central claim is a separation for the classic throughput definition: by choosing a topology that matches the demand, the achievable throughput asymptotically approaches at least 5/8, whereas demand-oblivious topologies are bounded by n/(2n-1) which approaches 1/2. The same separation holds under both direct and general routing. In addition, computing the demand-aware weak throughput is NP-hard while the direct variants admit polynomial-time algorithms.

What carries the argument

Classic throughput under demand-aware topology selection, contrasted with demand-oblivious performance, across direct (single-hop) and general (multi-hop) routing models.

If this is right

  • Worst-case throughput rises from approximately 1/2 to at least 5/8 once topologies may adapt to demands.
  • Direct-routing optimal topologies can be found efficiently in polynomial time.
  • Weak-throughput optimization remains NP-hard, so practical solvers must rely on heuristics or approximations.
  • The performance gap between adaptive and fixed topologies persists as the network grows.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Datacenter operators could use these bounds to decide when reconfigurable hardware justifies its cost.
  • Similar separation arguments may apply to other adaptive systems such as wireless or software-defined networks.
  • The NP-hardness result suggests studying approximation algorithms or restricted demand classes for faster practical deployment.

Load-bearing premise

Any desired topology can be realized exactly to serve the given demand matrix without limits on ports or reconfiguration speed.

What would settle it

A family of demand matrices on n nodes for which the maximum classic throughput achievable by any demand-aware topology stays below 5/8 - epsilon for large n would disprove the lower bound.

Figures

Figures reproduced from arXiv: 2605.04699 by Chen Avin, Matthias Bentert, Stefan Schmid.

Figure 1
Figure 1. Figure 1: Relations of different demand-aware throughput notions. An arrow from a view at source ↗
Figure 2
Figure 2. Figure 2: The directed 3-regular graphs optimizing the throughput and the weak direct view at source ↗
Figure 3
Figure 3. Figure 3: An example of our approach for the second stage for view at source ↗
Figure 4
Figure 4. Figure 4: The four different vertex-labeled directed 3-regular graphs with two vertices. view at source ↗
Figure 5
Figure 5. Figure 5: Repetition of Figure 4. The four different directed 3-regular graphs with two view at source ↗
Figure 6
Figure 6. Figure 6: The top left shows an input demand matrix view at source ↗
Figure 7
Figure 7. Figure 7: A graphical representation of the demand matrix constructed in the proof of view at source ↗
read the original abstract

The performance of distributed applications often critically depends on the interconnecting network or more specifically on its throughput: how fast data can be carried across a network. Over the last years, great progress has been made in understanding demand-oblivious throughput: how fast a given demand matrix describing pairwise communication requirements can be served on a given network. However, surprisingly little is known today about the achievable demand-aware throughput: the throughput on a network topology which can be optimized toward the demand. Such demand-aware networks have recently gained popularity in datacenters and are enabled by emerging reconfigurable optical technologies. In this paper, we are interested in both the achievable demand-aware throughput bounds as well as in the computational complexity of finding a throughput-optimizing network topology. We take a systematic approach and investigate four variants of demand-aware throughput: we analyze, and derive bounds for, two definitions of throughput, the classic throughput usually considered in the literature, and a new generalized definition which we call weak throughput; for each of them, we consider two routing models, a direct one, where demand can only be served on a single hop, and a general one, where multi-hop routing is allowed. Our main result is a separation result which solves an open problem in the literature about the classic throughput definition, showing that demand-aware topologies can outperform demand-oblivious topologies even in the worst case: the demand-aware throughput asymptotically approaches at least 5/8, while it is known that the demand-oblivious throughput is n/(2n-1), which is roughly 1/2. In terms of computational complexity, we show that computing the demand-aware weak throughput is NP-hard, but computing the demand-aware (weak) direct throughput is polynomial-time solvable.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper analyzes four variants of demand-aware network throughput (classic vs. weak definitions, each under direct single-hop and general multi-hop routing) and establishes a separation from demand-oblivious throughput. Its central claim is that demand-aware classic throughput achieves an asymptotic worst-case guarantee of at least 5/8, improving on the known demand-oblivious bound of n/(2n-1) ≈ 1/2; it further shows that computing demand-aware weak throughput is NP-hard while the direct-throughput variants are polynomial-time solvable.

Significance. If the separation and complexity results hold, the work resolves an open question by proving that demand-aware topologies can strictly outperform demand-oblivious ones even in the worst case over demand matrices. This has direct implications for reconfigurable optical datacenter networks. The paper's strength is its clean graph-theoretic derivation of the 5/8 lower bound and the matching complexity dichotomy, both obtained without fitted parameters or circular definitions.

minor comments (2)
  1. The abstract states that the demand-aware throughput 'asymptotically approaches at least 5/8' but does not explicitly indicate the limit (e.g., as n → ∞). Adding this clarification would prevent misinterpretation.
  2. A summary table listing the four variants together with their proven bounds and complexity status would improve readability and allow readers to compare the results at a glance.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading, positive summary, and recommendation of minor revision. We are pleased that the separation result and complexity dichotomy are viewed as resolving an open question with implications for reconfigurable datacenter networks. Since no specific major comments were raised, we address the overall feedback below and will incorporate any minor editorial suggestions in the revised version.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The derivation of the 5/8 asymptotic lower bound on demand-aware classic throughput and the n/(2n-1) comparison to demand-oblivious throughput rests on explicit worst-case analysis over arbitrary demand matrices and topology choices under the direct/general routing models. Complexity results (NP-hardness for weak throughput, polynomial-time for direct) are obtained via standard reductions on bipartite matching and flow problems. No equation or claim reduces by construction to a fitted parameter, self-definition, or load-bearing self-citation; all bounds are externally falsifiable combinatorial statements independent of the paper's own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard graph-theoretic models of networks and routing plus the new definitions of weak throughput; no free parameters or invented entities are introduced.

axioms (2)
  • standard math Networks are modeled as undirected graphs with unit-capacity edges.
    Implicit in all throughput definitions and routing models.
  • domain assumption Demand matrices are arbitrary non-negative real matrices representing pairwise communication requirements.
    Standard assumption for worst-case analysis in the field.

pith-pipeline@v0.9.0 · 5627 in / 1397 out tokens · 28513 ms · 2026-05-08T16:41:29.066145+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

34 extracted references · 30 canonical work pages

  1. [1]

    Vamsi Addanki, Chen Avin, and Stefan Schmid. Mars: Near-optimal through- put with shallow buffers in reconfigurable datacenter networks.Proceedings of the ACM on Measurement and Analysis of Computing Systems, 7(1):2:1–2:43, 2023. doi: 10.1145/3579312

    work page doi:10.1145/3579312 2023

  2. [2]

    Ver- 32 milion: A traffic-aware reconfigurable optical interconnect with formal throughput guarantees.CoRR, abs/2504.09892, 2025

    Vamsi Addanki, Chen Avin, Goran Dario Knabe, Giannis Patronas, Dimitris Syriv- elis, Nikos Terzenidis, Paraskevas Bakopoulos, Ilias Marinos, and Stefan Schmid. Ver- 32 milion: A traffic-aware reconfigurable optical interconnect with formal throughput guarantees.CoRR, abs/2504.09892, 2025. doi: 10.48550/ARXIV.2504.09892

    work page doi:10.48550/arxiv.2504.09892 2025

  3. [3]

    Binkert, Al Davis, Moray McLaren, and Robert S

    Jung Ho Ahn, Nathan L. Binkert, Al Davis, Moray McLaren, and Robert S. Schreiber. Hyperx: Topology, routing, and packaging of efficient large-scale net- works. InProceedings of the 2009 International Conference for High Performance Computing, Networking, Storage and Analysis (SC), pages 1–11. ACM, 2009. doi: 10.1145/1654059.1654101

    work page doi:10.1145/1654059.1654101 2009

  4. [4]

    Ahuja, Thomas L

    Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin.Network flows – Theory, algorithms and applications. Prentice Hall, 1993. ISBN 978-0-13-617549-0

    1993

  5. [5]

    2008 , isbn =

    Mohammad Al-Fares, Alexander Loukissas, and Amin Vahdat. A scalable, commod- ity data center network architecture. InProceedings of the ACM SIGCOMM 2008 Conference, pages 63–74. ACM, 2008. doi: 10.1145/1402958.1402967

    work page doi:10.1145/1402958.1402967 2008

  6. [6]

    Optimal oblivious reconfigurable networks

    Daniel Amir, Tegan Wilson, Vishal Shrivastav, Hakim Weatherspoon, Robert Klein- berg, and Rachit Agarwal. Optimal oblivious reconfigurable networks. InProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1339–1352. ACM, 2022. doi: 10.1145/3519935.3520020

    work page doi:10.1145/3519935.3520020 2022

  7. [7]

    Revolutionizing datacenter networks via reconfigurable topologies.Communications of the ACM, 68(6):44–53, 2025

    Chen Avin and Stefan Schmid. Revolutionizing datacenter networks via reconfigurable topologies.Communications of the ACM, 68(6):44–53, 2025. doi: 10.1145/3708980

    work page doi:10.1145/3708980 2025

  8. [8]

    Demand-aware network designs of bounded degree.Distributed Computing, 33(3-4):311–325, 2020

    Chen Avin, Kaushik Mondal, and Stefan Schmid. Demand-aware network designs of bounded degree.Distributed Computing, 33(3-4):311–325, 2020. doi: 10.1007/S00446- 019-00351-5

    work page doi:10.1007/s00446- 2020

  9. [9]

    Demand-aware network design with minimal congestion and route lengths.IEEE/ACM Transactions on Networking, 30 (4):1838–1848, 2022

    Chen Avin, Kaushik Mondal, and Stefan Schmid. Demand-aware network design with minimal congestion and route lengths.IEEE/ACM Transactions on Networking, 30 (4):1838–1848, 2022. doi: 10.1109/TNET.2022.3153586

    work page doi:10.1109/tnet.2022.3153586 2022

  10. [10]

    Das, Jon P

    Navid Hamed Azimi, Zafar Ayyub Qazi, Himanshu Gupta, Vyas Sekar, Samir R. Das, Jon P. Longtin, Himanshu Shah, and Ashish Tanwer. Firefly: A reconfigurable wireless data center fabric using free-space optics. InProceedings of the ACM SIGCOMM 2014 Conference, pages 319–330. ACM, 2014. doi: 10.1145/2619239.2626328

    work page doi:10.1145/2619239.2626328 2014

  11. [11]

    Universal connection schedules for reconfigurable networking

    Shaleen Baral, Robert Kleinberg, Sylvan Martin, Henry Rogers, Tegan Wilson, and Ruogu Zhang. Universal connection schedules for reconfigurable networking. InPro- ceedings of the 37th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4996–5026. SIAM, 2026. doi: 10.1137/1.9781611978971.18

    work page doi:10.1137/1.9781611978971.18 2026

  12. [12]

    Curtis, Tommy Carpenter, Mustafa Elsheikh, Alejandro L´ opez-Ortiz, and Srinivasan Keshav

    Andrew R. Curtis, Tommy Carpenter, Mustafa Elsheikh, Alejandro L´ opez-Ortiz, and Srinivasan Keshav. REWIRE: An optimization-based framework for unstructured data center network design. InProceedings of the 31st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), pages 1116–1124. IEEE, 2012. doi: 10.1109/INFCOM.2012.6195470. 33

    work page doi:10.1109/infcom.2012.6195470 2012

  13. [13]

    Shafayat Rahman, Xin Yuan, Scott Pakin, and Mike Lang

    Peyman Faizian, Md Atiqul Mollah, Md. Shafayat Rahman, Xin Yuan, Scott Pakin, and Mike Lang. Throughput models of interconnection networks: The good, the bad, and the ugly. InProceedings of the 25th IEEE Annual Symposium on High- Performance Interconnects (HOTI), pages 33–40. IEEE Computer Society, 2017. doi: 10.1109/HOTI.2017.21

    work page doi:10.1109/hoti.2017.21 2017

  14. [14]

    Helios: A hybrid electrical/optical switch architecture for modular data centers

    Nathan Farrington, George Porter, Sivasankar Radhakrishnan, Hamid Hajabdolali Bazzaz, Vikram Subramanya, Yeshaiahu Fainman, George Papen, and Amin Vahdat. Helios: A hybrid electrical/optical switch architecture for modular data centers. In Proceedings of the ACM SIGCOMM 2010 Conference, pages 339–350. ACM, 2010. doi: 10.1145/1851182.1851223

    work page doi:10.1145/1851182.1851223 2010

  15. [15]

    Sun, Joseph E

    Nathan Farrington, Alex Forencich, George Porter, P.-C. Sun, Joseph E. Ford, Yesha- iahu Fainman, George C. Papen, and Amin Vahdat. A multiport microsecond optical circuit switch for data center networking.IEEE Photonics Technology Letters, 25(16): 1589–1592, 2013. doi: 10.1109/LPT.2013.2270462

    work page doi:10.1109/lpt.2013.2270462 2013

  16. [16]

    De- pendent rounding and its applications to approximation algorithms.Journal of the ACM, 53(3):324–360, 2006

    Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, and Aravind Srinivasan. De- pendent rounding and its applications to approximation algorithms.Journal of the ACM, 53(3):324–360, 2006. doi: 10.1145/1147954.1147956

    work page doi:10.1145/1147954.1147956 2006

  17. [17]

    Garey and David S

    Michael R. Garey and David S. Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. ISBN 0-7167-1044-7

    1979

  18. [18]

    Devanur, Janardhan Kulkarni, Gireeja Ranade, Pierre-Alexandre Blanche, Houman Rastegarfar, Madeleine Glick, and Daniel C

    Monia Ghobadi, Ratul Mahajan, Amar Phanishayee, Nikhil R. Devanur, Janardhan Kulkarni, Gireeja Ranade, Pierre-Alexandre Blanche, Houman Rastegarfar, Madeleine Glick, and Daniel C. Kilper. ProjecToR: Agile reconfigurable data center interconnect. InProceedings of the ACM SIGCOMM 2016 Conference, pages 216–229. ACM, 2016. doi: 10.1145/2934872.2934911

    work page doi:10.1145/2934872.2934911 2016

  19. [19]

    Greenberg, James R

    Albert G. Greenberg, James R. Hamilton, Navendu Jain, Srikanth Kandula, Changhoon Kim, Parantap Lahiri, David A. Maltz, Parveen Patel, and Sudipta Sen- gupta. VL2: A scalable and flexible data center network.Communications of the ACM, 54(3):95–104, 2011. doi: 10.1145/1897852.1897877

    work page doi:10.1145/1897852.1897877 2011

  20. [20]

    Chen Griner, Johannes Zerwas, Andreas Blenk, Manya Ghobadi, Stefan Schmid, and Chen Avin. Cerberus: The power of choices in datacenter topology design – A through- put perspective.Proceedings of the ACM on Measurement and Analysis of Computing Systems, 5(3):38:1–38:33, 2021. doi: 10.1145/3491050

    work page doi:10.1145/3491050 2021

  21. [21]

    A survey of reconfigurable optical networks.Optical Switching and Network- ing, 41:100621, 2021

    Matthew Nance Hall, Klaus-Tycho Foerster, Stefan Schmid, and Ramakrishnan Du- rairajan. A survey of reconfigurable optical networks.Optical Switching and Network- ing, 41:100621, 2021. doi: 10.1016/J.OSN.2021.100621. 34

    work page doi:10.1016/j.osn.2021.100621 2021

  22. [22]

    and Kale, Laxmikant V

    Nikhil Jain, Abhinav Bhatele, Xiang Ni, Nicholas J. Wright, and Laxmikant V. Kal´ e. Maximizing throughput on a dragonfly network. InProceedings of the 2014 Interna- tional Conference for High Performance Computing, Networking, Storage and Analy- sis (SC), pages 336–347. IEEE Computer Society, 2014. doi: 10.1109/SC.2014.33

    work page doi:10.1109/sc.2014.33 2014

  23. [23]

    Measuring and understanding throughput of network topologies

    Sangeetha Abdu Jyothi, Ankit Singla, Brighten Godfrey, and Alexandra Kolla. Measuring and understanding throughput of network topologies. InProceedings of the 2016 International Conference for High Performance Computing, Networking, Storage and Analysis (SC), pages 761–772. IEEE Computer Society, 2016. doi: 10.1109/SC.2016.64

    work page doi:10.1109/sc.2016.64 2016

  24. [24]

    Optimal load-balancing

    Isaac Keslassy, Cheng-Shang Chang, Nick McKeown, and Duan-Shin Lee. Optimal load-balancing. InProceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), pages 1712–1722. IEEE, 2005. doi: 10.1109/INFCOM.2005.1498452

    work page doi:10.1109/infcom.2005.1498452 2005

  25. [25]

    HPCC: high precision congestion control,

    Yuliang Li, Rui Miao, Hongqiang Harry Liu, Yan Zhuang, Fei Feng, Lingbo Tang, Zheng Cao, Ming Zhang, Frank Kelly, Mohammad Alizadeh, and Minlan Yu. HPCC: High precision congestion control. InProceedings of the ACM SIGCOMM 2019 Con- ference, pages 44–58. ACM, 2019. doi: 10.1145/3341302.3342085

    work page doi:10.1145/3341302.3342085 2019

  26. [26]

    Mellette, Rob McGuinness, Arjun Roy, Alex Forencich, George Papen, Alex C

    William M. Mellette, Rob McGuinness, Arjun Roy, Alex Forencich, George Papen, Alex C. Snoeren, and George Porter. Rotornet: A scalable, low-complexity, optical datacenter network. InProceedings of the ACM SIGCOMM 2017 Conference, pages 267–280. ACM, 2017. doi: 10.1145/3098822.3098838

    work page doi:10.1145/3098822.3098838 2017

  27. [27]

    Mogul and Lucian Popa

    Jeffrey C. Mogul and Lucian Popa. What we talk about when we talk about cloud network performance.Computer Communication Review, 42(5):44–48, 2012. doi: 10.1145/2378956.2378964

    work page doi:10.1145/2378956.2378964 2012

  28. [28]

    Cambridge Uni- versity Press, 1995

    Rajeev Motwani and Prabhakar Raghavan.Randomized Algorithms. Cambridge Uni- versity Press, 1995. ISBN 0-521-47465-5

    1995

  29. [29]

    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 2021 Conference, pages 349–369. ACM, 2021. doi: 10.1145/3452296.3472913

    work page doi:10.1145/3452296.3472913 2021

  30. [30]

    Randomized distributed edge coloring via an extension of the

    Alessandro Panconesi and Aravind Srinivasan. Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds.SIAM Journal on Computing, 26 (2):350–368, 1997. doi: 10.1137/S0097539793250767

    work page doi:10.1137/s0097539793250767 1997

  31. [31]

    Leon Poutievski, Omid Mashayekhi, Joon Ong, Arjun Singh, Muhammad Mukar- ram Bin Tariq, Rui Wang, Jianan Zhang, Virginia Beauregard, Patrick Conner, Steve D. Gribble, Rishi Kapoor, Stephen Kratzer, Nanfang Li, Hong Liu, Karthik Nagaraj, Jason Ornstein, Samir Sawhney, Ryohei Urata, Lorenzo Vicisano, Kevin 35 Yasumura, Shidong Zhang, Junlan Zhou, and Amin V...

    work page doi:10.1145/3544216.3544265 2022

  32. [32]

    High throughput data center topology design

    Ankit Singla, Philip Brighten Godfrey, and Alexandra Kolla. High throughput data center topology design. InProceedings of the 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI), pages 29–41. USENIX Association, 2014

    2014

  33. [33]

    LFTI: A new performance metric for assessing interconnect designs for extreme-scale HPC sys- tems

    Xin Yuan, Santosh Mahapatra, Michael Lang, and Scott Pakin. LFTI: A new performance metric for assessing interconnect designs for extreme-scale HPC sys- tems. InProceedings of the 28th IEEE International Parallel and Distributed Pro- cessing Symposium (IPDPS), pages 273–282. IEEE Computer Society, 2014. doi: 10.1109/IPDPS.2014.38

    work page doi:10.1109/ipdps.2014.38 2014

  34. [34]

    Johannes Zerwas, Csaba Gy¨ orgyi, Andreas Blenk, Stefan Schmid, and Chen Avin. Duo: A high-throughput reconfigurable datacenter network using local routing and control.Proceedings of the ACM on Measurement and Analysis of Computing Systems, 7(1):20:1–20:25, 2023. doi: 10.1145/3579449. 36

    work page doi:10.1145/3579449 2023