TCAM-based High Speed Longest Prefix Matching with Fast Incremental Table Updates

This paper presents a new TCAM-based method for determining the Longest Prefix Match (LPM) in an IP routing table. The method is based on modifying the address encoder of the standard TCAM design to take the prefix lengths of the IP routing entries into account while performing multi-match resolution, thus allowing prefixes to be inserted in any random order. This enables full utilization of the TCAM address space while greatly simplifying the updating procedure as complex software sorting algorithms and extensive table modifications are avoided. The result is faster table updates and consequently a higher throughput of the network search engine, since the TCAM down time caused by incremental updates is eliminated. The LPM scheme is described in HDL for FPGA implementation and compared to an existing scheme for customized CAM circuits. The paper shows that the proposed scheme can process more packets per second, has less per-lookup power consumption and is easier to expand to larger routing tables than the existing implementation. The latency of the LPM operation is only log2 N clock cycles, where N is the maximum number of prefixes in the TCAM, and in a pipelined implementation the throughput of the system is one Longest Prefix Match lookup per clock cycle.