Gearbox - A Hierarchical Packet Scheduler for Approximate Weighted Fair Queuing

Explore a 16-minute conference talk from USENIX NSDI '22 presenting Gearbox, a hierarchical packet scheduler for approximate Weighted Fair Queuing (WFQ). Delve into the challenges of implementing WFQ in large-scale, high-speed network systems and discover how Gearbox addresses these issues with its innovative design. Learn about the scheduler's logical hierarchy of queuing levels, O(1) time complexity for enqueue and dequeue operations, and its ability to accommodate a wide range of packet departure times using a small number of FIFOs. Examine the performance evaluation results from NS2 simulations and FPGA implementation, showcasing Gearbox's effectiveness in achieving weighted max-min fairness, flow isolation, and competitive Flow Completion Time (FCT) performance. Gain insights into the scheduler's resource efficiency and its potential applications in next-generation programmable switches and smart NICs for improved network virtualization and service quality in data centers and other network systems.

Intro
Evolution of Packet Scheduling
Background: Programmable Data Plane
Challenges in Packet Scheduling Packets need to schedule
Calendar Queue Based Scheduler
Scheduler Accuracy Different packets have different tolerance of delay discrepancy
Gearbox: Hierarchical Architecture
Normalized Discrepancy of Gearbox Normalized Discrepancy
Evaluation: NS2
Implementation and Evaluation FPGA Implementation
Conclusion