Ternary CAM with Range Match Capabilities
Original Publication Date: 2001-Apr-15
Included in the Prior Art Database: 2003-Jun-18
Objective Ternary CAMs do not efficiently support arbitrary range match operators, since the implementation of a range match operator typically requires multiple ternary CAM entries. Some newly developed search algorithms (which are not part of this disclosed idea) allow to efficiently implement combined ternary CAM and range match functionality using conventional SRAM and SDRAM memory technology. The disclosed idea consists of an interface that allows to specify ternary CAM operators in combination with arbitrary range match operators. Description Figure 1 shows how the SRAM or SDRAM memory is surrounded by a lookup engine and a user interface with “CAM feeling”. Figure 2 shows four bit vectors that can be used to specify (over the user interface) an entry that includes combined ternary CAM and range match operators. The base vector contains all the exact match parts of the entry. The range segments selection vector indicates which parts of the entry contain ternary CAM and/or range match operators (these parts are marked in figure 2). The lower and upper bounds for these parts are then specified by the lower and upper bounds vectors l 1 and l 2 , respectively, u 1 and u 2 ). A ternary CAM operator is specified by a lower bound equal to all (binary) zeros and an upper bound equal to all (binary) ones. Arbitrary range match operators can have any value assigned to the lower and upper bounds.