CS Paper Radar

Rondo: Controlling Reordering in High-Throughput Packet Spraying

Xizhi Zhang, Zhongjie Chen, Yang Zhang, Fengyuan Ren

cs.NI ·submitted 2026-11-03 09:50 UTC · v1

Abstract

Modern datacenter applications demand high network bandwidth, motivating packet-level multipath transport to exploit the aggregate capacity of multiple paths. However, packet reordering under packet spraying poses challenges for hardware transports. Excessive packet reordering makes it difficult to infer packet loss, imposes substantial pressure on NIC resources, and ultimately degrades performance. Existing transports either prioritize throughput without controlling packet reordering, or mitigate reordering by restricting transmissions, which leaves available path capacity unused. In this paper, we identify two fundamental sources of packet reordering: transient inter-path queueing differences caused by control dynamics, and persistent path-delay differences due to path heterogeneity. These observations motivate a joint design of a multipath controller and a packet scheduler to address transient and persistent delay differences, respectively. We present Rondo, a packet-level multipath transport that achieves both high throughput and low packet reordering. Its multipath controller uses ACK-based per-path capacity estimation and probing to maintain stable path loads, while its packet scheduler adjusts packet transmission order to compensate for persistent delay differences. Testbed experiments and large-scale simulations show that Rondo reduces the maximum out-of-order degree by up to 97.5% while maintaining high throughput. With constrained receiver buffers, Rondo achieves up to 8.51 times higher goodput.

Closest papers

Nearest neighbours by meaning across the whole index.

Centrality-Based Deployment of Queue Policies in Acyclic Multipath Routing Networks

cs.NI ·2026-08-25 ·Mahima Gupta, Acquin Biju, Rijul Jain, Dipesh Sharma, Sreelakshmi Manjunath
similarity 0.65
Abstract

Excessive queueing delays constitute a significant impediment to latency-sensitive network applications. Although effective deployment of Active Queue Management (AQM) strategies has been proposed as a necessary solution, deployment remains sparse. This paper studies AQM deployment in a specific class of networks where routers/switches have a topological hierarchy, form acyclic paths, and adopt multipath routing. Our approach rests on the well-established premise that AQM deployment impacts packet-forwarding dynamics in networks carrying TCP flows, thus establishing a direct link between stability and network performance. We use fluid models for TCP and queue dynamics in the network, along with a simple threshold-based queue policy to outline a closed-loop model for the network. Stability analyses reveal that while the network is vulnerable to instability as the average round-trip time (RTT) of the TCP flows increases, it tolerates a much larger RTT without losing stability when the threshold-based AQM is deployed in an appropriate router. We then define a Katz centrality-based metric to choose the most appropriate router for AQM deployment, and argue that doing so ensures the greatest stabilising effect. Finally, packet-level simulations corroborate that the proposed deployment strategy ensures low-latency operation of the network.

0.29

Rethinking Adaptive Routing on Dragonfly

cs.NI ·2026-11-09 ·Ziyu Wang, Dezun Dong, Fei Lei
similarity 0.64
Abstract · 12 pages, 9 figures. Preliminary version. An updated final version will follow, and the source code will be open-sourced

The Dragonfly topology is widely deployed in leading supercomputers, where adaptive routing is crucial for high-performance interconnection. Despite years of research, a dilemma remains: state-of-the-art adaptive routing algorithms achieve excellent performance but demand hardware budgets far beyond what real router chips can afford -- prohibitive buffers, logically dependent floating-point operations, or exhaustive path-set traversals -- whereas realizable algorithms deliver unsatisfactory performance. Furthermore, existing algorithms fail to exploit the abundant almost-minimal paths in Dragonfly: when only the local channels of a minimal path are congested, they reroute packets to significantly longer global non-minimal paths, wasting global bandwidth and increasing latency. To address both limitations, we analyze intra-group path contention and propose the Decoupled Incremental Adaptive Routing (DIAR) algorithm, which decouples routing into global path selection at the source and incremental local detours onto almost-minimal paths, guaranteeing deadlock freedom without additional virtual channels, escape rings, or turn models. Requiring only a few comparators, shifters, adders, and multiplexers, DIAR reduces buffer overhead by up to four orders of magnitude compared with state-of-the-art algorithms, while achieving comparable or superior performance across all evaluated scenarios: relative to the strongest realizable adaptive routing algorithm in each scenario, DIAR improves saturation throughput by up to 30.0% across synthetic traffic patterns and improves performance by up to 34.9% (13.2% on average) across HPC workloads.

