A VLSI priority packet queue with inheritance and overwrite

Reliable priority-based flow-control is essential for real-time applications involving hard-deadlines. However, the use of first-in-first-out (FIFO) queues in such systems introduces priority inversion resulting in unbounded transmission delays. For this reason, a priority transmission queue is critical for multimedia and mission-critical systems. Yet very few priority queue implementations exist. This paper presents the design of a novel VLSI priority packet queue (PPQ), implemented in 1.2 /spl mu/m CMOS technology. It achieves fast operation by manipulating its contents in terms of packet segments, rather than individual words. Similar to paged memory, this new segmented architecture greatly reduces implementation cost by reusing segments and avoiding storage area fragmentation. By distributing the computationally intensive priority comparison operation over the access time for an entire segment, the PPQ achieves 96% of the speed of a high-speed packet FIFO. The PPQ can either perform priority inheritance or overwrite lower priority packets to minimize the impact of queue overflow. In addition, it is suitable as a general computer network interface buffer, since it robustly handles asynchronous read and write clocks of greatly disparate frequencies. Our initial implementation achieves well over twice the speed of a nonpipelined approach with minimal additional overhead. Furthermore, scaling this design to larger capacities and more priority levels results in an even greater improvement in speed over conventional approaches.<>