A power-saving pre-classifier for TCAM-based IP lookup

摘要

Ternary Content Addressable Memory (TCAM) is widely used for designing high-throughput forwarding engines on most of today's high-end routers. Despite its capability for line-speed queries, it is very power hungry and space inefficient. By making use of a pre-classifier to activate TCAM blocks selectively, MEETIP, a recently proposed TCAM based IP lookup scheme, significantly improves the utilization of TCAMs. However, it suffers from performance degradation because it uses a two-level pre-classifier. In this paper, we propose SplitIP, a memory and power efficient TCAM-based scheme for IP routing table lookup. We first transform the IP lookup problem to a point location problem through a routing table projection. Based on the projection, we propose a top-down splitting algorithm to separate routing table prefixes evenly into TCAM blocks. Finally, a simpler one-level classifier is constructed for fast pre-classification using improved range encoding techniques. The top-down prefix partitioning algorithm combined with the database independent encoding scheme provides an incremental update for SplitIP. Experimental results show that our design achieves more than 97% power reduction with a TCAM storage overhead of less than 3% on average. (C) 2019 Elsevier B.V. All rights reserved.