Programmable Calendar Queues for High-speed Packet Scheduling

on YouTube ↗22m

" summary

Claim: calendar queues let switches escalate priorities of buffered packets over time so complex schedulers run at line rate. Implementation maps calendar “days” to FIFO queues, uses marker packet recirculation and head/tail pointers to rotate queues, and can be driven either by dataplane primitives (nanosecond updates) or by the switch CPU (microsecond updates). Prototype emulates LSTF, Fair Queueing and pFabric, evaluates in a simulator and a small testbed, approximates ideal SRPT closely, and uses 32 queues per port in the evaluation as a practical config.

AI-written summary · about

" chapters (17)

1. 0:00Intro
2. 0:25Packet Scheduling
3. 1:20Static Priority Limitations
4. 2:57Calendar Queues (CQs)
5. 4:17Outline
6. 4:35Reconfigurable Switches
7. 5:27Programmable Calendar Queues (PCOs)
8. 6:25Realizing Algorithms using PCOS
9. 7:35Example using PCQs: Fair Queueing
10. 9:07Example using PCQs: Earliest Deadline First
11. 11:18Implementing PCas in hardware
12. 13:14Hardware Feasibility
13. 14:13Case Study: Coflow Scheduling
14. 14:54Coflow Testbed Setup
15. 15:14Coflow Scheduling Evaluation
16. 15:53Case Study: Burst-friendly Fair Queueing
17. 17:21Summary

" 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
• 25mApproximating Fair Queueing on Reconfigurable SwitchesMing Liu, Arvind Krishnamurthy, Naveen Kr. Sharma, Kishore Atreya · NSDI '18
• 22mEiffel: Efficient and Flexible Software Packet SchedulingAmin Vahdat, Yimeng Zhao, Nandita Dukkipati, Ahmed Saeed, Ellen Zegura, Mostafa Ammar, Khaled Harras · NSDI 2019
• 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)
• 12mTwenty Years After: Hierarchical Core-Stateless Fair QueueingIon Stoica, Xin Jin, Vladimir Braverman, Zhuolong Yu, Jingfeng Wu · NSDI ’21
• 15mEverything Matters in Programmable Packet SchedulingGabor Retvari, Pooria Namyar, Behnaz Arzani, Laurent Vanbever, Albert Gran Alcoz, Balázs Vass · NSDI '25
• 16mManaging Congestion Control Heterogeneity on the Internet with Approximate Performance...Ayush Mishra, Archit Bhatnagar, Yixuan Zhang, Ben Leong, Ya Gao, Raj Joshi · NSDI '26
• 13mSifter: An Inversion-Free and Large-Capacity Programmable Packet SchedulerPeixuan Gao, Anthony Dalleggio, Jiajin Liu, Chen Peng, Yang Xu, H. Jonathan Chao · 21st USENIX Symposium on Networked Systems Design and Implementation (NSDI '24)