Formal Abstractions for Packet Scheduling
summary
Formal operational semantics for PIFO trees and a new notion called homomorphic embedding show when one tree can reproduce another’s packet permutations; compilation preserves per-packet ranks so mappings are rank-preserving compilation resilient to silent flows. Two algorithms are provided: an efficient constructor that builds the minimum-height d-ary target for a regular d-ary hardware and a slower mapper that checks arbitrary-source embeddings and returns a mapping. A software simulator runs traces and the artifacts are reusable.
AI-written summary · about
chapters (11)
- 0:00Packet scheduling challenges
- 1:25Limitations of scheduling tools
- 2:52P43 scheduling trees
- 5:58P43 as scheduling language
- 7:03Expressiveness in P43 trees
- 8:28Tree compilation challenges
- 10:15Compiling heterogeneous trees
- 12:23Embedding algorithms for trees
- 13:47Simulating P43 performance
- 14:51P43 deployment adaptation
- 15:57Q&A
related talks
15mEverything Matters in Programmable Packet Scheduling
13mSifter: An Inversion-Free and Large-Capacity Programmable Packet Scheduler
23mSP-PIFO: Approximating Push-In First-Out Behaviors using Strict-Priority Queues
22mDependently-Typed Data Plane Programming
20mContra: A Programmable System for Performance aware Routing
13mClubHeap: A High-Speed and Scalable Priority Queue for Programmable Packet Scheduling
22mEiffel: Efficient and Flexible Software Packet Scheduling
28mSafe, Modular Packet Pipeline Programming