Concurrent searching of different tables within a content addressable memory
View Patent ↗A method and apparatus are described for the filtering of a common input string to generate various filtered comparand strings. The filtering of a common input string enables concurrent lookups in different tables to be performed on multiple filtered comparands by different CAM devices (or different blocks within a CAM device), to compare the data in the filtered comparand strings with data stored in its associative memory. By performing multiple lookups in parallel, rather than sequentially, packet throughput in a CAM may be significantly increased.
1. A method comprising
filtering a common input string to generate a first filtered string and a second filtered string, wherein the first filtered string is different than the second filtered string, and wherein the first filtered string has string segments of the common input string and one or more gaps between the string segments;
compacting the first filtered string, wherein compacting comprises shifting one or more of the string segments to remove the one or more gaps; and
performing lookups in first and second content addressable memory blocks, respectively, using the first and second filtered strings, respectively.
2. The method of claim 1 , further comprising:
generating the common input string having a plurality of comparands;
transmitting the common input string to a content addressable memory (CAM) device; and
processing the common input string to extract each comparand.
3. The method of claim 2 , further comprising concurrently comparing the plurality of extracted comparands with data stored in separate CAM blocks in the CAM device.
4. The method of claim 3 , further comprising:
translating a first input bit of a first comparand from a first bit position to a different bit position of a second comparand; and
comparing the second comparand with data stored in a first content addressable memory array of one of the separate CAM blocks.
5. The method of claim 4 , further comprising:
translating a second input bit of the first comparand from a second bit position to a different bit position of a third comparand; and
comparing the third comparand with data stored in a second content addressable memory array.