The ideal programmable scheduler is a Push-In First-Out (PIFO) queue, which achieves perfect packet sorting by pushing packets into arbitrary positions in the queue, while only draining packets from the head. Unfortunately, implementing PIFO queues in hardware is challenging due to the need to arbitrarily sort packets at line rate based on their ranks [1]. There is an ongoing quest for approximating the behaviour of a PIFO queue with the help of some FIFO queues with different priorities, where each FIFO queue is responsible for storing a given range of ranks. These ranges of ranks are then heuristically adjusted based on the ranks of incoming packets. As of now, a proper theoretical analysis of how these rank ranges should be adjusted optimally is still missing. The student's task is to investigate the applicability of quantile sketches (like Ddsketch [2]) for a provably good approximation of the PIFO behaviour under various circumstances.
Hivatkozások
1] Albert Gran Alcoz, Balázs Vass, Gábor Rétvári, Laurent Vanbever. 2023. Everything Matters in Programmable Packet Scheduling. ArXiv. https://doi.org/10.48550/arXiv.2308.00797
[2] Charles Masson, Jee E. Rim, and Homin K. Lee. 2019. DDSketch: a fast and fully-mergeable quantile sketch with relative-error guarantees. Proc. VLDB Endow. 12, 12 (August 2019), 2195–2205. https://doi.org/10.14778/3352063.3352135