BBQ: A Fast and Scalable Integer Priority Queue for Hardware Packet Scheduling

on YouTube ↗18m

" summary

BBQ implements a pipeline-parallel integer priority queue (hierarchical find-first-set) in hardware, synthesized on a commodity FPGA and projected to a 7nm ASIC, and it sustains line-rate scheduling while supporting large flow counts. It achieves 100 Gbps (148.8 Mpps) on FPGAs, 1 Tbps (1,488 Mpps) on ASICs, and supports over 100K flows and 32K priorities, using an 11-stage deep pipeline and techniques like speculation and operation coloring; the FPGA implementation meets the claimed throughput and the design is open source.

AI-written summary · about

" chapters (6)

1. 0:00Introduction to packet scheduling
2. 2:47Challenges in hardware design
3. 7:11The integer priority queuing idea
4. 10:49Designing the BBQ architecture
5. 15:17Evaluation and performance
6. 17:28Conclusion

" related talks

• 13mClubHeap: A High-Speed and Scalable Priority Queue for Programmable Packet SchedulingBin Liu, Yang Xu, Zhikang Chen, Haoyu Song, Zhiyu Zhang · NSDI '25
• 22mEiffel: Efficient and Flexible Software Packet SchedulingAmin Vahdat, Yimeng Zhao, Nandita Dukkipati, Ahmed Saeed, Ellen Zegura, Mostafa Ammar, Khaled Harras · NSDI 2019
• 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
• 15mEverything Matters in Programmable Packet SchedulingGabor Retvari, Pooria Namyar, Behnaz Arzani, Laurent Vanbever, Albert Gran Alcoz, Balázs Vass · NSDI '25
• 25mApproximating Fair Queueing on Reconfigurable SwitchesMing Liu, Arvind Krishnamurthy, Naveen Kr. Sharma, Kishore Atreya · NSDI '18
• 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)
• 16mManaging Congestion Control Heterogeneity on the Internet with Approximate Performance...Ayush Mishra, Archit Bhatnagar, Yixuan Zhang, Ben Leong, Ya Gao, Raj Joshi · NSDI '26
• 23mSP-PIFO: Approximating Push-In First-Out Behaviors using Strict-Priority QueuesLaurent Vanbever, Albert Gran Alcoz, Alexander Dietmüller · NSDI 2020