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

Matthias Bentert, Chen Avin, Stefan Schmid · 2026

Read A Separation Between Optimal Demand-Oblivious and Demand-Aware Network Throughput by Matthias Bentert, Chen Avin, Stefan Schmid (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-04699.txt.

Introduction

Matthias Bentert, Chen Avin, and Stefan Schmid compare two ways of running a communication network. One fixes the topology in advance and serves whatever demand arrives. The other reshapes the topology toward the known demand. Reconfigurable optical hardware in modern data centres now allows that second way. Oblivious throughput has been studied deeply, while demand-aware throughput remained poorly understood.

They take a systematic approach to four variants of demand-aware throughput. Those variants cover two definitions of the classic throughput measure. The authors derive bounds on what is achievable. They also study the computational complexity of finding the topology that optimises throughput for a given demand matrix. The work separates what demand awareness can and cannot buy in network performance.

Catalog record

CREATORMatthias Bentert, Chen Avin, Stefan Schmid
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE94 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.04699

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Separation Between Optimal Demand-Oblivious and Demand-Aware Network Throughput Matthias Bentert, Chen Avin, Stefan Schmid 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 classical 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 \frac{5}{8} , while it is known that the demand-oblivious throughput is at most n 2 ​ n − 1 ≈ 1 2 \frac{n}{2n-1}\approx\frac{1}{2} . In terms of computational complexity, we show that computing the demand-aware weak throughput is NP-hard, but computing the demand-aware direct throughput and the demand-aware weak direct throughput are both polynomial-time solvable. We leave it as an open problem whether computing the demand-aware throughput is polynomial-time solvable or NP-hard, but we conjecture that it is NP-hard. 1 Introduction Many data-intensive distributed applications, especially those related to high-performance computing and machine learning, critically depend on a high-throughput interconnecting communication network. Accordingly, over the last decades, significant efforts have been made to design novel datacenter networks which provide high capacity at low cost. To this end, researchers intensively studied how to define and measure the throughput of a network [ 23 , 29 ] , how to model its impact on application performance [ 13 , 27 ] , and how to improve it [ 1 , 5 , 6 , 11 , 25 , 26 , 32 ] . A particularly intriguing solution are demand-aware networks (also known as topology engineering in the literature) [ 9 , 7 , 8 , 10 , 18 , 15 , 20 , 31 , 34 ] : networks whose topology can be optimized towards the demand using emerging optical switching technologies. However, defining and analyzing the throughput of a demand-aware network topology is surprisingly subtle. Existing literature so far mostly revolves around the demand-oblivious throughput: design a network topology (a graph) G (with given link capacities) that can serve well any (doubly stochastic) demand matrix \mathcal{M} , describing pairwise communication requirements. More specifically, the throughput of a (directed) graph G with respect to a demand matrix \mathcal{M} is defined by the maximum factor by which the rates specified in the demand matrix must be scaled (or equivalently, the time horizon of the transmission increased) such that they can be served on the topology without violating its link capacities [ 22 , 23 , 33 , 34 , 20 , 1 , 2 , 24 ] . The throughput of a graph is defined as its worst-case throughput over all possible demand matrices. It is already known that the throughput of demand-oblivious networks connecting n nodes is at most \frac{n}{2n-1}\approx\frac{1}{2} [ 24 ] . Empirical studies suggest that demand-aware networks can achieve a higher throughput. However, whether this also holds under worst-case demand matrices has been an open question for several years [ 20 , 1 , 2 , 14 ] . We study this fundamental question. Particularly: is there a separation between the worst case demand-aware throughput and the demand-oblivious throughput? To shed light on the demand-aware throughput, we take a systematic approach and study both the achievable bounds as well as the computational complexity of optimizing the topology. Moreover, we consider two different throughput definitions and two different routing models, that is, four scenarios in total. In particular, in addition to the classic throughput definition in the literature mentioned above, we also introduce an intuitive and more general definition which we call the weak throughput of a network: in a nutshell (details will follow), the weak throughput measures the highest possible percentage of demands that can be served. In terms of routing models, we consider a multi-hop scenario, where the demand can be routed arbitrarily over the network, and a single-hop scenario, where the demand can be served only across a single link—as is sometimes the case in optical networks [ 21 ] . We refer to the latter as direct routing. Before presenting our contributions in detail, we introduce our model more formally. 1.1 Formal Model For a positive integer n , we use [n] to denote the set \{1,2,\ldots,n\} . We use \boldsymbol{1}_{x} for a Boolean expression x as the indicator function: “1 if x holds and 0 otherwise”. For a sequence \sigma=(\phi_{1},\phi_{2},\ldots,\phi_{\ell}) , we use x\in\sigma as a shorthand for x\in\{\phi_{1},\phi_{2},\ldots,\phi_{\ell}\} . We model networks as multigraphs, that is, graphs can contain self-loops and parallel arcs. If each vertex in a directed graph G has exactly r incoming and outgoing arcs, then we call G a directed r -regular graph . A path P in a directed graph is a sequence of arcs ((u_{1},v_{1}),(u_{2},v_{2}),\ldots,(u_{\ell},v_{\ell})) such that for all {i\in[\ell-1]} it holds that v_{i}=u_{i+1} . We say that P is a path from u_{1} to v_{\ell} . The length \len(P)=\ell of a path P is the number of arcs in it and we only consider paths containing at least one arc in this work. This is consistent with the existing literature, where demand from a node v to itself has to use some arcs (possibly a self-loop). We mention in passing that while our specific constructions do use self-loops, all of our results can also be transferred to the setting where demand from a node to itself can be served by empty paths. The throughput bounds (and a construction in a hardness proof later on) will then of course be slightly different. A matrix is doubly stochastic if each entry is non-negative and each row and each column sums to 1 . As in the existing literature, we will assume that all input matrices are doubly stochastic. For a matrix \mathcal{M}=(a_{i,j})_{i,j\in[n]} and a number x , we use x\mathcal{M} to denote the matrix, where each entry is scaled by a factor of x , that is, the matrix (xa_{i,j})_{i,j\in[n]} . We will often match the i -th row and i -th column of a matrix to the i -th vertex in a graph. For notational convenience, we will often use [n] as the set of

Read the complete text