Fast and scalable priority queue architecture for high-speed network switches
- 7 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 2 (0743166X) , 538-547
- https://doi.org/10.1109/infcom.2000.832227
Abstract
In this paper, we present a fast and scalable pipelined priority queue architecture for use in high-performance switches with support for fine grained quality of service (QoS) guarantees. Priority queues are used to implement highest-priority-first scheduling policies. Our hardware architecture is based on a new data structure called a pipelined heap, or P-heap for short. This data structure enables the pipelining of the enqueue and dequeue operations, thereby allowing these operations to execute in essentially constant time. In addition to being very fast, the architecture also scales very well to a large number of priority levels and to large queue sizes. We give a detailed description of this new data structure, the associated algorithms and the corresponding hardware implementation. We have implemented this new architecture using a 0.35 micron CMOS technology. Our current implementation can support 10 Gb/s connections with over 4 billion priority levels.Keywords
This publication has 24 references indexed in Scilit:
- A generalized processor sharing approach to flow control in integrated services networks-the multiple node casePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Rate controlled servers for very high-speed networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Rate-function schedulingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Scalable hardware priority queue architectures for high-speed packet switchesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Tiny Tera: a packet switch coreIEEE Micro, 1997
- A systolic architecture for fast stack sequential decodersIEEE Transactions on Communications, 1994
- A generalized processor sharing approach to flow control in integrated services networks: the single-node caseIEEE/ACM Transactions on Networking, 1993
- A VLSI sequencer chip for ATM traffic shaper and queue managerIEEE Journal of Solid-State Circuits, 1992
- Congestion-free communication in high-speed packet networksIEEE Transactions on Communications, 1991
- Concurrent access of priority queuesIEEE Transactions on Computers, 1988