0.30

PAISF: A Partially Adaptive In-Order Selection Function for Routing in On-Chip, Inter-Chiplet, and Wafer-Scale Networks

cs.AR cs.NI ·2026-11-17 ·Patrick Iff, Luca Oertig, Andrin Weber, Luca Benini, Torsten Hoefler
similarity 0.63
Abstract

The growing number of compute elements per chip, along with advances such as chiplet systems and wafer-scale integration, drives the need for scalable and efficient routing algorithms for irregular topologies. A routing algorithm consists of a routing function (RF) that ensures deadlock freedom and a selection function (SF) that avoids congestion and, in some cases, guarantees in-order packet delivery. We propose two novel SFs for irregular topologies, ISF and PAISF, which ensure in-order delivery by hashing a packet's entropy value to determine its path. Packets with the same entropy follow the same path and arrive in order. Compared to a deterministic RF, a deterministic SF, and Multi, three alternative in-order delivery strategies, (PA)ISF improves throughput by 15.2% and reduces energy per packet and latency under load by 12.1% and 11.3%, at the cost of a zero-load latency increase by 3.3% on average across workloads and topologies.

0.25

Ordered Chaos: Towards Adaptive Multipath Load Balancing with Precise Fast Loss Detection

cs.NI ·2026-10-30 ·Tommaso Bonato, Ahmad Ghalayini, Nadeen Gebara, Benoit Pit-Claudel, Jiayong Li +7 more
published similarity 0.62
Abstract · To appear in the proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (SC 2026)

Load balancing in best-effort datacenter fabrics faces a tradeoff. Order-preserving schemes such as Equal-Cost Multipath (ECMP) retain loss semantics but use path diversity coarsely, while packet spraying balances load well but removes the ordering signals needed for fast, precise loss detection. We present Ordered Chaos, an end-host design that preserves enough structure for reliable loss detection without giving up fine-grained multipath routing. Reactive Subflow Spraying (RSS) divides each flow into ordered, dynamically routed subflows. Precise Fast Loss Detection (PFLD) combines this ordering with probes to distinguish reordering from congestion, corruption, tail, and retransmission losses within one RTT. Across simulations, AI and HPC workloads, and a DPU prototype, RSS+PFLD improves tail flow completion time by up to $3\times$, eliminates up to 99% of timeout-based recoveries, and accelerates collective and training communication by up to 35%.

0.46

Parallel Architectures For Priority Scheduling In Programmable Data Plane Switches

cs.NI ·2026-10-03 ·Nikhil Shinde, Krishna M. Sivalingam, Gauravdeep Shami
published similarity 0.62
Abstract · 16 pages, Extended version of work published in IEEE LCN 2025

Programmable Data Plane (PDP) switches enable flexible packet processing but remain limited in scheduling capabilities, particularly for priority-based policies that require strict ordering of packets according to user-defined ranks. An earlier work, called Push-in First-out (PIFO), proposed a priority queue that enables ordering enqueued packets based on their priority. It provided an ideal abstraction for programmable packet scheduling; however, its requirement for line-rate packet sorting makes it impractical at high network speeds (100 Gbps and beyond). Approximate schedulers such as SPPIFO, AIFO, and RIFO reduce complexity but introduce priority inversions, thus degrading latency, fairness, and Flow completion times (FCTs) since they rely on First-in First-out (FIFO) queues or use Active Queue Management (AQM) as a substitute for scheduling. To address the scalability limitations of accurate schedulers while avoiding the correctness issues of approximate schedulers, this work proposes two packet queuing architectures, Parallel Processing for Priority Ordering (P3PO) and Parallel PIFO Queuing Architecture (PPQA). Both architectures decompose a large global priority queue into multiple smaller bounded-capacity priority queues that operate in parallel. P3PO uses a cascading set of priority queues with priority-based bounds to ensure that packets are inserted into the earliest queue capable of maintaining ordering. PPQA distributes packets across multiple independent priority queues based on occupancy, using a demultiplexer for balanced queuing and a multiplexer for globally selecting the highest-priority packet at dequeue. The architectures are implemented in the NetBench packet-level simulator and evaluated using empirical datacenter workloads (Web-search and Data-mining).

