CS Paper Radar

Parallel Architectures For Priority Scheduling In Programmable Data Plane Switches

Nikhil Shinde, Krishna M. Sivalingam, Gauravdeep Shami

cs.NI ·submitted 2026-10-03 15:19 UTC · v1
published

Abstract

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).

Comment
16 pages, Extended version of work published in IEEE LCN 2025

Closest papers

Nearest neighbours by meaning across the whole index.

Packet iSlip

cs.NI ·2026-09-25 ·Marc Mosko
similarity 0.64
Abstract

This paper examines input/output buffered crossbar switches under combined packet and cell data. Our switch architecture uses input buffering with Virtual Output Queues to avoid Head of Line Blocking. The switch fabric is a crossbar with no speedup. We use a modified iSlip [McKeown] crossbar scheduler geared towards packet data, called piSlip. Cell ports are largely unmodified from standard iSlip behavior. For packet output ports, we introduce changes to the grant pointer which minimizes output latency caused by packet reassembly. Our model uses several output states, including packet cut-through. From simulation results, we show that piSlip with virtual cut-through offers latency characteristics significantly better than unmodified iSlip with similar packet port interfaces. Simulation further shows that piSlip and iSlip have similar maximum and average buffering requirements.

0.26

Rondo: Controlling Reordering in High-Throughput Packet Spraying

cs.NI ·2026-11-03 ·Xizhi Zhang, Zhongjie Chen, Yang Zhang, Fengyuan Ren
similarity 0.62
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.

0.19

DualPI2 Active Queue Management in ns-3: Implementation And Validation

cs.NI ·2026-08-12 ·Maria Eduarda Veras, Eduardo Freitas, Assis T. de Oliveira Filho, Djamel Sadok, Judith Kelner
similarity 0.59
Abstract

The demand for ultra-low latency applications necessitates advanced network architectures like the Low Latency, Low Loss, and Scalable Throughput (L4S) standard. A core component of L4S is the DualPI2 Active Queue Management (AQM), which ensures the safe coexistence of scalable and classic traffic. Despite L4S's growing adoption, the ns-3 network simulator lacks a high-fidelity, up-to-date DualPI2 model. This paper presents a comprehensive implementation of the DualPI2 AQM in ns-3, while also mirroring the official Linux Kernel architecture. Our model incorporates representative mechanisms previously absent in simulation, such as credit-based Weighted Round Robin (WRR) scheduling, step-marking, and overload protection. To guarantee simulation accuracy, we validate our implementation against a physical Linux testbed across 25 diverse Bandwidth-Delay Product (BDP) scenarios. Results demonstrate that our ns-3 model replicates real-world behavior, ensuring strict throughput fairness and queue delay isolation. Ultimately, this validated model equips the research community with a robust tool to evaluate and advance L4S performance across diverse network topologies, ranging from data centers to wireless home and office environments.

0.04

QPS-ToR: A Parallel Iterative Switching Algorithm for Reconfigurable Optical Datacenter Switching

cs.NI ·2026-09-08 ·Dongzhao Song, Qianru Yu, Jun Xu
similarity 0.59
Abstract

Reconfigurable optical data center networks (RODCNs) have emerged as a promising solution for scaling DCN capacity, yet their scheduling mechanisms remain a performance bottleneck: traffic-oblivious schemes inherently limit throughput, while the state-of-the-art traffic-aware scheme, NegotiaToR, uses single-iteration iSLIP as its scheduling engine, which limits throughput to around 60% and treats all source-destination pairs with equal priority regardless of queue length. We propose QPS-ToR, which replaces NegotiaToR's scheduling logic with SW-QPS, a sliding-window algorithm originally proposed for crossbar scheduling that achieves around 90% throughput with a single low-complexity iteration. QPS-ToR operates within NegotiaToR's existing workflow, requiring only a revision of the scheduling cycle from three-step Request-Grant-Accept (RGA) to two-step Request-Grant (RG) with a sliding window mechanism. In flow-level simulations with 128 ToRs under realistic datacenter workloads, QPS-ToR achieves up to 36% higher throughput and 82% lower flow completion time (FCT) compared to NegotiaToR, and consistently outperforms RotorNet, a representative traffic-oblivious scheme, on the parallel network topology.

