Twenty Years After: Hierarchical Core-Stateless Fair Queueing

on YouTube ↗12m

" summary

Implements Core-Stateless Fair Queueing on programmable switches and generalizes it to Hierarchical CSFQ that approximates hierarchical fair queuing while keeping only interior-node state. Design uses a window-based rate estimator, discretized probabilistic dropping and a few recirculation packets to update fair share; it runs at line rate using a single FIFO queue. Testbed with 40 Gbps servers shows tenant isolation (about 3x per-flow throughput in the demo) and up to 60% lower flow completion time vs. TCP.

AI-written summary · about

" chapters (10)

1. 0:00Intro
2. 1:12Core-Stateless Fair Queueing (CSFQ)
3. 3:51Hierarchical Fair Queueing
4. 4:28Hierarchical CSFQ
5. 5:04Hierarchical Computation
6. 7:00Data Plane Design Rate estimator
7. 8:48Evaluation
8. 9:31Testbed Experiments
9. 10:23Large-scale DCN simulations
10. 11:20Conclusion

" related talks

• 25mApproximating Fair Queueing on Reconfigurable SwitchesMing Liu, Arvind Krishnamurthy, Naveen Kr. Sharma, Kishore Atreya · NSDI '18
• 16mManaging Congestion Control Heterogeneity on the Internet with Approximate Performance...Ayush Mishra, Archit Bhatnagar, Yixuan Zhang, Ben Leong, Ya Gao, Raj Joshi · NSDI '26
• 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)
• 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
• 20mHarmony: A Congestion-free Datacenter ArchitectureAmin Vahdat, Saksham Agarwal, Qizhe Cai, Rachit Agarwal, David Shmoys · 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI '24)
• 16mBuilding A CSFQ-Inspired Transport for Switched CXL Memory PoolingMing Liu, Zerui Guo, Emily Shriver · NSDI '26
• 22mEiffel: Efficient and Flexible Software Packet SchedulingAmin Vahdat, Yimeng Zhao, Nandita Dukkipati, Ahmed Saeed, Ellen Zegura, Mostafa Ammar, Khaled Harras · NSDI 2019
• 16mFlow Scheduling with Imprecise KnowledgeKai Chen, Guyue Liu, Wenxin Li, Xin He, Yuan Liu, Keqiu Li, Zhao Ge, Zewei Guan, Heng Qi, Song Zhang · 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI '24)