Sifter: An Inversion-Free and Large-Capacity Programmable Packet Scheduler

on YouTube ↗13m

" summary

Sifter claims inversion-free, large-capacity programmable scheduling by combining Sift Sorting coarse buckets (FIFO rotating RCQ) with a small mini PIFO for fine ordering, using a measured speed-up factor (~10 metadata operations per packet transmit) to finish sorting between dequeues. Simulations (NF3) with 256 hosts and >500 flows match ideal PIFO on flow completion time and delay, and an FPGA prototype sustains 100 Gbps line-rate while emitting monotonically increasing ranks (no packet inversions).

AI-written summary · about

" chapters (3)

1. 0:00Background and motivation
2. 5:38Design of sifter
3. 9:24Evaluation and conclusion

" related talks

• 15mEverything Matters in Programmable Packet SchedulingGabor Retvari, Pooria Namyar, Behnaz Arzani, Laurent Vanbever, Albert Gran Alcoz, Balázs Vass · NSDI '25
• 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
• 23mSP-PIFO: Approximating Push-In First-Out Behaviors using Strict-Priority QueuesLaurent Vanbever, Albert Gran Alcoz, Alexander Dietmüller · NSDI 2020
• 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
• 25mApproximating Fair Queueing on Reconfigurable SwitchesMing Liu, Arvind Krishnamurthy, Naveen Kr. Sharma, Kishore Atreya · NSDI '18
• 16mPacket Order Matters! Improving Application Performance by Deliberately Delaying PacketsDejan Kostić, Hamid Ghasemirahni, Tom Barbette, Georgios P. Katsikas, Alireza Farshin, Amir Roozbeh, Massimo Girondi, Marco Chiesa, Gerald Q. Maguire Jr. · 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI '22)