Trie search engines and ternary CAM used as pre-classifier
View Patent ↗A method performs a lookup on a search key word, employing a trie database including multiple trie blocks that include pointers to other trie blocks. Each trie is accessible by means of a segment of the search key. A selected section of the search key word is applied to a content addressable memory. In the event of an absence of a match of the selected section with an entry in the content addressable memory, a trie search is performed on the whole search key word. In the event of a match of the selected section with an entry in the content addressable memory, a partial trie search is performed, commencing with a first segment of the search key word after the selected section that has been matched in the content addressable memory.
1. A method of performing a lookup on a search key word, employing both a ternary content addressable memory and a trie database stored in random access memory (RAM) comprising a multiplicity of trie blocks that include pointers to other trie blocks, wherein each trie is accessible by means of a segment of said search key, the method comprising:
applying a selected section of the search key word to a ternary content addressable memory;
in the event of an absence of a match of said selected section with an entry in the ternary content addressable memory, performing a search on the whole of said search key word in a trie database stored in random access memory (RAM); and
in the event of a match of said selected section with an entry in the ternary content addressable memory, performing a partial search of the trie database stored in RAM commencing with a first segment of said search key word after said selected section that has been matched in the ternary content addressable memory.
2. A method as in claim 1 and further comprising applying to the ternary content addressable memory a comparison mask which delimits said selected section; and excluding from the partial search of the trie database that part of the search key which corresponds to said selected section as delimited by said comparison mask.
3. A method as in claim 1 wherein the search key comprises at least 128 bits.
4. A method as in claim 1 wherein the search key comprises a network address conforming to Internet Protocol version 6.
5. A method of performing a lookup on a search key word, employing both a ternary content addressable memory and a trie database comprising a multiplicity of trie blocks that include pointers to other trie blocks, wherein each trie is accessible by means of a segment of said search key, the method comprising:
applying a selected section of the search key word to a ternary content addressable memory;
in the event of an absence of a match of said selected section with an entry in the ternary content addressable memory:
performing, in a trie database stored in random access memory (RAM), a search on the whole of said search key word; and
in the event of a match of said selected section with an entry in the ternary content addressable memory:
accessing from said ternary content addressable memory an associated random access memory to obtain outputs that define a partial search in the trie database commencing with a first segment of said search key word after said selected section that has been matched in the ternary content addressable memory.
6. A method as in claim 5 and further comprising applying to the ternary content addressable memory a comparison mask which delimits said selected section; and obtaining from said random access memory an indicator which identifies that part of the search key which corresponds to said selected section as delimited by said comparison mask.