Scale-up PIFO: Interleaving Multiple Priority Queues for High Speed Programmable Scheduling

Abstract

Push-In First-Out (PIFO) offers a unified abstraction for rapidly deploying diverse scheduling algorithms on the same hardware. As SerDes-lane aggregation pushes port rates to 1.6 Tbps, the perpacket processing budget is at a sub-nanosecond scale, making single-queue PIFO designs fail to keep up. Mirroring lane aggregation, we advocate interleaving multiple PIFO queues. However, simple round-robin parallelization introduces substantial scheduling error, and in the worst case, it can grow to the order of the buffer size. We propose Scale-up PIFO, which expands throughput while bounding scheduling error in a hardware-friendly manner. The key observation is that the round-robin dequeue mechanism mis-orders packets when rank-similar packets concentrate in a single PIFO. Scale-up PIFO thus introduces the Rank Range Load Balancing algorithm, partitioning the rank space into ranges, distributing packets within each range evenly across parallel PIFO queues, and dynamically adapting boundaries to the traffic pattern. We built an FPGA prototype and synthesized Scale-up PIFO in a 28 nm ASIC process. Scale-up PIFO can aggregate up to 8 PIFO queues and provide 1.6 Tbps throughput. Packet-level simulations show significant reductions in scheduling error and short-flow Flow Completion Time (FCT) over prior approximate PIFO schemes. To the best of our knowledge, Scale-up PIFO is the first programmable scheduling framework reaching 1.6 Tbps by interleaving across multiple PIFO queues.