A Scalable and High Speed Priority Encoder Design for Packet Classification

Ternary Content Addressable Memories (TCAMs) are used in modern routers for performing packet classification at wire-speed. TCAMs that are available commercially are equipped with an in-built priority encoder and hence the look-up performance of the TCAMs depend on the priority encoder as well. Typically, TCAM chips for network application uses the priority encoder size ranging between 3,640- to 20,97, 152 - bits. However, existing priority encoder designs in the literature suffer from poor scalability. This paper proposes an efficient algorithm to implement scalable and high-speed priority encoder for TCAM chips. The logical depth of the proposed priority encoder is <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(log_{4}N)$</tex>, where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$N$</tex> is the priority encoder size. For instance, the priority encoders of size 2097152 bits implemented using the proposed tree-based algorithm has 11 - stages. Further, the throughput of the priority encoder is enhanced using pipelining. The implementation results shows that the proposed priority encoder has improved the circuit delay by 36.29% and the EPO (Energy per Operation) by 32% when compared with the best-known OR-based design.