Everything Matters in Programmable Packet Scheduling
Abstract
Operators can deploy any scheduler they desire on existing switches through programmable packet schedulers: they tag packets with ranks (which indicate their priority) and sched ule them in the order of these ranks. The ideal programmable scheduler is the Push-In First-Out (PIFO) queue, which sched ules 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 SP PIFO 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).
Research Area: Network Programmability
People
BibTex
@INPROCEEDINGS{alcoz2025everything,
copyright = {In Copyright - Non-Commercial Use Permitted},
year = {2024},
type = {Conference Paper},
author = {Gran Alcoz, Albert and Vass, Balázs and Namyar, Pooria and Arzani, Behnaz and Rétvári, Gábor and Vanbever, Laurent},
size = {19 p.},
abstract = {Operators can deploy any scheduler they desire on existing switches through programmable packet schedulers: they tag packets with ranks (which indicate their priority) and sched ule them in the order of these ranks. The ideal programmable scheduler is the Push-In First-Out (PIFO) queue, which sched ules 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 SP PIFO 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).},
keywords = {Programmable Scheduling; Packet Scheduling; Computer Networks},
language = {en},
DOI = {10.3929/ethz-b-000625335},
title = {Everything Matters in Programmable Packet Scheduling},
Note = {22st USENIX Symposium on Networked Systems Design and Implementation (NSDI 2025); Conference Location: Philadelphia, PA, USA; Conference Date: April 28-30, 2025}
}Research Collection: 20.500.11850/625335