Everything Matters in Programmable Packet Scheduling

Operators can deploy any scheduler they desire on existing
switches through programmable packet schedulers: they tag
packets with ranks (which indicate their priority) and schedule
them in the order of these ranks. The ideal programmable
scheduler is the Push-In First-Out (PIFO) queue, which schedules
packets in a perfectly sorted order by “pushing” packets
into any position of the queue based on their ranks. However,
it is hard to implement PIFO queues in hardware due to their
need to sort packets at line rate (based on their ranks).
Recent proposals approximate PIFO behaviors on existing
data-planes. While promising, they fail to simultaneously
capture both of the necessary behaviors of PIFO queues: their
scheduling behavior and admission control. We introduce
PACKS, an approximate PIFO scheduler that addresses this
problem. PACKS runs on top of a set of priority queues and
uses packet-rank information and queue-occupancy levels
during enqueue to determine whether to admit each incoming
packet and to which queue it should be mapped.
We fully implement PACKS in P4 and evaluate it on real
workloads. We show that PACKS better-approximates PIFO
than state-of-the-art approaches. Specifically, PACKS reduces
the rank inversions by up to 7× and 15× with respect to SPPIFO
and AIFO, and the number of packet drops by up to 60%
compared to SP-PIFO. Under pFabric ranks, PACKS reduces
the mean FCT across small flows by up to 33% and 2.6×,
compared to SP-PIFO and AIFO. We also show that PACKS
runs at line rate on existing hardware (Intel Tofino).