SP-PIFO: Approximating Push-In First-Out Behaviors using Strict-Priority Queues
Abstract
Push-In First-Out (PIFO) queues are hardware primitives which enable programmable packet scheduling by allowing to perfectly reorder packets at line rate. While promising, implementing PIFO queues in hardware and at scale is not easy: only hardware designs (not implementations) exist and they can only support about 1000 flows. In this paper, we introduce SP-PIFO, a programmable packet scheduler which closely approximates the behavior of PIFO queues using strict-priority queues—at line rate, at scale, and on existing devices. The key insight behind SP-PIFO is to dynamically adapt the mapping between packet ranks and available queues to minimize the scheduling errors. We present a mathematical formulation of the problem and derive an adaptation technique which closely approximates the optimal queue mapping without any traffic knowledge. We fully implement SP-PIFO in P4 and evaluate it on real workloads. We show that SP-PIFO: (i) closely matches ideal PIFO performance, with as little as 8 priority queues; (ii) arbitrarily scales to large amount of flows and ranks; and (iii) quickly adapts to traffic variations. We also show that SP-PIFO runs at line rate on existing programmable data planes.
Research Area: Network Programmability
People
Talk
BibTex
@INPROCEEDINGS{alcoz2020sp-pifo,
isbn = {978-1-939133-13-7},
year = {2020},
booktitle = {Proceedings of the 17th USENIX Symposium on Networked Systems Design and Implementation},
type = {Conference Paper},
editor = {Bhagwan, Ranjita and Porter, George},
author = {Gran Alcoz, Albert and Dietmüller, Alexander and Vanbever, Laurent},
abstract = {Push-In First-Out (PIFO) queues are hardware primitives which enable programmable packet scheduling by allowing to perfectly reorder packets at line rate. While promising, implementing PIFO queues in hardware and at scale is not easy: only hardware designs (not implementations) exist and they can only support about 1000 flows.In this paper, we introduce SP-PIFO, a programmable packet scheduler which closely approximates the behavior of PIFO queues using strict-priority queues—at line rate, at scale, and on existing devices. The key insight behind SP-PIFO is to dynamically adapt the mapping between packet ranks and available queues to minimize the scheduling errors. We present a mathematical formulation of the problem and derive an adaptation technique which closely approximates the optimal queue mapping without any traffic knowledge.We fully implement SP-PIFO in P4 and evaluate it on real workloads. We show that SP-PIFO: (i) closely matches ideal PIFO performance, with as little as 8 priority queues; (ii) arbitrarily scales to large amount of flows and ranks; and (iii) quickly adapts to traffic variations. We also show that SP-PIFO runs at line rate on existing programmable data planes.},
language = {en},
address = {Berkeley, CA},
publisher = {USENIX Association},
title = {SP-PIFO: Approximating Push-In First-Out Behaviors using Strict-Priority Queues},
PAGES = {59 - 76},
Note = {17th USENIX Symposium on Networked Systems Design and Implementation (NSDI 2020); Conference Location: Santa Clara, CA, USA; Conference Date: February 25-27, 2020}
}Research Collection: 20.500.11850/446995
Slide Sources: https://gitlab.ethz.ch/projects/40918