Exp-PIFO: Scalable and Efficient Programmable Packet Scheduling

Programmable packet schedulers provide great flexibility in the ordering of packet transmission. They allow network operators to optimize crucial performance metrics, such as Flow Completion Time (FCT), using strategies that adapt to changes in the characteristics of incoming traffic. A challenge in programming these devices is that they are severely limited in registers, memory, and control flow operations. The popular scheduling strategy Push-In First-Out (PIFO), for example, cannot be straightforwardly implemented because it relies on sorting packets, which is difficult to implement at line speed on current hardware. Fixed-priority approximations of PIFO, like SP-PIFO and AIFO, do have hardware implementations but generally still do not scale well in, for example, the number of memory cells being used. This paper introduces a new PIFO approximation strategy, Exp-PIFO, which prioritizes packets based on adaptive exponential prioritization criteria, called exponential bins. Exp-PIFO approximates the behavior of PIFO using only two memory cells to keep track of its state and uses a lookup table to avoid a complex control flow. We initially expected our improvement in memory and computation to come at a cost w.r.t. FCT performance compared to PIFO and its existing approximations. However, our empirical evaluation shows that Exp-PIFO sometimes even outperforms strict PIFO. We provide an explanation for this behavior and demonstrate the practical feasibility of Exp-PIFO through a proof-of-concept implementation on an Intel Tofino switch, which uses significantly less memory than comparable implementations of SP-PIFO and AIFO.