Multiple string searching using ternary content addressable memory
View Patent ↗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 a 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 various embodiments, 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 string search apparatus for implementing search operations between an input string of characters and a plurality of signatures embodied by a state diagram having a plurality of branches of sequential states extending from a root node, wherein each state is associated with a goto transition to a next state and with a failure transition to a fail state, the string search apparatus including a database 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 diagram; 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 first portion of each state entry includes a state field and a character field that are individually masked with respect to the first portions of other state entries, wherein the first portion of each state entry further includes a previous result field and a count field, and the second portion of each state entry includes a next state field and a result field.
2. The string search apparatus of claim 1 , further including a control circuit coupled to the TCAM and to the associated RAM, the control circuit comprising:
a state register having a current character field, a current state field, a current prefix field, and a count field;
an input register for receiving the input string of characters, wherein the input register provides input characters to the current character field of the state register;
a counter for providing a count value to the count field of the state register; and
result logic for providing a result code to the current prefix field of the state register.
3. The string search apparatus of claim 1 , wherein the character field of each TCAM state entry includes a number N≧2 of characters of the signatures.
4. The string search apparatus of claim 3 , further including a control circuit coupled to the TCAM and to the associated RAM, the control circuit comprising:
a state register having a current character field, a current state field, a current prefix field, and a count field, wherein the current character field stores N of the characters of the input string.
5. The string search apparatus of claim 4 , wherein the state register provides a search key comprising the N current characters, a current state, a current prefix, and a count value to the TCAM for a compare operation with the first portions of the state entries stored in the TCAM.
6. The string search apparatus of claim 4 , wherein the control circuit further comprises:
an input register coupled to the state register and configured to receive the input string of characters;
a counter for providing a count value to the count field of the state register; and
result logic for providing a result code to the current prefix field of the state register.
7. The string search apparatus of claim 6 , wherein the control circuit further comprises:
a rollback circuit coupled to the input register, wherein the rollback circuit stores a rollback value that controls a read pointer of the input register.
8. A string search apparatus for implementing search operations between an input string of characters and a plurality of signatures embodied by a state diagram having a plurality of branches of sequential states extending from a root node, wherein each state is associated with a goto transition to a next state and with a failure transition to a fail state, the string search apparatus including a database 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 diagram; 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 first portion of each state entry includes a state field and a character field that are individually masked with respect to the first portions of other state entries, wherein all failure transitions to the root node are represented by a single state entry stored in the database.
9. The string search apparatus of claim 2 , wherein the state field and the character field of the single state entry consist of ternary don't care bits.
10. The string search apparatus of claim 8 , wherein the character field of each state entry that represents a failure transition to a non-root state consists of ternary don't care bits.
11. A string search apparatus for implementing search operations between an input string of characters and a plurality of signatures embodied by a state diagram having a plurality of branches of sequential states extending from a root node, wherein each state is associated with a goto transition to a next state and with a failure transition to a fail state, the string search apparatus including a database 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 diagram; and
associated random access memory (RAM) having a plurality of rows each for storing a second portion of the corresponding state entry, wherein the first portion of each state entry includes a state field and a character field that are individually masked with respect to the first portions of other state entries, wherein all the goto transitions to a second state immediately adjacent to the root node are represented by a single state entry stored in the database.
12. The string search apparatus of claim 5 , wherein the state field of the single state entry consists of ternary don't care bits.
13. A string search apparatus for implementing search operations between an input string of characters and a plurality of signatures embodied by a state diagram having a plurality of branches of sequential states extending from a root node, wherein each state is associated with a goto transition to a next state and with a failure transition to a fail state, the string search apparatus 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 diagram, wherein the first portion of each state entry includes a state field and a character field that are individually masked with respect to the first portions of other state entries;
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 of each state entry 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 is configured to provide multiple characters of the input string to the TCAM during a search operation according to the state diagram stored in the TCAM and the associated RAM, wherein the control circuit comprises:
a state register including a current character field and a current state field, wherein the state field of at least one TCAM state entry stores a number N≧2 of characters of a corresponding goto transition, and the current state field of the state register stores N characters of the input string; and
a current prefix field.
14. The string search apparatus of claim 13 , wherein the state register provides a search key comprising N characters of the input string concatenated with a current state value to the TCAM for the search operation.
15. The string search apparatus of claim 13 , wherein the control circuit further comprises:
an input register to receive the input string of characters and configured to provide the input characters to the current character field of the state register;
result logic configured to provide a result code received from the associated RAM to the current prefix field of the state register; and
a rollback circuit coupled to the input register, wherein the rollback circuit stores a rollback value that controls a read pointer of the input register.
16. The string search apparatus of claim 13 , wherein all failure transitions to the root node are represented by a single state entry stored in the TCAM.
17. The string search apparatus of claim 16 , wherein the state field and the character field of the single state entry consist of ternary don't care bits.
18. The string search apparatus of claim 13 , wherein the character field of each state entry that represents a failure transition to a non-root state consists of ternary don't care bits.
19. The string search apparatus of claim 13 , wherein all the goto transitions to a second state immediately adjacent to the root node are represented by a single state entry stored in the TCAM.
20. The string search apparatus of claim 19 , wherein the state field of the single state entry consists of ternary don't care bits.
21. A string search apparatus for implementing search operations between an input string of characters and a plurality of signatures embodied by a state diagram having a plurality of branches of sequential states extending from a root node, wherein each state is associated with a goto transition to a next state and with a failure transition to a fail state, the string search apparatus including a database 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 diagram, wherein the first portion of each state entry includes a state field and a character field that are individually masked with respect to the first portions of other state entries;
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 of each state entry includes a next state field and a result field; and
a control circuit coupled to the TCAM and the associated SRAM, wherein the control circuit comprises:
a state register having a current character field, a current state field, a current prefix field, and a count field;
an input register for receiving the input string of characters, wherein the input register provides input characters to the current character field of the state register;
a counter for providing a count value to the count field of the state register;
result logic for providing a result code to the current prefix field of the state register.
22. The string search apparatus of claim 21 wherein the control circuit further comprises:
a rollback circuit coupled to the input register, wherein the rollback circuit stores a rollback value that controls a read pointer of the input register.
23. The string search apparatus of claim 21 , wherein all failure transitions to the root node are represented by a single state entry stored in the database.
24. The string search apparatus of claim 23 , wherein the state field and the character field of the single state entry consist of ternary don't care bits.
25. The string search apparatus of claim 21 , wherein the character field of each state entry that represents a failure transition to a non-root state consists of ternary don't care bits.
26. The string search apparatus of claim 21 , wherein all the goto transitions to a second state immediately adjacent to the root node are represented by a single state entry stored in the database.
27. The string search apparatus of claim 26 , wherein the state field of the single state entry consists of ternary don't care bits.