Approximating Fair Queueing on Reconfigurable Switches

on YouTube ↗25m

" summary

Implementation of approximate Fair Queueing on reconfigurable switches uses per-packet processing and mutable on-switch state to emulate bit-by-bit round robin with a count-min sketch variant for per-flow rounds, a bytes-per-round quantum, and a Rotating Strict Priority dequeue implemented via a small set of FIFO queues. Prototype on a Cavium NPU and simulations on a leaf-spine topology show using 12–16 FIFOs and <10% extra resources yields 2–4x faster average short-flow completion and 4–8x better 99th-tail latency versus TCP/DCTCP.

AI-written summary · about

" chapters (14)

1. 0:00Intro
2. 0:37Congestion Control Today
3. 1:32Fair Queueing : in-network enforcement
4. 2:46Fair Queueing without per-flow queues
5. 6:53Realizing Fair Queueing on Reconfigurable Switches
6. 7:59Our approach: Approximate Fair Queueing
7. 8:41Storing Approximate Flow Counters
8. 11:28Buffering Packets in Approximate Sorted Order
9. 13:09Rotating Strict Priority (RSP)
10. 13:54Realizing an RSP Scheduler
11. 15:04Summary of Techniques
12. 17:09Evaluation
13. 17:21Prototype Implementation
14. 19:08Simulation Results: Comparison to Fair Queueing

" related talks

• 12mTwenty Years After: Hierarchical Core-Stateless Fair QueueingIon Stoica, Xin Jin, Vladimir Braverman, Zhuolong Yu, Jingfeng Wu · NSDI ’21
• 16mManaging Congestion Control Heterogeneity on the Internet with Approximate Performance...Ayush Mishra, Archit Bhatnagar, Yixuan Zhang, Ben Leong, Ya Gao, Raj Joshi · NSDI '26
• 22mProgrammable Calendar Queues for High-speed Packet SchedulingMing Liu, Changhoon Kim, Arvind Krishnamurthy, Anirudh Sivaraman, Chenxingyu Zhao, Pravein Govindan Kannan, Naveen Kr. Sharma · NSDI 2020
• 16mGearbox: A Hierarchical Packet Scheduler for Approximate Weighted Fair QueuingPeixuan Gao, Anthony Dalleggio, Yang Xu, H. Jonathan Chao · 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI '22)
• 16mPRED: Performance-oriented Random Early Detection for Consistently Stable Performance...Tong Li, Zhuotao Liu, Ke Xu, Xiangyu Gao, Kun Tan, Xinle Du, Guangmeng Zhou, Hanlin Huang, Mowei Wang · NSDI '25
• 23mSP-PIFO: Approximating Push-In First-Out Behaviors using Strict-Priority QueuesLaurent Vanbever, Albert Gran Alcoz, Alexander Dietmüller · NSDI 2020
• 13mSifter: An Inversion-Free and Large-Capacity Programmable Packet SchedulerPeixuan Gao, Anthony Dalleggio, Jiajin Liu, Chen Peng, Yang Xu, H. Jonathan Chao · 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI '24)
• 16mBackpressure Flow ControlKevin Zhao, Thomas E. Anderson, Mohammad Alizadeh, Georgios Nikolaidis, Prateesh Goyal, Preey Shah · 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI '22)