Extreme-Scale Interconnection Networks Alejandro Cano† , Cristina Brinza‡ , Cristóbal Camarero† , Carmen Martı́nez† , Ramón Beivide†,∗ † Universidad de Cantabria, SPAIN ‡ Performed while working for the Universidad de Cantabria, SPAIN ∗ Barcelona Supercomputing Center, SPAIN {alejandro.cano, cristobal.camarero, carmen.martinez,ramon.beivide} @unican.es, [email protected]
arXiv:2605.26960v1 [cs.NI] 26 May 2026
May 27, 2026
Abstract Extreme-scale data centers are the backbone of nextgeneration computing, enabling breakthroughs in science, artificial intelligence, and global innovation through unprecedented processing power and scalability. This work examines leaf-spine network topologies that offer extreme scalability—connecting a vast number of endpoints—while delivering strong performance at low cost. It takes as a starting point two alternatives to the widely used Fat-Tree topology: the Orthogonal Fat-Tree and the Random Folded Clos. The resulting Multipass Random Leaf-Spine (MRLS) networks inherit their advantages and surpass Fat-Trees in both throughput and flexibility. To fully leverage the topological properties of these networks, various nonminimal routing strategies are considered. An exhaustive evaluation using an interconnection network simulator provides insight into the trade-offs and scalability of these topologies under realistic conditions, positioning them as a promising solution for extreme-scale systems. The MRLS achieves a 50% speedup against a Fat-Tree for an All2All collective comprising 100k endpoints, and 100% against Dragonfly networks for the same collective.
1
Figure 1: Orthogonal Fat Tree with parameter q = 2. It has n = 14 leaf switches and k = 3 up-links at the leaf switches.
Figure 2: MRLS with n = 14 leaf switches and k = 3 up-links at the leaf switches. Highlighted a pair of nodes at distance 4 and one path.
switches that are not connected to any endpoint. In contrast, in direct networks (DN) such as Dragonfly (DF) [5], there is no distinction among switches, and all of them have endpoints connected. The FT is a particularly notable indirect network for being rearrangeably non-blocking, meaning it can support communication between any pair of nodes using disjoint paths. This implies there is no interference between multiple transmissions when employing circuit switching. However, the implementation cost of FT networks is substantially higher compared to other alternatives, prompting the exploration of more scalable and cost-effective solutions. For extreme-scale systems, where the network can account for a significant fraction of the system cost, minimizing it is crucial, even if it poses additional challenges. Among scalable 2-level network topologies, the Orthogonal Fat-Tree (OFT) is a prominent candidate [6]. Figure 1 shows the smallest one. While it offers much greater scalability than FT, its performance degrades significantly when subjected to non-uniform traffic. To address this, non-minimal routing strategies are often employed to improve throughput and load balancing [7]. However, a key limitation of the OFT lies in its rigid construction requirements: it can only be built for very specific parameter values. This constraint limits both the applicability and expandability of the topology, making it difficult to adapt to the desired system size.
Introduction
As workload demands in Data Center (DC) and HighPerformance Computing (HPC) systems continue to increase, the scale of network interconnects also expands. This growth directly impacts the achievable performance of the overall system. Extreme-scale DCs interconnect hundreds of thousands of endpoints, with projections of their upgrade to millions [1, 2, 3]. A significant proportion of the interconnects used nowadays are indirect networks such as the Fat-Tree (FT) or Folded Clos [4]. In an indirect network (IN), switches are organized into levels. The lowest level consists of leaf switches, which connect directly to endpoints and to switches in the level above. The highest level consists of root switches (or spines if it’s a two-level network), which connect only to the switches below them. Communication between endpoints is indirect, meaning traffic must traverse intermediate 1
Table 1: Notation throughout the article.
The Random Folded Clos (RFC) [8] offers an alternative topology designed to balance performance and scalability while facilitating flexible system expansion. Unlike the strictly defined interconnection pattern of the OFT, the RFC employs a random interconnection pattern between switch levels. Figure 2 depicts a 2-level, randomly interconnected network featuring the same number of switches and endpoints as the OFT shown in Figure 1. However, this topology deviates from the standard RFC, as it lacks inherent up-down connectivity and allows minimal path lengths of up to four hops. Consequently, we introduce this distinct topology which we call Multipass Random Leaf-Spine (MRLS), alongside a corresponding routing mechanism. This work investigates such networks and evaluates their suitability for extreme-scale systems. In particular, our contributions are as follows:
S N M R A D d(x, y) Θ l h Ni u d f q
1. The proposal of MRLS, a novel network topology, alongside a routing method for randomly wired indirect networks.
Total number of endpoints. Total number of switches. Total number of bidirectional links. Switch radix. Average distance between leaf switches in an IN, or between vertices in a DN. Diameter, the maximum distance between leaf switches. Distance from x to y. Estimator of the load per endpoint. Number of switch levels. Height of a multistage network, h = l − 1. Number of switches in the level i. Number of upward ports of a switch in an IN. Number of downward ports of a switch in an IN. Thickness factor of the switches in an IN. A power of prime, employed in OFT (cf. [9, 10]).
2. A comprehensive analysis of the architectural benefits of MRLS, demonstrating key topological adAlthough this abstraction simplifies the model, it vantages such as fine-grained scalability and en- is robust. Specialized architectures like BCube [11] hanced routing efficiency. (multi-interface endpoints) or GPU-dense nodes like those in the Frontier supercomputer (multiple NICs per 3. An extensive performance evaluation comparing endpoint) technically deviate from this simple model. MRLS networks against state-of-the-art indirect However, these cases represent only a constant-factor and direct topologies such as Dragonfly, including increase in connectivity. Therefore, we proceed with large-scale simulations supporting up to 100,000 the switch-level graph model, noting that extensions endpoints. to multi-interface scenarios are straightforward. Next, FTs and other more cost-effective topologies The structure of the paper is as follows. Section 2 introduces the notation for topologies and formulae for are introduced. performance and cost. Section 3 elaborates on the limitations of current topologies. In Section 4, the MRLS proposal is formally introduced and studied. Section 5 describes the workloads for simulation and selected scenarios. The simulation results are shown and analyzed in Section 6. Section 7 concludes the paper.
2.1.1
The non-blocking Fat-Tree
The most prevalent topology in modern DCs and HPC systems is the Fat-Tree [12], which is essentially a multistage folded Clos network [13]. To ensure non-blocking behavior, standard Fat-Trees are built such that the aggregate bandwidth going up2 Background wards from any switch equals the bandwidth going This section establishes the basic concepts and nota- downwards. Using switches with radix R, this implies tion used in the paper. We begin by defining the net- splitting ports evenly, using R/2 ports for up links and work models and standard topologies, followed by a the other R/2 for down links. For a Fat-Tree of height h: formal analysis of the relationships between topological distances, performance, and cost. Table 1 summarizes • There are h + 1 levels of switches. the key notation employed throughout the article.
2.1
• The network supports S = 2(R/2)h+1 endpoints.
Topologies
• The diameter is 2h, and the average distance A is The topology of a network describes the interconnecclose to the diameter. tion pattern between endpoints and switches. In many high-performance systems, each endpoint possesses a While exhibiting high performance, the Fat-Tree single network interface and is connected to one switch. This allows us to omit the endpoints and abstract the is expensive due to the high number of cables and topology as a graph where vertices represent switches switches required to maintain its non-blocking bandand edges represent the physical links between them. width. 2
2.1.2
Cost-Effective topologies
link bandwidth. A value of L = 1 means that all endpoints inject traffic into the network at full rate withDriven by the high cost of Fat-Trees, extreme-scale sysout provoking saturation. Under our assumptions, by tems often employ other topologies to minimize it when construction, it is impossible for an endpoint to inject interconnecting the same number of endpoints. Examtraffic over its nominal rate, that is, with L > 1. ples of topologies that have been proposed to reduce While L is a direct measure of performance, it dethe cost of Fat-Trees include: pends on many factors, including the application’s communication patterns and the routing algorithm, • Slimmed Fat-Tree [14, 15, 16, 17]. making it difficult to model directly. Consequently, it is useful to set an upper bound on L defined only by • Orthogonal Fat-Tree (OFT) [6]. the network’s topological properties in a specific traffic • Random Folded Clos (RFC) [8]. scenario. We denote it as the network capacity limit (Θ), which is the performance bound of the topology • Dragonfly [5]. under uniform random traffic. Observe that other trafAll these topologies relax the non-blocking assump- fic patterns could surpass Θ. As established in prior tion of the FT. The OFT, RFC, and Dragonfly reduce work [9, 18], this capacity limit is given by: the average distance with respect to FTs, allowing for 2M (1) Θ= a decrease in cost at the expense of performance degraS·A dation under non-uniform traffic patterns. where S is the number of endpoints, M is the number of physical links (with 2M representing the total 2.2 Basic Metrics full-duplex bandwidth), and A is the average distance. That is, assuming a constant target capacity Θ, inThe design of any interconnection network is governed creasing the number of endpoints S without drastically by a tight interplay between physical constraints toincreasing the number of links M requires minimizgether with performance and cost metrics. Here, we ing the average distance A. This motivation drives formalize these relationships. the interest in topologies that approach the Moore Bound [19], which defines the theoretical minimum di2.2.1 Topological Distances ameter for a graph of a given degree. The capacity limit serves to classify networks in the We consider two primary distance metrics measured following way: over the switch-to-switch graph: • The diameter (D), the maximum shortest path between any pair of switches connected to endpoints.
• A value of Θ = 1 indicates a balanced network, which has enough capacity to support all endpoints transmitting at their full rate.
• The average distance (A), the average minimal path length across all pairs of switches connected to endpoints.
• A value of Θ < 1 signifies an oversubscribed network, where the topology itself is the bottleneck.
• A value of Θ > 1 could suggest an overdimenEach of these metrics has a counterpart considering sioned network, having more capacity than needed paths between any pair of switches instead of just beto support full-rate traffic from all endpoints. Nevtween switches connected to endpoints. These are deertheless, this exceeded capacity can be beneficial noted in the paper as D∗ and A∗ , respectively, and acfor handling non-uniform traffic patterns and proquire relevance when dealing with evolved packet routviding robustness against congestion. The auging mechanisms such as derouting through an arbitrary mented capacity can be leveraged by adaptive switch. routing algorithms, which may use non-minimal If the routing algorithm allows non-minimal paths, paths—increasing the effective path length to a it is important to note that the length of the employed value higher than A—to balance the load across paths may be different in practice. In many cases, there the network. is a maximum path length, which is a bound on the number of switches that can be visited along a route. Under these conditions, the relationship 0 ≤ L ≤ This is a routing-dependent metric complementary to min{1, Θ} holds. Here, achieving L = min{1, Θ} the diameter. is also challenging. Even in non-oversubscribed networks (Θ ≥ 1), achieving the maximum injected load of L = 1 requires additional resources. Factors like 2.2.2 Performance Head-of-Line (HoL) blocking or poor load balancing In practice, the performance of an interconnection net- due to packet routing can prevent the system from work is determined by the injected load (L) per end- reaching its full potential. Ideal routing and Virtual point1 , which represents the average amount of traffic Output Queueing [20] would allow the system to reach an endpoint injects into the network normalized by the L = min{1, Θ}; however, this is not always realistic. 1 This is equivalent to the accepted load per endpoint, or Thus, while having Θ ≥ 1 is a necessary condition for achieving good performance, it is not a guarantee. throughput. 3
2.2.3
Scalability
this number, one would need to increase the number of levels to 4, leading to a prohibitive cost in cables (50% more than in a 3-level FT), switches (40% more), and energy consumption. Cost reduction is often achieved through coarse adjustments, such as oversubscription. For instance, in a FT, reducing the number of non-leaf switches cuts costs but immediately halves the bisection bandwidth. Hence, one must choose between a generic, expensive non-blocking FT or a significantly cheaper, lowerperformance slimmed FT. Similarly, direct networks like Dragonfly [5] reduce costs by optimizing for uniform traffic, but this structural decision fixes the performance characteristics. If the workload demands slightly better worst-case performance, the network cannot be easily tuned up, requiring a different topological class entirely. Therefore, to achieve extreme scalability while maintaining good performance at an attainable cost, other, more cost-efficient topologies must be considered.
The scalability of a topology is its ability to increase the number of endpoints S while maintaining a capacity limit Θ. Usually, to increase the number of endpoints in a topology, either the number of switches or their radix R and the number of links connecting them, must also be increased. Also, the capacity limit Θ is typically set to 1, representing a balanced network. However, other values can be considered based on specific performance requirements. For example, a fully populated Fat-Tree has a scalability function of S = 2−h Rh+1 , with Θ = 1.0. In contrast, a simple ring topology is considered unscalable because maintaining capacity Θ requires the endpoint count to freeze as the network grows (since A grows linearly with N ). 2.2.4
Cost
Finally, we quantify the cost of a topology by means of very simple metrics such as the number of links and switches required by each endpoint. They can be di3.2 Rigidity of network topologies rectly obtained from Eq. (1). The Link Cost per endpoint can be expressed in A major drawback of most cost-efficient topology famterms of the average distance: ilies is the discrete nature of their valid network sizes, suffering from structural rigidity. If the system needs Θ·A M = (2) to be expanded in the future, it may be very challengCostlinks = S 2 ing and costly to find a new valid configuration. Also, Similarly, the Switch Cost per endpoint depends on performance is usually rigid within a given topology how many endpoint-facing ports versus inter-switch family. To overcome these sizing constraints, network ports are used. If we denote k as the average degree of topologies should be flexible, with fine-grained scalathe switch-to-switch graph, the cost due to switches is bility and performance. Costswitches =
N Θ·A = . S k
(3)
3.2.1
Fine-grain scalability
These equations show that low-diameter topologies, Fine-grain scalability is intrinsically linked to increwhich provide low A values, are essential for building mental expandability [21] (also referred to as finegrained incremental expansion). This property encost-effective, extreme-scale systems. sures that a DC can grow its capacity by small increments—adding a single rack or switch—rather than 3 Motivation requiring massive, step-wise upgrades to reach the next valid topological size. Randomly wired topologies inThere are several reasons why the research conducted deed satisfy these criteria satisfactorily, as described in in this work is necessary. The most important ones [22, 23]. are related to network cost and scalability, which are It is important to separate network scalability from considered below. the practice of connecting fewer endpoints than possible. Almost any topology can support any number of endpoints S below its maximum by simply leaving 3.1 Network Cost ports unconnected (depopulation). The following defExtreme-scale DCs demand interconnection networks inition formalizes, in our context, the fine-grain scalathat connect vast numbers of endpoints while balanc- bility concept: ing high performance against manageable costs. A natural question arises: How can we minimize the cost per Definition 3.1. The fine grain scalability of a topolendpoint for a specific system size and switch technol- ogy is the density of the achievable (N1 , R) pairs, with ogy? N1 = N for direct networks. This density is the inThe cost of a FT grows rapidly with the number of verse of the gap between the values of two consecutive endpoints, as Costlinks = h and Costswitches = R2 (h+ 12 ), instances. making them impractical for extreme-scale systems. With switches of 64 ports (R = 64), a 2-level Fat-Tree We prefer to use N1 instead of the whole N as it can support up to 2048 endpoints, and a 3-level Fat- represents more clearly the goal of adding switches with Tree can support up to 65,536 endpoints. To surpass endpoints, rather than just switches for their own sake. 4
The FT offers moderate granularity. While it can be depopulated by removing entire pods, maintaining full bisection bandwidth typically restricts the network to specific sizes. That is, switches at the top level cannot be removed, as it would lead to a general performance loss. The OFT is much more rigid. Due to its reliance on specific routing paths to handle adversarial traffic, leaf switches cannot be selectively removed without breaking connectivity guarantees. Thus, only full configurations are possible. The values of radix are R = 2(q +1), with q a prime power. By the Prime Number theorem this means that around some target R∗ , there are about one valid value from each 2 log R∗ . Its number of leaf switches N1 = 2(q 2 + q + 1) gives an additional restric∗ tion. Around some target will be about one p ∗ N1 there valid value for each 2N1 log N1∗ . 3.2.2
N2 spine switches. Each leaf switch has d down links to connect to endpoints and u uplinks connected to varying spine switches. Each spine switch has u + d downlinks connected to leaf switches. All switches have radix R = u + d. The interconnections between the two levels of switches are decided via a random process [24]. We denote in this work the thickness factor as f = u/d. The inverse of this thickness factor is used in other works as the slimming factor [17], which is also known as the fitness ratio, contention factor, or blocking ratio [25]. The reasonable thickness factor values for MRLS lie in 1 ≤ f ≤ 3, as we show in the next section. Unlike FTs, RFCs or OFTs, a MRLS network may be built for any value of N1 and N2 following uN1 = RN2 . This is the greatest fine-grain scalability possible for an indirect network.
Fine-grain performance
4.1
In standard topologies, not only is the size of the systems is rigid, but also their performance This work explores extreme-scale topologies that not only are finegrained scalable but also allow for fine-grain performance tuning. This implies that for any desired number of endpoints S and switch radix R, the topology can be adjusted to achieve a specific performance level, rather than being constrained to a few discrete options.
4
Scalability
Extreme-scale DCs require topologies capable of expanding from 100,000 to potentially millions of endpoints [3]. In this context, we compare MRLS networks against known topologies (FT, OFT, RFC). In Figure 3, we illustrate the expandability spectrum of MRLS networks for a fixed radix R = 36. The employed thickness factor is f = 1. The figure highlights regions where MRLS networks can achieve specific even diameters D depending on the number of network passes needed to connect a number of endpoints S. The diameter including spines (D∗ ) is also a notable structural property of the topology and is important for the non-minimal routing algorithms required by these topologies. Hence, their thresholds are included. Observe that two consecutive regions for D∗ are included in a region with a given diameter D. It should be noted that D can be obtained from D∗ by ∗ D = 2⌊ D2 ⌋, but not vice versa. The boundaries between regions are actual function plots, indicating the probability for a MRLS instance with the indicated number of endpoints to lie in the left region. Also, they are quite sharp, with a small proportion of sizes being in reasonable doubt about which side they will fall on. Technical details can be found in Appendix A. Looking at the figure, the first boundary is observed to lie around 2K endpoints with a reasonable chance of having a diameter of either 2 or 4. Having D = 2 establishes the limit up to which up/down routing can be employed. From this limit, multi-pass routing is needed, incrementing the diameter by 2 units for each pass. The next boundary is around 30K endpoints, in which the diameter does not change, but only D∗ . That is, the leaf-to-spine maximum distance changes from 4 to 5. To the left, the 2-level OFT can be seen, which has parameters D = 2 and D∗ = 3; and also the 3-level FT, with D = D∗ = 4. Looking at the far right, it can be observed that even using a small radix such as R = 36, a MRLS network can connect 100M endpoints with D = 6, way beyond current practical goals.
Multipass Random Leaf Spine Networks
Among other interesting properties, regular randomly wired direct topologies such as Jellyfish, exhibit lower cost and finer grain scalability than FTs, as described in [22] . In [23], the Random Folded Clos network was introduced as an indirect alternative to the Jellyfish. RFC networks were designed to use Up/Down routing. This simplifies key aspects such as deadlock avoidance, but introduces two important limitations. Foremost, it entails a notable restriction on scalability. This can be waived by adding switch levels, but this leads to unnecessarily large costs. Secondly, even in those networks that are up/down-connected, there is a performance loss from not considering other routes. In this work, we propose the Multipass Random Leaf Spine (MRLS) networks. Our objective is to decouple the physical topology from the routing restrictions, creating a network that retains the cabling simplicity of leaf-spine architectures while unlocking fine-grained scalability and performance. MRLS networks are conceived for extreme-scale systems. In these networks, connectedness between certain pairs of leaf switches is guaranteed through multiple up/down routing phases through the network. Thus, although the network has just 2 levels of switches, its diameter is higher than 2. We formally introduce these networks in the following definition. Definition 4.1. A Multipass Random Leaf-Spine is a 2-level network which consists of N1 leaf switches and 5
6-level∗ FT
D = D = 10
D=D =8
5-level∗ FT
D = 4, D = 6
3-level OFT ∗
D=D =6
4-level∗ FT
D=D =4
3-level∗ FT
D = 2, D = 3
2-level OFT ∗
D=D =2
full leaf-spine ∗
D=D =1
full mesh ∗
Probability
1 D=2 D∗ = 3
D=4 D∗ = 4
D=4 D∗ = 5
D=6 D∗ = 6
105
106
D=6 D∗ = 7
0 103
S=
104
107
108
Average distance
6 5 4 3 2
Figure 3: Scalability spectrum for MRLS with R = 36 and f = 1 together some references. Regions are marked with D = x D∗ = y, meaning that a MRLS in the region has a leaf to leaf diameter of x and a maximum distance between arbitrary switches of y.
MRLS D=2
total number of compute nodes
2-level FT
MRLS D=D ∗ =4 3-level FT
4.2
MRLS D ∗ =5 2-level OFT
In a MRLS network, the cost in links per endpoint is the thickness factor f , as it determines how many links are used to connect endpoints versus how many are used for inter-switch connectivity:
106
105
Costlinks (MRLS) = f =
104
103
Cost
0
Figure 4: topologies.
u M Θ·A = = d S 2
(4)
Although expanding the network by adding more endpoints to the MRLS keeps the cost ratios constant, it increases the average distance A and thus reduces the capacity limit Θ. So, in order to achieve a fixed performance when expanding the network, as A increases, the thickness factor f can be increased as well. This means that for a leaf switch the number of uplinks u 36 50 100 150 200 increases while the number of downlinks d to endpoints is reduced. router radix (number of ports) In general, an MRLS network has the following advantages: Scalability of low-diameter multistage • The cost is easily tunable. The thickness factor f can be adjusted to meet specific cost/performance targets. In Figure 3 the cost is 1 link per endpoint as f = 1 but the network can connect any desired of number of endpoints. • Random wiring provides an almost optimal average distance for any given number of switches and links, minimizing the cost for a target performance [26].
The bottom part of Figure 3 shows the value of the expected average distance A for a MRLS network with a given number of endpoints S. It can be seen to grow slowly, giving 2 ≤ A ≤ 6 for any practical size. As f = 1 is employed, these correspond to values 13 ≤ Θ ≤ 1 for the capacity limit.
As stated above, the thickness factor f can be used to tune the performance of the network even beyond what A requires to be balanced in Equation 1. In typFigure 4 provides another scalability comparison, ical indirect topologies, Up/Down routing is assumed, showing the radix required to connect a given number leading to minimal routes. In this case, the average of endpoints with each topology configuration. Both path length of packets usually equals the topological Figure 3 and 4 have their MRLS networks normalized average distance A. However, routes in MRLS netby f = 1. Observe that it is possible to normalize in works are more similar to those of direct networks, and another way, let us say, with Θ = 1 by changing f . the average path length of packets can be longer than 6
A depending on the selected routing algorithm. This raises the question of whether to dimension the network for non-uniform traffic by replacing the value of A in Equation 1 with the longer effective path lengths of the routes in such a scenario. Thus, if we set A to the average path length of packets under the most adverse permutation traffic and obtain M for Θ = 1, we can build a network that behaves similarly to a nonblocking FT for such a permutation.
4.3
Polarized routing proceeds hop-by-hop by evaluating candidate links based on a very simple logic. Any switch c routing a packet from source s to destination t tracks its distance to both endpoints: d(c, s) and d(c, t). Since s and t are leaf switches in a leaf-spine network, both distances have the same parity and vary by exactly ±1 at every hop. This property allows us to map the routing decisions into just four possible link categories to evaluate each possible next link, making it very efficient. For any switch n as a next hop candidate from switch c, the tuple (d(n, s) − d(c, s), d(n, t) − d(c, t)) can only have 4 values:
Multipass routing in leaf-spine networks
Unlike FTs, OFTs, or RFCs, MRLS networks are not designed for Up/Down routing, and thus, they require a more general algorithm that can leverage the path diversity of the topology. Since a MRLS network is connected randomly, its routing algorithm must be topology-agnostic. However, its bipartite indirect structure allows for a significant simplification of the routing logic, compared to direct networks:
• Forward (+1, −1): The link moves the packet further from the source and closer to the destination. These are minimal routes and are always allowed. • Expansion (+1, +1): The link moves the packet further from both source and destination. This is a non-minimal deroute, only allowed at the beginning of the path, while d(c, s) < d(c, t).
• All routes are symmetrical and follow the same [U p − Down]∗ structure.
• Contraction (−1, −1): The link moves the packet closer to both endpoints. This deroute is only allowed at the end of the path, once d(c, s) ≥ d(c, t).
• Deadlock avoidance techniques require half the resources compared to other topology agnostic routing algorithms for direct networks: Ladder or Virtual Ordered Classes [20] require 1VC per hop, while MRLS requires 1VC per two hops (Up-Down phase), halving the resources needed.
• Backtrack (−1, +1): The link moves the packet closer to the source and further from the destination. These are never allowed.
• The maximum hop bound of a practical routing algorithm can be reduced to 2D.
To implement this, the exact distance values are not required to be carried in the packet header. Instead, a simple 2-bit label per port is sufficient to classify the links into the previous four categories. The routing table is queried twice (indexed by source and destination) to retrieve a bit that indicates if the neighbor is closer (1) or further (0). This 2-bit combination directly yields the label, and the algorithm simply filters the allowed labels based on the current location of the packet. Among the permitted links, the routing selects the one with the lowest occupancy, penalizing deroutes (Expansion and Contraction) to prioritize minimal paths. The simplicity of Polarized rules does not, a priori, guarantee a valid neighbor of c to continue a route for every c, s, and t. The switch c is denoted as a corner relative to s and t if there is no neighbor of c satisfying the changes in the distance tuples allowed by the algorithm. To employ it successfully, the absence of such corners is required. In the case of random topologies, such as MRLS, the probability of having a corner is negligible in practical cases. Nevertheless, all pairs (s, c) can be checked, and the MRLS can be re-rolled if any corner is found. Polarized routing also benefits from the leaf-spine structure by selecting routes with low maximum length, the same as in Valiant routing [30] and other non-minimal mechanisms. It is proved in Theorem 4.2 that the maximum length of the routes is upper bounded by twice the diameter 2D.
Two approaches are considered: K-Shortest Paths (KSP) algorithm [27], and Polarized routing [28]. In both routing mechanisms, a penalty is applied to nonminimal routes so that minimal routes are preferred. 4.3.1
K-Shortest Paths (KSP)
In KSP routing, multiple shortest paths are precomputed for each source–destination pair. Randomization among paths of equal length proves to be important to balance traffic [27], while an adaptive selection mechanism allows packets to choose their final route dynamically after the first hop. Experiments show improvements when increasing the value of K, the number of shortest paths included in the routing table for each source/destination pair. For the simulation, K = 250 is employed, though further improvement is still possible. Even tables with K = 8 (cf. [22]) pose problems to use them in actual switches [29]. This optimistic value is used for a better comparison with Polarized routing. 4.3.2
Polarized routing
Polarized routing is an adaptive, non-minimal algorithm conceived as a topology-agnostic solution for direct networks [28]. Next, it is adapted to indirect random networks, showing great advantages when using it in particular topologies such as MRLS. 7
• Indirect Networks (FT and OFT): Using a switch radix of 36, we evaluated an 11K-endpoint scale (both FT and OFT) and a 100K-endpoint scale (using a 50% depopulated 4-level FT).
Theorem 4.2. The routes provided by Polarized routing in a leaf-spine network have a length k satisfying k ≤ 2D∗ − 2 ≤ 2D.
• Dragonfly Networks (DF and DF+ [32]): Using a switch radix of 32, we evaluated a 16Kendpoint scale (full-sized DF, and DF+ with a global trunking of 4).
Proof. Consider a Polarized route from source s to destination t, both leaf switches. In a network with levels, there are no links that lead to another switch at the same distance. This entails that for a current switch c, any Polarized hop will move away from s when d(s, c) < d(c, t) and toward t otherwise. Denote by m the first switch in the route with d(s, m) ≥ d(m, t), that is, the middle switch. It is clear that d(s, m) − d(m, t) ≤ 1, as it cannot change by more than 2 at each hop. Furthermore, as s and t are both leaf switches, d(s, m) ≡ d(m, t) (mod 2), leading to d(s, m) = d(m, t). Call l = d(s, m). Let p be the previous switch to m in the route, it has d(s, p) = l ± 1 and d(p, t) = l ± 1. If it were d(s, p) = l + 1 then d(s, p) = l + 1 ≥ d(p, t) = l ± 1, contradicting m being the first such switch. The same contradiction happens if d(p, t) = l − 1. Thus, d(s, p) = l − 1 and d(p, t) = l + 1, implying l + 1 ≤ D∗ . By the preceding argument, the route is minimal from s to p and from m to t. This yields a length of k = (l − 1) + 1 + l = 2l ≤ 2(D∗ − 1).
At each scale, one or more MRLS configurations are adapted to match the number of endpoints of the compared topologies, while also ensuring a similar or lower cost in terms of links per endpoint. State-of-the-art adaptive routing algorithms were utilized for all topologies. Polarized routing performs exceptionally well on MRLS; however, it is less effective (or requires extensive modifications) for DF and DF+. Thus, we employ the standard UGAL and FPAR mechanisms for the Dragonfly networks. Additionally, depending on the technology used, DF networks may achieve lower real-world costs by utilizing cheaper electrical cables for short links, a factor ignored in this simplified cost model defined in Equation (2). The details of the simulated topologies are presented in Table 2.
5.2
5
Evaluations were conducted under three distinct synthetic traffic models:
Experimental Setup
1. Throughput (Max Injection Rate): Uses Bernoulli equal-sized messages across four traffic patterns: Uniform (UN), Random Endpoint Permutation (REP), Random Switch Permutation (RSP—a highly adverse pattern), and Bipartite Uniform (BU), a pattern which models typical communication in a DC divided into two halves: one containing caches or directories, and the other accessing uniform data within them.
To compare the performance of the different topologies we employ CAMINOS [31], an event-driven network simulator that operates at the flit level and accurately models the microarchitecture of network switches. The switch operates with a 2× speedup and a random allocator, and each packet consists of 16 flits. It provides buffer space for 8 packets per virtual channel (VC) at the input ports and 4 packets per VC at the output ports. The MRLS networks are configured with the minimum number of VCs required to guarantee deadlock freedom—specifically, 3 or 4 VCs for maximum hop bounds of 6 or 8, respectively. In each comparison, the baseline topologies are initially provisioned with an equivalent number of VCs. However, because MRLS routing rarely reaches its maximum hop bound in practice, the competing topologies are generally allocated one fewer VC during the majority of the simulations. The exception to this configuration are the Dragonfly topologies, which are consistently equipped with 4 VCs 2 .
5.1
Traffic scenarios
2. Tail Latency (Mice and Elephant Flows): Measures up to the 99.99th percentile packet latency of uniform traffic at a load of 0.5 flits/cycle. Other load values have been evaluated as well, showing similar trends, but we omit them for brevity. To model real-world environments, traffic is split into mice flows (1-packet messages; 90% of total messages, 10% of volume) and elephant flows (16-packet messages; 10% of total messages, 90% of volume). 3. AI/HPC Collectives: Evaluates All2All and Allreduce operations:
Evaluated Networks
• All2All: Tasks are scaled to the minimum endpoints available per scale (11,052; 16,512; and 104,976 tasks).
We evaluate the MRLS topology against two distinct families of network architectures considering three different number of servers:
• Allreduce: Uses Rabenseifner’s algorithm [33], which requires power-of-two task counts (8,192; 16,384; and 65,536 tasks). This scenario inherently favors structured
2 Resources
to fully reproduce our experiments, including the experimental setup and the MRLS topology files, are available at https://github.com/alexcano98/ MRLS-topology-reproducibility.git
8
Table 2: Parameters of the evaluated topologies. Topology(R,S)
Notes
Costlinks
Costswitches
Routing
MRLS(36, 11052) MRLS(36, 11052) MRLS(36, 11664) MRLS(36, 104976) MRLS(36, 104976) MRLS(36, 104976) MRLS(32, 16640) OFT(36, 11052) FT(36, 11664) FT(36, 104976) DF+(32, 16640) DF(32, 16512)
u = 18 u = 21 u = 24 u = 18 u = 24 u = 27 u = 19 q = 17 h=2 50% pop. 65 groups 129 groups
1 1.4 2 1 2 3 1.462 1 2 3 1.5 1.5
0.083 0.106 0.139 0.083 0.139 0.194 0.122 0.083 0.139 0.222 0.127 0.125
Pol and KSP Pol Pol Pol Pol Pol Pol Pol MIN MIN FPAR UGAL
MRLS KSP
MRLS Pol
OFT
0.4 0.2 0
1
1.4
0.5
0
2
Max Hops (99% / bound) 4/6 4/6 4/6 6/8 6/8 6/8 4/6 4 4 6 6 6
4 4 4 4 4 4 4 2 4 6 3 3
Fat-Tree Bipartite Uniform
1
throughput
throughput
throughput
0.6
11052 11052 11664 104976 104976 104976 16640 11052 11664 104976 16640 16512
Random Switch Permutation
Random Endpoint Permutation 1
0.8
Diameter
1
Costlinks
1.4
throughput
Uniform
Endpoints
0.5
0
2
1
Costlinks
1.4
0.8 0.6 0.4 0.2 0
2
1
Costlinks
1.4
2
Costlinks
Throughput for different traffic patterns.
Percentile
99.99%
OFT cost 1 MRLS cost 1 MRLS cost 1.4 FT cost 2 MRLS cost 2
99.9% 99% 90%
6 4 2 0
0% 0
100
200
300
400
500
600
700
·105
All2All Cycles to finish
Cycles to finish
·105
800
1
1.4
2
AllReduce
6
4
2
0
1
Costlinks
Latency (Cycles)
Tail latency for mice and elephant flows.
1.4
2
Costlinks
Collectives evaluation
Figure 5: Comparison of indirect networks connecting 11k endpoints. topologies like FT, whose hypercube mapping facilitates the some locality characteristic of the algorithm. Additionally, message sizes vary between steps, and a substantial portion of the traffic is exchanged between endpoints connected to the same switch.
6
Experimental Results
6.1
Networks of 11K endpoints
6.1.1
Throughput evaluation
It can be observed that for the same cost, the MRLS topologies yield very similar performance to the OFT. While KSP routing in MRLS achieves similar performance to Polarized routing under most traffic patterns, its throughput drops by 26% under the more challenging RSP traffic. Consequently, the remainder of our evaluation focuses on Polarized routing for MRLS due to its higher efficiency and robustness. For the more expensive configurations (MRLS with costs of 1.4 and 2.0, alongside the FT), throughput for UN and BU traffic is nearly identical, though MRLS holds a marginal advantage. Under REP traffic, the cost-2 MRLS outperforms the FT by 11%, and the cost-1.4 MRLS by 24%. Similarly, for the more challenging RSP traffic, the cost-2 MRLS outperforms the FT by 6%, and the cost-1.4 MRLS by 40%. The FT is a full-bisection bandwidth network with Θ = 1, which theoretically allows it to deliver maxi-
In this subsection, we evaluate one OFT, one FT, and three MRLS networks from Table 2, all of them comprising approximately 11K endpoints. Additionally, an MRLS configuration using KSP routing is evaluated to provide a comparison against Polarized routing. Results for the 11K-endpoint networks are presented in Figure 5. 9
Θ
0.748 1.029 1.420 0.527 1.048 1.561 0.900 1 1 1 1 1
MRLS
0.8 0.6 0.4 0.2 0
1
2
0.5
0
3
Random Switch Permutation
1
2
0.5
0
3
1
Costlinks
Costlinks
2
Bipartite Uniform
1
1
throughput
throughput
throughput
Random Endpoint Permutation 1
throughput
Uniform
1
Fat-Tree
0.8 0.6 0.4 0.2 0
3
1
2
3
Costlinks
Costlinks
Throughput for different traffic patterns.
Percentile
99.99% 99.9%
FT MRLS cost 1 MRLS cost 2 MRLS cost 3
99% 90%
6
4
2
0
0% 0
200
400
600
800
·105
All2All Cycles to finish
Cycles to finish
·105
1,000
Latency (Cycles)
Tail latency for mice and elephant flows.
1
2
3
AllReduce
6
4
2
0
1
Costlinks
2
3
Costlinks
Collectives evaluation
Figure 6: Comparison of indirect networks connecting 100k endpoints. mum throughput across all traffic patterns. While the analogous MRLS lacks a formal proof of being rearrangeably non-blocking, its higher capacity (Θ) reduces blocking across the fabric in practice, yielding an average speedup of 7.1%. Notably, doubling the cost does not yield proportional throughput gains for UN and BU patterns, indicating that the network becomes over-provisioned for these workloads.
6.2.1
Throughput evaluation
It can be observed that for the same cost, MRLS yields 4%–7% higher throughput than the FT. In this case, Θ(MRLS) = 1.561 > Θ(FT) = 1, suggesting that with ideal forwarding, a maximum throughput of 1.0 could be achieved. In practice, sporadic contention occurs, but it is less frequent in MRLS due to its higher capacity. Nevertheless, MRLS is over-dimensioned at f = 3; 6.1.2 Mice and elephant flows evaluation employing f = 2 yields comparable performance for Regarding tail latency, the OFT and its equivalent most traffic. Specifically, this 33% reduction in cost inMRLS perform nearly identically. However, the gap curs only a 4% penalty in Uniform throughput, though between the FT and its comparable MRLS widens con- the performance penalty reaches 27% under the more siderably, with the FT exhibiting a roughly 30% in- demanding switch permutation traffic. Below a cost of 2, MRLS throughput scales proportionally with cost crease in packet latency. across all traffic patterns (cf. [34]). Indeed, reducing the cost by 50% (from f = 2 to f = 1) results in a 6.1.3 Collectives evaluation throughput ratio between 0.48 and 0.52. For both collectives, the comparable MRLS and OFT perform similarly, exhibiting only a 2%–3% difference 6.2.2 Mice and elephant flows evaluation in completion time. Conversely, the cost-2 MRLS outperforms the FT by 17% in the All2All operation, Tail latency metrics indicate that the MRLS with f = 1 whereas the FT outperforms MRLS by 10% in the performs considerably worse than the other configuraAllreduce. The FT’s superiority in Allreduce stems tions, as it becomes saturated under the evaluated load. from the strong locality of this communication pat- The remaining topologies exhibit very similar latencies, tern, which inherently benefits from the FT’s hierar- with the f = 3 MRLS showing a slight advantage. chical structure and its higher number of endpoints per switch. Furthermore, the cost-1.4 MRLS matches the 6.2.3 Collectives evaluation All2All performance of the FT while reducing the cost by 30%, although it remains 10% slower in the Allre- The collective performance trends at 100K endpoints duce operation. closely mirror those observed at 11K. MRLS is significantly faster for the All2All operation (by 48%), whereas the FT excels in the Allreduce operation (by 6.2 Networks of 100K endpoints 20%). This highlights that the extra capacity of MRLS In this subsection, we compare one FT against three does not strictly guarantee faster execution times, esMRLS configurations from Table 2, all scaled to 100K pecially for highly structured traffic patterns that benefits other networks. Nevertheless, the proportionality endpoints. The evaluation is presented in Figure 6. 10
Dragonfly+ Uniform
Dragonfly
Random Endpoint Permutation
MRLS
Random Switch Permutation
0.8
Bipartite Uniform
0.4 0.2
0.6 0.4 0.2
0.4
0.2
0.8 0.6 0.4 0.2
0
0
0
throughput
0.6
throughput
throughput
throughput
0.6 0.8
0
Throughput for different traffic patterns.
Dragonfly+ Dragonfly MRLS
99% 90% 0% 0
200
400
600
800
Cycles to finish
Percentile
99.9%
6 4 2 0
Latency (Cycles)
Tail latency for mice and elephant flows.
·105
All2All Cycles to finish
·105
99.99%
AllReduce
1.5
1
0.5
0
Collectives evaluation
Figure 7: Comparison of a MRLS against current top direct networks. All connect 16k endpoints with Costlinks ≤ 1.5. of throughput to cost holds true in the All2All, providing superior performance per cost when the thickness factor f is adequately chosen.
capacity bottleneck affects all intra-group traffic. As a result, even a balanced network with Θ = 1 suffers severe performance degradation when traffic is not perfectly distributed across global links. The same effect occurs in RSP and REP, the latter to a lesser extent. 6.3 Comparison with Dragonfly net- This demonstrates that Dragonfly networks are highly works sensitive to the specifics of process allocation; thereIn this subsection, the performance of MRLS is com- fore, an optimal application placement would improve pared against DF and DF+ topologies. The results their performance on this benchmark. for these networks are displayed in Figure 7. The DF networks feature a diameter of 3 and a small average 6.3.2 Mice and elephant flows evaluation distance, reflecting a cost of Costlinks ≈ 1.5. They The tail latency evaluation shows that MRLS outperare compared against an MRLS configuration with an forms standard DF, while DF+ exhibits slightly better equivalent cost (f = Costlinks = 1.46). tail latency than MRLS. In principle, this is a disadvantageous scenario for MRLS, as its routing paths cannot have an odd integer length. When adjusting the MRLS to Dragonfly sizes, 6.3.3 Collectives evaluation this limitation is reflected in its relatively low Θ = For the collective operations, MRLS demonstrates 0.900. vastly superior performance. In the All2All operation, MRLS is approximately 100% faster than both Dragonfly variants. For the Allreduce operation, MRLS is 50% faster than DF and 12% faster than DF+. While The MRLS outperforms both Dragonfly variants across the direct nature of Dragonfly networks assists them all traffic patterns while maintaining a similar links- in Allreduce, MRLS remains overwhelmingly superior per-endpoint ratio. For Uniform traffic, it yields 14% for global All2All communication. This is once again and 19% higher throughput than DF+ and DF, respec- caused by the inherent global bottleneck of Dragonfly tively. These performance gaps widen further under topologies. the other traffic patterns. The Bipartite Uniform (BU) traffic pattern is particularly noteworthy. While all indirect networks main- 7 Conclusions tained similar performance for both UN and BU traffic, Dragonfly networks struggle here. In a BU scenario, Due to its high cost, alternatives to the Fat-Tree must where half the racks act as clients and the other half be considered to achieve extreme scalability. Networks as caches, relying on minimal routes severely limits the such as OFT have demonstrated their ability to internumber of usable global links in a Dragonfly topol- connect a huge number of endpoints. However, they ogy. To exploit the full global capacity, these networks are tied to very specific sizes and their capacity for exmust use longer, non-minimal routes, a requirement pansion is extremely limited. In contrast, MRLS netthat does not arise under Uniform traffic. This global works are expandable and can accommodate virtually 6.3.1
Throughput evaluation
11
any number of endpoints. They enable a trade-off between scalability and performance, interconnecting a massive number of nodes without significant degradation. Furthermore, MRLS networks (and OFT) require routing algorithms that support non-minimal paths to handle adverse traffic efficiently. Challenges like its physical layout and implementation remain and merit further research for adoption in large-scale DCs. The MRLS achieves a 50% speedup against a Fat-Tree for an All2All collective comprising 100k endpoints, and 100% against Dragonfly networks for the same collective.
12
References
the ACM SIGCOMM 2009 Conference on Data Communication, ser. SIGCOMM ’09. New York, NY, USA: Association for Computing Machinery, 2009, p. 63–74. [Online]. Available: https://doi.org/10.1145/1592568.1592577
[1] J. Lin, S. Hu, Z. Lu, and R. Deng, “An analysis and comparison of the development status of green data centers in China,” in 2023 IEEE 8th International Conference on Smart Cloud (SmartCloud), IEEE. IEEE Computer Society, 2023, pp. 130– [12] C. E. Leiserson, “Fat-trees: Universal networks for hardware-efficient supercomputing,” IEEE Trans135. actions on Computers, vol. C-34, no. 10, pp. 892– [2] SemiAnalysis, “Top 10 largest AI datacenters 901, 1985. in 2026,” https://www.youtube.com/watch?v= [13] C. Clos, “A study of non-blocking switching a-9egkpaZUw, Jan. 2026. networks,” The Bell System Technical Journal, [3] K. F. Pilz, J. Sanders, R. Rahman, and L. Heim, vol. 32, no. 2, pp. 406–424, 1953. “Trends in AI supercomputers,” arXiv preprint arXiv:2504.16026, 2025. [14] S. Kamil, L. Oliker, A. Pinar, and J. Shalf, “Communication requirements and interconnect [4] TOP500 Team, “Top500: The list,” https://www. optimization for high-end scientific applications,” top500.org/, 2025. IEEE Transactions on Parallel and Distributed Systems, vol. 21, no. 2, pp. 188–202, Feb. 2010. [5] J. Kim, W. J. Dally, S. Scott, and D. Abts, “Technology-driven, highly-scalable dragonfly [15] E. A. León, I. Karlin, A. Bhatele, S. H. Langer, topology,” in 2008 International Symposium on C. Chambreau, L. H. Howell, T. D’Hooge, and Computer Architecture. IEEE Computer Society, M. L. Leininger, “Characterizing parallel scien2008, pp. 77–88. tific applications on commodity clusters: An empirical study of a tapered fat-tree,” in SC ’16: [6] M. Valerio, L. Moser, and P. Melliar-Smith, Proceedings of the International Conference for “Fault-tolerant orthogonal fat-trees as interconHigh Performance Computing, Networking, Stornection networks,” in Proceedings 1st Internaage and Analysis, Nov. 2016, pp. 909–920. tional Conference on Algorithms and Architectures for Parallel Processing, vol. 2, IEEE. IEEE [16] A. Jokanovic, J. C. Sancho, J. Labarta, G. RoComputer Society, 1995, pp. 749–754. driguez, and C. Minkenberg, “Effective qualityof-service policy for capacity high-performance [7] G. Kathareios, C. Minkenberg, B. Prisacari, computing systems,” in 2012 IEEE 14th InternaG. Rodriguez, and T. Hoefler, “Cost-effective tional Conference on High Performance Computdiameter-two topologies: analysis and evaluaing and Communication 2012 IEEE 9th Internation,” in SC ’15: Proceedings of the International Conference on Embedded Software and Systional Conference for High Performance Computtems, Jun. 2012, pp. 598–607. ing, Networking, Storage and Analysis. Association for Computing Machinery, 2015, pp. 1–11. [17] J. Navaridas, J. Miguel-Alonso, F. J. Ridruejo, [8] C. Camarero, C. Martı́nez, and R. Beivide, and W. Denzel, “Reducing complexity in tree“Random folded Clos topologies for datacenter like computer interconnection networks,” Parallel networks,” in 2017 IEEE International Sympocomputing, vol. 36, no. 2-3, pp. 71–85, 2010. sium on High Performance Computer Architecture (HPCA). IEEE Computer Society, 2017, pp. 193– [18] A. Singla, P. B. Godfrey, and A. Kolla, “High throughput data center topology design,” in 11th 204. USENIX Symposium on Networked Systems De[9] C. Camarero, C. Martı́nez, E. Vallejo, and R. Beisign and Implementation (NSDI 14). USENIX: vide, “Projective networks: Topologies for large The Advanced Computing Systems Association, parallel computer systems,” IEEE Transactions 2014, pp. 29–41. on Parallel and Distributed Systems, vol. 28, no. 7, [19] A. J. Hoffman and R. R. Singleton, “On Moore pp. 2003–2016, 02 2017. graphs with diameters 2 and 3,” IBM Journal of [10] M. Besta and T. Hoefler, “Slim Fly: A cost effecResearch and Development, vol. 4, no. 5, pp. 497– tive low-diameter network topology,” in SC ’14: 504, 1960. Proceedings of the International Conference for High Performance Computing, Networking, Stor- [20] W. Dally and B. Towles, “Principles and practices of interconnection network,” 01 2004. age and Analysis. IEEE Computer Society, 2014, pp. 348–359. [21] S. Zhao, R. Wang, J. Zhou, J. Ong, J. C. Mogul, [11] C. Guo, G. Lu, D. Li, H. Wu, X. Zhang, Y. Shi, and A. Vahdat, “Minimal rewiring: Efficient live C. Tian, Y. Zhang, and S. Lu, “BCube: a high expansion for Clos data center networks,” in 16th performance, server-centric network architecture USENIX Symposium on Networked Systems Defor modular data centers,” in Proceedings of sign and Implementation (NSDI 19). USENIX: 13
The Advanced Computing Systems Association, 2019, pp. 221–234.
3rd International Workshop on High-Performance Interconnection Networks in the Exascale and BigData Era (HiPINEB). IEEE, 2017, pp. 1–8.
[22] A. Singla, C.-Y. Hong, L. Popa, and P. B. Godfrey, “Jellyfish: networking data centers randomly,” in [33] R. Thakur, R. Rabenseifner, and W. Gropp, “OpProceedings of the 9th USENIX Conference on timization of collective communication operations Networked Systems Design and Implementation, in mpich,” The International Journal of High Perser. NSDI’12. USA: USENIX Association, 2012, formance Computing Applications, vol. 19, no. 1, p. 17. pp. 49–66, 2005. [23] C. Camarero, C. Martınez, and R. Beivide, “On [34] S. Kassing, A. Valadarsky, G. Shahaf, random wiring in practicable folded Clos networks M. Schapira, and A. Singla, “Beyond fatfor modern datacenters,” IEEE Transactions on trees without antennae, mirrors, and disco-balls,” Parallel and Distributed Systems, vol. 29, no. 8, in Proceedings of the Conference of the ACM pp. 1780–1793, 2018. Special Interest Group on Data Communication, 2017, pp. 281–294. [24] A. Steger and N. C. Wormald, “Generating random regular graphs quickly,” Combinatorics, [35] N. Kan, “Martingale approach to the coupon colProbability and Computing, vol. 8, no. 04, pp. 377– lection problem,” Journal of Mathematical Sci396, 1999. ences, vol. 127, no. 1, pp. 1737–1744, 2005. [25] C. Camarero, J. Corral, C. Martı́nez, and R. Beivide, “Modelling standard and randomized slimmed folded Clos networks,” in European Conference on Parallel Processing, Springer. Springer, 2020, pp. 185–199. [26] B. Bollobás, Random Graphs, 2nd ed. Cambridge studies in advanced mathematics, 2001. [27] Z. ALzaid, S. Bhowmik, and X. Yuan, “Multipath routing in the Jellyfish network,” in 2021 IEEE international parallel and distributed processing symposium workshops (IPDPSW), IEEE. IEEE Computer Society, 2021, pp. 832–841. [28] C. Camarero, C. Martı́nez, and R. Beivide, “Polarized routing: an efficient and versatile algorithm for large direct networks,” in 2021 IEEE Symposium on High-Performance Interconnects (HOTI). IEEE Computer Society, 2021, pp. 52– 59. [29] G. Bernardi, R. Mahajan, C. Seshadhri, E. Carlesso, C. M. Joseph, S. Kumar, P. Manikonda, L. Popa, R. Ram, S. Robinson, and E. Tennent, “Expanding into reality: Random graphs for datacenter networks,” arXiv preprint arXiv:2604.15261, 2026. [30] L. G. Valiant, “A scheme for fast parallel communication,” SIAM Journal on Computing, vol. 11, no. 2, pp. 350–361, 1982. [Online]. Available: https://doi.org/10.1137/0211027
A
Average Distance and Probabilities
This appendix explains the mathematical details behind the graphs shown in Figures 3 and 4. Most of Figure 3 can be estimated experimentally by generating many networks near the thresholds and measuring the probability of obtaining a given D∗ . Indeed, we have also done that for the first three thresholds. Deriving analytical expressions that accurately match these measurements makes it possible to extrapolate to much larger network sizes. The same expressions also enable the construction of Figure 4, which would be otherwise unfeasible due to the vast amount of topologies to generate. The main issue at hand is an accurate estimation of the distance distribution. Afterwards, the average distances A and A∗ can be computed. Furthermore, additional details are provided to obtain the probability that separates the regions corresponding to different values of D∗ . Our focus is on accurate predictions for realistic network sizes, where asymptotic approximations such as those in [8] perform poorly. In Figure 3, such approximations could lead to important deviations. In contrast, the approximations presented here match the experimental data precisely. For statistical notation, we denote the probability of an event E by P [E], the conditional probability given condition C by P [E|C], the expected value of a random variable V by E[V ], and the conditional expectation of the random variable V given a predicate C by E[V |C].
[31] C. Camarero, D. Postigo, and P. Fuentes, “The CAMINOS interconnection networks simulator,” Journal of Parallel and Distributed A.1 Distance Distribution Computing, vol. 204, p. 105136, 2025. [Online]. Available: https://www.sciencedirect.com/ Denote by Sr (c) the sphere of switches at distance exactly r from a switch c, the center. The cardinalities science/article/pii/S0743731525001030 of these spheres form the distance distribution. As we [32] A. Shpiner, Z. Haramaty, S. Eliad, V. Zdornov, are dealing with random topologies, the sequence varies B. Gafni, and E. Zahavi, “Dragonfly+: Low cost depending on the chosen center. Nevertheless, from a topology for scaling datacenters,” in 2017 IEEE probabilistic point of view there are only two sequences 14
(i = 1, 2): nir = E[|Sr (c)| | c is a switch at level i]. The sequence n1r is enough to compute A, both are required to determine the D∗ regions. We employ i = 1, 2 for coherence with Table 1. At some point we employ arithmetic modulo 2, which must be understood as i + r = 1 + rem(1 + i + r, 2) = j, the value j = 1, 2 with i + r ≡ j (mod 2). We also employ, for a switch c at level i, the ball Br (c) containing those switches at the level r + i that are at distance r or lower from c. Define the analogous sequences bir = E[|Br (c)|c is a switch at level i]. Note that nir ≤ bir ≤ Nr+i and, for r ≥ 2, nir = bir − bir−2 . The first values are obtained directly from the regularity of MRLS, n10 = n20 = b10 = b20 = 1, n11 = b11 = u, and n21 = b22 = R. Afterwards, we deal with Br (c) as if it were the neighborhood of an arbitrary set. This is, for 1 ≤ r, Br (c) = N (Br−1 (c)), S where the neighborhood N is defined as N (X) = a∈X S1 (a). Therefore,
threshold separating k − 1 from k + 1 for the maximum distance between switches at the corresponding levels. Asymptotically, it is unimportant which pair i, j to choose. However, such a decision can lead to small but appreciable errors. The most precise choice appears to be i = 1 and s a leaf switch. Note how this forces the intersection to occur at the spine level. For the calculation of the actual threshold we need to consider all pairs. Hence, let G be the total count of possible pairs. That is, let G = N21 when both s and t are leaf (even distance) and G = N1 N2 otherwise. Let λ be the expected number of pairs (s, t) with S1 (s) ∩ Sk−2 (t) = ∅. Writing λ in terms of the probability of intersection of the considered spheres, λ = GP [S1 (s) ∩ Sk−2 (t) = ∅ | s leaf, t leaf if k odd, spine if k even].
(7)
This gives the probability of having a diameter below (5) a given k, 1 λ where η i (x) = E[|N (X)| | |X| = . (8) P [D∗ ≤ k] = (1 − )G = exp −λ + O x, all switches of X are at level i]. G G Estimating the value of |N (X)| is a variant of the Some remarks are needed regarding the probability coupon collector problem. In particular, as a consethat S1 (s) and Sk−1 (t) have an empty intersection, quence of Theorem 2.1 in [35] it can be shown that which is considered next. xni1 . (6) η i (x) = Ni+1 1 − exp − Ni+1 A.3 Probability for Empty Intersection bir+1 = η i+r (bir ),
Then, iterating (5) provides the expected count of switches at every distance. For the average distance, take only even distances starting at a leaf switch, this is, ⌊D/2⌋ X 1 A= 2in12i . N1 − 1 i=1
To calculate the probability in (7) we need to consider the size for X = S1 (s) and Y = Sk−2 (t). This is the distance distribution estimated in previous subsection A.1. Consider the probability that two random sets X, Y ⊂ Ω have empty intersection. For convenience, we take x = |X|, y = |Y | and n = |Ω|. Let us consider In the same way, A∗ can also be computed. In Ω and Y to be fixed, and count the ways that X could this case, without skipping any term and starting be made. From the n elements of Ω choose x to form from both leaf and spine switches. Therefore, A∗ = X. The set X ∩ Y is empty when these x choices are PD∗ taken over the n − y elements of Ω \ Y , that is: (N − 1)−1 kn1 + kn2 . k=1
A.2
k
k
Threshold Function for D∗
P [X ∩ Y = ∅] =
A key figure of random networks is the value at which the diameter increases. In [26] functions that separate a property such as the diameter are denoted as threshold functions. That is an asymptotic definition and thus lies outside the scope of our focus. Let us consider a pair of switches s and t, and their distance δ = d(s, t). Then t ∈ Sδ (s) and s ∈ Sδ (t). Furthermore, for any 0 ≤ i, j ≤ δ with i + j = δ, Si (s)∩Sj (t) contains those switches that belong to any minimal path and are at the indicated step. Hence, to consider the diameter threshold, our aim is to determine whether Si (s) ∩ Sj (t) is empty or not. To obtain the threshold separating D∗ = k from ∗ D = k + 1 we consider a pair i, j with 0 ≤ i, j ≤ k − 1 and i + j = k − 1. If some candidates s, t fail to be within distance k − 1, then d(s, t) ≥ k + 1. Note that it cannot be k due to parity. In other words, it is the 15
n−y x n x
=
(n − x)!(n − y)! (n − x − y)!n!
(9)
This expression is symmetric in x and y, and therefore in X and Y , as it can be observed in the right side of (9). Using equations (5),(6),(7),(8),(9) yields values that fit experimental data, such as those drawn in Figure 3.