0.35

Design Rules for Low-Latency Multipath Congestion Control

cs.NI ·2026-11-16 ·Danny De Vleeschauwer, Chia-Yu Chang, Koen De Schepper, Simone Bolettieri
similarity 0.60
Abstract

We first study optimal congestion control from a theoretical perspective. Concretely, we consider a system that optimizes the sum of the utilities of all the users, in which the users are allowed to send their traffic over different paths over the network and derive design rules that optimal (low-latency) multipath congestion control needs to follow. Because, as it turns out that optimal congestion control requires coordination between the network nodes, and hence, is hard to implement, we investigate how to approximate its performance with algorithms in which (i) the network nodes make independent decisions and (ii) coordination is only allowed between the subflows that belong to the same user. Therefore, these design rules need to be slightly relaxed. We compare the performance of these realistic algorithms with the optimal algorithm. We also investigate to what extent the algorithms that are currently defined and are being defined in the Internet Engineering Task Force (IETF), in particular, (i) Prague congestion control (i.e., congestion control based on Accurate Explicit Congestion Notification (AccECN) marks) and (ii) a variant of a loss-based multipath congestion control algorithm, adhere to these rules.

0.29

Scalable Packet Tracking on FPGAs for Erasure-Coded RDMA over Lossy WANs

cs.AR ·2026-09-18 ·Yicheng Qian, Konstantin Taranov, Yevgeny Yankilevich, Assaf Shacham, Mahmoud Elhaddad +3 more
published similarity 0.60
Abstract · This paper appeared in the 36th International Conference on Field-Programmable Logic and Applications https://2026.fpl.org/

Modern AI workloads increasingly rely on scale across architectures that interconnect multiple datacenters to form a single "AI factory", overcoming the power and cooling constraints of individual sites. However, extending Remote Direct Memory Access (RDMA) across wide area networks (WANs) introduces fundamental challenges: multi-path packet reordering, high latency, and packet loss that severely degrade performance. While erasure coding (EC) has emerged as a promising mechanism for loss recovery, its effectiveness critically depends on efficient packet arrival tracking implemented in hardware. We present COmpact Multi-path Erasure-coded Tracking (COMET), the first fully hardware-offloaded packet-arrival tracking design implemented on an FPGA-based network interface card (NIC) for multi-path RDMA over lossy WANs. COMET employs a scalable cache-based architecture that supports operation at high link rates. Our evaluation shows that COMET sustains line rate operation at 400 Gbps and beyond. Critically, COMET decouples on-chip memory footprint from link Bandwidth-Delay Product (BDP), and its cache-based architecture (COMET Cache) enables supporting 6 times more concurrent connections than state-of-the-art (SOTA) SoC-based designs. These results demonstrate that scalable, fully hardware-offloaded packet-arrival tracking is practical on FPGA-based NICs at current data rates, and its architectural scalability extends to emerging 1.6 Tbps NICs and beyond.

0.40

A mechanism for TCP-aware Active Queue Management in packet-forwarding devices

cs.NI ·2026-10-17 ·Swarnarup Bhunia, Somit Gond, Vayun Goel, Sreelakshmi Manjunath, Padmanabhan Rajan
similarity 0.60
Abstract

The deployment of Active Queue Management (AQM) policies is known to be a promising solution to bufferbloat, the problem of persistently-full large buffers in Internet routers. However, most AQMs involve tunable parameters, and some require awareness of the characteristics of the transport-layer protocol implemented at the end systems, thereby rendering their deployment infeasible. We consider one such AQM-- a threshold-based queue policy which requires the packet-dropping threshold to be co-designed with relevant TCP parameters. We propose a mechanism that detects network congestion, estimates the congestion window evolution in the end hosts, estimates the required TCP parameter, and produces an optimal value of the packet-dropping threshold. Arguments based on analysis of the TCP fluid model are presented to substantiate the proposed mechanism. A simulation-based performance evaluation reveals the effectiveness of the proposed mechanism, compared to some widely implemented queue policies, in terms of various user- and system-oriented metrics. The proposed mechanism is particularly well-suited for implementation in Software Defined Networks (SDN) where the algorithms can run in the SDN controller and the packet-dropping threshold can be implemented in the data-plane switches through open interfaces.

0.15