Succinct priority indexing structures for the management of large priority queues
Hao Wang, Bill Lin · 2009
Priority queues are an essential building block for implementing advanced per-flow service disciplines at high-speed network links. In this paper, we propose novel solutions to the scalable implementation of priority queues by decomposing the problem into two parts, a succinct priority index in SRAM that can efficiently maintain a real-time sorting of priorities, coupled with a DRAM-based implementation of large packet buffers. In particular, we propose three related novel succinct priority index data structures for implementing high-speed priority indexes: a Priority-Index (PI), a Counting-Priority-Index (CPI), and a Pipelined Counting-Priority-Index (Pipelined CPI). We show that all three structures can be very compactly implemented in SRAM using only Theta(U) space, where U is the size of the universe required to implement the priority keys (timestamps). We also show that our proposed priority index structures can be implemented very efficiently as well by leveraging hardware-optimized instructions that are readily available in modern 64-bit microprocessors. The operations on the PI and CPI structures take Theta(logWU) time, where W is the processor word-length (i.e., W = 64 bits). Alternatively, operations on the Pipelined CPI structure take constant time with only Theta(logWU) pipeline stages. Finally, we show the application of our proposed priority index structures for scalable management of large packet buffers at line speeds.