A Hybrid Approach to CAM-Based Longest Prefix Matching for IP Route Lookup

Ternary Content Addressable Memories (CAMs) are widely used by high-speed routers to find matching routes in a routing table, because they enable the longest prefix matching operation to complete in a single clock cycle. However, they are costly and their power consumption is very high. In this paper, we identify two kinds of redundancy in the usage of TCAMs in IP route lookup, and then propose a hybrid scheme which combines Binary CAMs and Ternary CAMs to reduce the total area and power consumption, exploiting the uneven distribution of IP prefix lengths in real-world IP routing tables. We also introduce shared memory blocks for further simplification of the lookup circuit. The simulation results show that our approach can save more than 50% of transistors in CAMs, compared with the traditional way in storing a set of real-world routing tables, and that it reduces the critical path in IP route lookup significantly.