Towards an Efficient Combination of Adaptive Routing and Queuing Schemes in Fat-Tree Topologies

Jose Rocher-Gonzalez, Jesus Escudero-Sahuquillo, Pedro J. Garcia, Francisco J. Quiles, Gaspar Mora · 2025

Read Towards an Efficient Combination of Adaptive Routing and Queuing Schemes in Fat-Tree Topologies by Jose Rocher-Gonzalez, Jesus Escudero-Sahuquillo, Pedro J. Garcia, Francisco J. Quiles, Gaspar Mora (2025) 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-2502-00597.txt.

Introduction

Jose Rocher-Gonzalez and co-authors work on combining two congestion tools for the fat-tree networks that link supercomputers. Their 2025 paper starts from the fat-tree shape, which offers many equal routes between any two nodes. Multi-path routing can spread traffic across those routes and lower congestion.

A second tool separates flows into queues, yet the authors' earlier work showed spreading can backfire by scattering congested flows across queues. Their proposal adds restrictions on how alternative routes are chosen, so spreading and queue separation reinforce rather than fight each other. The target is a network that handles the bursty traffic of computing centers without hot spots. The work is a design step toward pairing the two schemes in real machines.

Catalog record

CREATORJose Rocher-Gonzalez, Jesus Escudero-Sahuquillo, Pedro J. Garcia, Francisco J. Quiles, Gaspar Mora
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE72 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-00597

Browse the full library · About the Tower of Babel

Full text

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

