Spring: Theory and an Efficient Heuristic for Programmable Packet Scheduling with SP-PIFO

Vass, Balázs (2025) Spring: Theory and an Efficient Heuristic for Programmable Packet Scheduling with SP-PIFO. INFOCOMMUNICATIONS JOURNAL, 17 (3). pp. 2-10. ISSN 2061-2079

Preview

Text InfocomJournal_2025_3_1.pdf - Published Version Download (1MB) | Preview

Abstract

Theoretical hardware model Push-In First-Out (PIFO) is used for programmable packet scheduling, allowing for flexible and dynamic reconfiguration of scheduling policies. SP-PIFO (Strict Priority-PIFO), on the other hand, is a practical emulation of PIFO that can be easily implemented using standard P4 switches. The efficiency of SP-PIFO relies on a heuristic called Push-Up/Push-Down (PUPD), which dynamically adjusts the mapping of input packets to a fixed set of priority queues in order to minimize scheduling errors compared to an ideal PIFO. This paper presents the first formal analysis of the PUPD algorithm. Our analysis shows that as more priority queues are added to the system, the ability of PUPD to emulate an optimal PIFO model decreases linearly. Based on this finding, we propose an optimal offline scheme that can determine the optimal SPPIFO configuration in polynomial time, given a stochastic model of the input. Additionally, we introduce an online heuristic called Spring, which aims to approximate the offline optimum without requiring a stochastic input model. Our simulations demonstrate that Spring can improve the performance of SPPIFO by a factor of 2x in certain configurations.

Actions (login required)

Edit Item