BART-Enhanced Ternary CAM technology
Original Publication Date: 2002-Aug-27
Included in the Prior Art Database: 2003-Jun-21
The proposal involves a technique for improving the storage-efficiency of a ternary CAM (TCAM)-based search engine by reducing the number of TCAM locations needed for storing and searching a given search table, for example, a routing table used for IP forwarding. The improved storage-efficiency is achieved by converting the conventional single-cycle search operation into a multi-cycle search operation. The proposed technique is based on the BaRT compression scheme that is described in . Fig.1 shows a BaRT-compressed data structure, consisting of multiple linked compressed tables, distributed over several stages. This structure is typically used with conventional SRAM and DRAM memory technologies. The structure consists of an uncompressed table that is indexed by the entire first segment of the search key, and of multiple compressed tables that are indexed by specific bits of the remaining segments. Those so called "compressed index bits" are selected by an index mask (imask) that is stored together with the pointer to a given compressed table. After the index operation, the segment value is compared against a test value stored in the "indexed" table entry, eventually masked with a so called test mask (tmask) if available. For a detailed description is referred to . The various compressed tables are assigned unique table id.'s in Fig. 1. Using these table id.'s it is possible to convert the data structure in Fig. 1 into a new data structure suitable for a TCAM. This is shown in Fig. 2 for the table in Fig.1 with table ID '11'. The new data structure is based on the fact that a TCAM does perform a full parallel comparison on all TCAM entries. Therefore, instead of using a pointer (as in Fig. 1) now the unique table id. and the table index are used to select a set of TCAM entries that store a specific table, and to only focus on those entries to determine the search result. Fig. 3 shows corresponding entry format definitions.