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

Explore a groundbreaking approach to hardware packet scheduling in this 18-minute conference talk from NSDI '24. Delve into the Bitmapped Bucket Queue (BBQ), an innovative hardware-based integer priority queue that addresses the challenges of fairness, isolation, and fine-grained control in multi-tenant cloud environments. Learn how BBQ leverages the Hierarchical Find First Set primitive to achieve priority packet scheduling at line-rate while supporting hundreds of thousands of concurrent flows. Discover the architecture and implementation details of BBQ, which guarantees 100 Gbps line rate on FPGAs and 1 Tbps line rate on ASICs. Gain insights into its performance capabilities, including support for over 100K flows and 32K priorities at 300 MHz on commodity FPGAs, outperforming similar hardware priority queue designs by 3×. Understand the potential impact of BBQ on modern switches and NICs, and its implications for expanding the suite of applicable scheduling policies in network traffic management.