Multiple string searching using ternary content addressable memory
View Patent ↗Disclosed herein is a method and apparatus for multiple string searching using a ternary content addressable memory. The method includes receiving a text string having a plurality of characters and performing an unanchored search of a database of stored patterns matching one or more characters of the text string using a state machine, wherein the state machine comprises a ternary content addressable memory (CAM) and wherein the performing comprises comparing a state and one of the plurality of characters with contents of a state field and a character field, respectively, stored in the ternary CAM. In the method and apparatus described herein, one or more of the following search features may be supported: exact string matching, inexact string matching, single character wildcard matching, multiple character wildcard matching, case insensitive matching, parallel matching and rollback.
1. A search engine for implementing search operations between an input string of characters and a plurality of patterns embodied by a state machine, the search engine comprising:
a ternary content addressable memory (TCAM) having a plurality of rows each for storing a first portion of a corresponding state entry of the state machine, wherein the first portion includes a state field, a character field, and a previous result field; and
an associated random access memory (RAM) having a plurality of rows each for storing a second portion of the corresponding state entry, wherein the second portion includes a next state field and a result field.
2. The search engine of claim 1 , wherein the state field, the character field, and the previous result field of the first portion of each state entry are individually masked with respect to the first portions of other state entries.
3. The search engine of claim 1 , wherein the state and character fields of at least one of the state entries consists of ternary don't care bits.
4. The search engine of claim 1 , wherein the first portion of each state entry further includes a count field.
5. The search engine of claim 1 , further comprising:
control circuitry coupled to the TCAM and the associated RAM, wherein the control circuitry includes a current state register, a current character register, and a current prefix register.
6. The search engine of claim 5 , wherein the first portion of each state entry further includes a count field, and the control circuitry further comprises a count register.
7. The search engine of claim 6 , wherein the count field stores a count value indicative of a predetermined number of wildcards in a corresponding one of the patterns.
8. The search engine of claim 7 , wherein the control circuitry further comprises a counter having an input to receive an increment signal and having an output coupled to the count register.
9. The search engine of claim 5 , wherein the control circuitry further comprises result logic configured to load a result value from the result field of the associated RAM into the current prefix register.
10. The search engine of claim 5 , wherein the contents of the current prefix register are compared with the previous result fields stored in the TCAM.
11. A search engine for implementing search operations between an input string of characters and a plurality of patterns embodied by a state machine, the search engine comprising:
a ternary content addressable memory (TCAM) having a plurality of rows each for storing a first portion of a corresponding state entry of the state machine, wherein the first portion includes a state field and a character field;
an associated random access memory (RAM) having a plurality of rows each for storing a second portion of the corresponding state entry, wherein the second portion includes a next state field and a result field; and
a control circuit coupled to the TCAM and the associated RAM, wherein the control circuit comprises a current prefix register.
12. The search engine of claim 11 , wherein the state and character fields of at least one of the state entries consists of ternary don't care bits.
13. The search engine of claim 11 , wherein the control circuit further comprises a current state register and a current character register.
14. The search engine of claim 11 , wherein the control circuit further comprises result logic configured to load a result value from the result field of the associated RAM into the current prefix register.
15. The search engine of claim 11 , wherein the first portion of each state entry further comprises a previous result field.
16. The search engine of claim 15 , wherein the contents of the current prefix register are compared with the previous result fields stored in the TCAM.
17. The search engine of claim 11 , wherein the first portion of each state entry further includes a count field, and the control circuit further comprises a count register.
18. The search engine of claim 17 , wherein the count field stores a count value indicative of a predetermined number of wildcards in a corresponding one of the patterns.
19. The search engine of claim 17 , wherein the control circuit further comprises a counter having an input to receive an increment signal and having an output coupled to the count register.