Towards an Efficient Combination of Adaptive Routing and Queuing Schemes in Fat-Tree Topologies Jose Rocher-Gonzalez, Jesus Escudero-Sahuquillo, Pedro J. Garcia, Francisco J. Quiles, Gaspar Mora Abstract The interconnection network is a key element in High-Performance Computing (HPC) and Datacenter (DC) systems whose performance depends on several design parameters, such as the topology, the switch architecture, and the routing algorithm. Among the most common topologies in HPC systems, the Fat-Tree offers several shortest-path routes between any pair of end-nodes, which allows multi-path routing schemes to balance traffic flows among the available links, thus reducing congestion probability. However, traffic balance cannot solve by itself some congestion situations that may still degrade network performance. Another approach to reduce congestion is queue-based flow separation, but our previous work shows that multi-path routing may spread congested flows across several queues, thus being counterproductive. In this paper, we propose a set of restrictions to improve alternative routes selection for multi-path routing algorithms in Fat-Tree networks, so that they can be positively combined with queuing schemes. Journal: Journal of Parallel and Distributed Computing 1 Motivation Nowadays, interconnection networks have become key elements in High-Performance Computing (HPC) and Datacenters (DC) systems, where they connect thousands of computing and storage nodes. Therefore, the global performance of any HPC or DC system is directly coupled with the performance of its interconnection network. This makes critical to carefully design all the aspects of the interconnection network such as the topology, routing, power efficiency, etc. so that the network is not the bottleneck of the whole system. One key design aspect of interconnection networks is the topology. Efficient topologies should offer full connectivity, cost-effectiveness, high-bisection bandwidth, path diversity, etc [ 1 ] . The properties of a given topology should be leveraged by efficient routing algorithms, mainly balancing traffic among the available paths, in order to reduce the probability of hot-spot appearance. Fat-Trees are one of the two most common topologies in the supercomputers of the TOP500 list [ 2 ] . In particular, Fat-Trees offer full bisection bandwidth, inherent fault tolerance capabilities, and path diversity, among other advantages. Moreover, their structure is naturally deadlock-free between any pair of end-nodes. These features are leveraged by several efficient routing algorithms, either deterministic [ 3 ] oblivious [ 4 ] or adaptive [ 5 , 6 , 7 ] . However, even in networks with efficient topologies and routing algorithms, congestion may appear due to packet flows intensely and persistently contending to use the network resources, then severely degrading network performance. In the lossless networks used in HPC and DC systems, congestion spreads due to the backpressure of flow control, forming what is known as a “congestion tree” [ 8 ] , that grows from the point where congestion originates (the root) towards the end-nodes (leaves). Note that congestion is favored by “many to one" traffic patterns, i.e., by oversubscribed end-nodes (“incast” congestion), but also by flows contending at the inner network (“in-network” congestion). Regardless its origin, congestion may lead to non-congesting flows advancing at the same pace as congesting ones, due to the Head-of-Line (HoL) blocking effect [ 9 ] . In general, HoL blocking happens when a packet stuck at the head of a buffer or queue blocks the packets stored behind in that queue, even if the latter request free resources. This effect is especially severe in lossless networks, where congesting packets cannot be discarded, hence they cause HoL blocking to non-congesting ones if they share queues. Moreover, in lossless networks HoL blocking may appear either at the switch where congestion originates ( low-order HoL blocking [ 9 ] ) or at other switches, due to the backpressure of flow control from that switch ( high-order HoL blocking [ 10 ] ). Another negative effect of congestion is buffer hogging [ 11 ] which appears when congesting packets hog all the the space of a given buffer. Among the solutions proposed to deal with congestion and its effects, several techniques implemented in real systems are based on throttling packet injection at the sources upon congestion notification [ 12 , 13 ] . However, they do not scale with network size because the notification delay depends on the network diameter, so the sources may react too late, or receive obsolete information [ 14 ] . Other methods proposed recently [ 15 , 16 ] use speculative messages that can be dropped under a congestion scenario, combined with a reservation handshake protocol between source and destination end-nodes. Another efficient and simple approach to reduce the effects of congestion is separating packet flows into different queues (or Virtual Channels [ 17 ] ) at each switch port. In this way, the sharing of buffer space among congesting and non-congesting flows may be reduced, and so the HoL blocking. This queue-based flow-separation approach is followed by many proposals, usually known as queuing schemes , that differ on the specific policy followed to map flows to queues. The most prominent of them are analyzed in Section 2.3 . Besides, the use of multi-path (oblivious or adaptive) routing has been considered to deal with congestion. Actually, in some cases these routings may hinder the formation of congested points, but they may also be useless, like in incast congestion situations. Moreover, these routings may lead to dynamic changes in the shape of congestion trees, making them more difficult to solve by other congestion management mechanisms that may be active simultaneously. In that regard, we performed a previous study on the combination of multi-path routing algorithms with some popular queuing schemes in Fat-Trees [ 18 ] . In that study, the experiment results show how multi-path routings spread congestion trees throughout the network under heavy congestion scenarios, such that a higher number of queues are affected. Indeed, some combinations of queuing schemes with multi-path routings are counterproductive, as they are outperformed by deterministic routing. Based on that preliminary study, this paper further explores several ways to restrict the set of routes that can be selected by adaptive routing, analyzing how this impacts on the spreading of congestion trees, on the efficiency of queuing schemes, and ultimately, on network performance. In summary, the main contributions of this paper are: 1. We propose restrictions to the path selection of adaptive routing, such as limiting adaptivity to a given network stage, reducing the set of output ports that can be selected, or modifying the threshold of queue occupancy that triggers adaptivity. 2. We study how the combined use of several of these restrictions makes the network to behave better. 3. We analyze the impact of applying the proposed restrictions to multi-path routing on different queuing schemes used to reduce HoL blocking. 4. We evaluate different combination of queuing schemes with restricted adaptive routings under incast and in-network congestion scenarios. The rest of the paper is organized as follows. Section 2 provides some background on Fat-trees, routing algorithms and queuing schemes. Based on our previous work, Section 3 analyzes the problems that arise upon combining adaptive routing with queuing schemes. Section 4 describes the proposed restrictions to adaptive routing. In Section 5 , the proposals are evaluated through simulation results. Finally, we conclude the study in Section 6 . 2 Background 2.1 Fat-Tree

Read the complete text