A Scalable High-Speed Priority Encoder Design for Packet Classification

Ternary Content Addressable Memories (TCAMs) are used in modern routers to perform packet classification at wire speed. Commercially available TCAMs come with built-in priority encoders, and thus the lookup performance of TCAMs depends on the priority encoder’s efficiency. Typically, TCAM chips for network applications use priority encoder sizes ranging from 3640 to 2,097,152 bits. However, existing priority encoder designs in the literature suffer from scalability issues. This paper proposes an efficient algorithm to implement a scalable and high-speed priority encoder for TCAM chips. The logical depth of the proposed priority encoder is \(O(\log _4 N)\) , where N represents the priority encoder size. For example, when implementing priority encoders of size 2,097,152 bits using the proposed tree-based algorithm, they have only 11 stages. Furthermore, pipelining is used to enhance the priority encoder’s throughput. Detailed implementation results show that the proposed priority encoder reduces propagation delay by 36.29% and lowers energy consumption per operation by 32% compared to the best-known OR-based design.