Scalable hardware priority queue architectures for high-speed packet switches

In packet-switched networks, queueing of packets at the switches can result when multiple connections share the same physical link. To accommodate a large number of connections, a switch can employ link-scheduling algorithms to prioritize the transmission of the queued packets. Due to the high-speed links and small packet sizes, a hardware solution is needed for the priority queue in order to make the link schedulers effective. But for good performance, the switch should also support a large number of priority levels (P) and be able to buffer a large number of packets (N). So a hardware priority queue design must be both fast and scalable (with respect to N and P) in order to be implemented effectively. In this paper we first compare four existing hardware priority queue architectures, and identify scalability limitations on implementing these existing architectures for large N and P. Based on our findings, we propose two new priority queue architectures, and evaluate them using simulation results from Verilog HDL and Epoch implementations.