Exp-PIFO: Scalable and Efficient Programmable Packet Scheduling#

Habib Mostafaei (TU/e); Mohammad Ezzati (TU Berlin); Pieter J. L. Cuijpers (TU/e); Stefan Schmid (TU Berlin); Gábor Rétvári (BME); Sem Borst (TU/e)

• Why: PIFO — the abstraction underlying ideal push-in-first-out scheduling — has been blocked from real switch silicon because it needs line-speed sorting. The approximations that fit hardware (SP-PIFO, AIFO) don't scale in queue count. This paper's approximation is startlingly cheap, and it sometimes beats the abstraction it approximates.
• What: A new PIFO approximation, Exp-PIFO, that tracks scheduling state with only two memory cells and uses a lookup table to avoid complex control flow. Empirically it sometimes outperforms strict PIFO on flow-completion-time metrics — and the paper explains why rather than shrugging. Proof-of-concept on Intel Tofino uses significantly less memory than SP-PIFO/AIFO implementations (from abstract only).
• How: Adaptive exponential prioritization: packets are prioritized by "exponential bins" — a coarse logarithmic ranking that preserves the ordering properties that matter for FCT while collapsing the state needed to maintain it.
• Where applicable: PISA-based programmable switches (Tofino demonstrated). Directly relevant to anyone building scheduling logic into switch pipelines or reasoning about what QoS primitives are actually implementable in merchant silicon; the two-cell state makes it deployable where nothing else fits.