Gearbox: A Hierarchical Packet Scheduler for Approximate Weighted Fair Queuing
Talkat 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI '22) · 2022-04-04..04-06·
summary
Proposes a hierarchical scheduler that approximates WFQ with O(1) enqueue/dequeue operations and a provable normalized discrepancy ≤ 1, using a few logical FIFO levels to cover wide timestamp ranges. Evaluated in NS2 (3-level fat‑tree, 256 hosts) it matches ideal WFQ on flow completion time and achieves weighted max‑min fairness with low packet loss; implemented in VHDL on a Xilinx Alveo U250, runs at 350 MHz, sustains 100GbE for packets >123 bytes while using under 1% logic and under 4% block memory.
AI-written summary · about
chapters (11)
- 0:00Intro
- 0:27Evolution of Packet Scheduling
- 1:27Background: Programmable Data Plane
- 1:53Challenges in Packet Scheduling Packets need to schedule
- 2:35Calendar Queue Based Scheduler
- 5:11Scheduler Accuracy Different packets have different tolerance of delay discrepancy
- 7:00Gearbox: Hierarchical Architecture
- 10:15Normalized Discrepancy of Gearbox Normalized Discrepancy
- 10:57Evaluation: NS2
- 13:33Implementation and Evaluation FPGA Implementation
- 14:07Conclusion
related talks
25mApproximating Fair Queueing on Reconfigurable Switches
12mTwenty Years After: Hierarchical Core-Stateless Fair Queueing
22mProgrammable Calendar Queues for High-speed Packet Scheduling
22mEiffel: Efficient and Flexible Software Packet Scheduling
13mSifter: An Inversion-Free and Large-Capacity Programmable Packet Scheduler
13mClubHeap: A High-Speed and Scalable Priority Queue for Programmable Packet Scheduling
15mEverything Matters in Programmable Packet Scheduling
16mManaging Congestion Control Heterogeneity on the Internet with Approximate Performance...