P3PO: Parallel Processing For Priority Ordering In Programmable Schedulers

Packet schedulers enable Programmable Data-plane (PDP) switches to schedule packets correctly according to their priority. Existing PDP implementations do not support priority-based scheduling mechanisms required by scheduling policies. Push-in First-out (PIFO) offers a priority queuing abstraction; however, it faces scalability challenges due to the need for packet sorting at line-rate. To address this, approximate schedulers trade scheduling accuracy for implementation simplicity, but suffer from priority inversions. This paper presents Parallel Processing for Priority Ordering (P3PO) architecture, which partitions a global priority queue into multiple smaller, independently sorted queues that operate concurrently. P3PO is implemented using the NetBench simulator, and its performance (FCTs, delays, packet drops) is measured for in-cast traffic patterns. P3PO has FCTs close to PIFO and performs 14-62% better compared to existing approaches for small-sized flows and 47-60% better for large-sized flows. P3PO also reduces the packet drops in the network by 66-95% across different flow sizes.