0.18

Decentralized Latency Models and Information Flow for TSN Shapers - A Tutorial

cs.NI ·2026-10-08 ·Alexej Grigorjew, Stefan Geissler, Jürgen Schmitt, Tobias Hossfeld
similarity 0.59
Abstract · This work has been submitted to IEEE COMST for possible publication. Copyright may be transferred without notice, after which this version m…

Recent advancements in the fields of industrial automation and in-vehicle communication have also increased the requirements on their underlying networks. Traditional field bus technologies are being replaced by regular Ethernet devices with features from the IEEE Time-Sensitive Networking working group. Their standards are designed to achieve zero congestion loss and deterministic latency bounds, but the specific guarantees can differ depending on the shapers used and how the bounds are calculated. After several contributions to the standardization efforts, this work presents a number of decentralized latency models that can be applied locally on the switches, without requiring global knowledge from the rest of the network. It includes a formal definition of delay segments that allows to incorporate interoperability between different shapers and latency models in the future. It presents pseudo-code suggestions for the latency bounds computation of Strict Priority, Credit-Based Shaping, Asynchronous Traffic Shaping, and Cyclic Queuing and Forwarding, all of which can be applied locally on the devices. Finally, five models were implemented and evaluated with respect to their efficiency in terms of latency, jitter, and number of accepted streams. The results illustrate how different shapers are suited for different networks and traffic distributions.

0.32

Ofan: Optimal Load Balancing for AI Training

cs.NI cs.DCcs.PF ·2026-10-05 ·Sarah McClure, Evyatar Cohen, Jakob Krebs, Alexander Shpiner, Mark Silberstein +3 more
theory similarity 0.58
Abstract · Extends the second part (Ofan) of arXiv:2507.21372

The extreme collective completion time (CCT) demands of AI workloads challenge existing packet spraying algorithms, which can have trouble efficiently load-balancing workloads that are sent at full line rates. We trace this to a structural cause: on a fat tree, once a packet picks its upward path, the downward path to its destination is unique, so destination-oblivious schemes cannot undo the imbalance it creates. We prove that such schemes can suffer from $Θ(\sqrt{m})$ queueing for messages of size $m$, thus eventually triggering rate reductions by the congestion control. Instead, we suggest Ofan, a switch-based destination-aware LB scheme that can reach $O(1)$ queueing. We also present its pOfan variant that fits the pipe-based architecture of current switches. Our P4 implementation shows that it consumes modest resources. An end-to-end FSDP2 evaluation with Llama-3 405B-parameter models shows that Ofan cuts CCT inflation by $16$--$39\times$ when compared to existing algorithms.

0.26

Priority-Based Network Access with Strict-Priority Scheduling in PLCA Multidrop Networks

cs.NI ·2026-11-11 ·Mohamed Elattar, Zhe Lou, Georg Carle
similarity 0.57
Abstract · 16 pages, 11 figures, 2 tables. This work has been submitted to the IEEE for possible publication. Copyright may be transferred without noti…

Shared-medium Ethernet is gaining renewed attention across industrial domains, driven by the adoption of 10BASE-T1S. In such multidrop networks, collision-free and deterministic medium access is achieved through Physical Layer Collision Avoidance (PLCA). However, PLCA follows a node-based cyclic access structure that does not account for traffic priority, leading to high access latency for time-sensitive traffic and limited scalability with increasing network size. Existing PLCA extensions improve latency for selected devices but remain restricted to node-based access and do not support network-wide traffic differentiation. To address these limitations, this paper introduces a priority-based network access and scheduling mechanism for multidrop networks. The proposed approach decouples medium access from node-based ordering and enables class-based prioritization, allowing high-priority traffic from any device to be transmitted ahead of lower-priority traffic. It further supports a configuration that emulates Strict Priority (SP) scheduling, providing low and bounded access latency for highest-priority traffic. Analytical bounds on the worst-case access latency are derived, validated, and shown to be tight. Performance evaluation demonstrates that the proposed mechanism reduces the maximum observed access latency for high-priority traffic by over 65% compared to PLCA, with latency increasing by less than 1% as the network grows from 8 to 40 devices.

0.35

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.57
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.23