Signature searching system
View Patent ↗In a signature searching system, contents of a ternary content addressable memory (CAM) are searched to obtain a first index value that corresponds to a first group of predetermined data sequences. The first group of predetermined data sequences is selected from among a plurality of groups of predetermined data sequences based, at least in part, on the first index value, and a determination made as to whether any of the predetermined data sequences within the first group is present within a stream of data.
1. A method of searching a stream of data using a ternary content addressable memory (CAM) to determine whether a predetermined data sequence is present in the data stream:
searching the contents of the ternary CAM-to obtain a first index value that corresponds to a first group of predetermined data sequences;
selecting the first group of predetermined data sequences from among a plurality of groups of predetermined data sequences based, at least in part, on the first index value; and
determining whether any of the predetermined data sequences within the first group is present within the stream of data.
2. The method of claim 1 wherein the stream of data comprises a packet and wherein searching the contents of the ternary CAM comprises:
combining data from a plurality of fields within a header of the packet to generate a search value; and
comparing the search value with the contents of the ternary CAM.
3. The method of claim 1 wherein selecting the first group of predetermined data sequences from among the plurality of groups of predetermined data sequences comprises indexing a lookup table using the first index value to obtain an identifier of the first group of predetermined data sequences.
4. The method of claim 3 further comprising addressing a data storage having the plurality of groups of predetermined data sequences stored therein based on an address determined, at least in part, from the identifier of the first group of predetermined data sequences.
5. The method of claim 3 further comprising indexing the lookup table using the first index value to obtain a value that indicates one or more regions to be searched within the stream of data.
6. The method of claim 1 wherein searching the contents of the ternary CAM to obtain a first index value comprises comparing a first search value obtained from a combination of packet header fields with the contents of the ternary CAM.
7. The method of claim 6 further comprising comparing the first search value with the contents of the ternary CAM to obtain a second index value that corresponds to a second group of predetermined data sequences.
8. The method of claim 7 wherein comparing the first search value with the contents of the ternary CAM to obtain a second index value that corresponds to a second group of predetermined data sequences comprises comparing the first search value with the contents of the ternary CAM to obtain the second index value concurrently with said determining whether any of the predetermined data sequences within the first group is present within the stream of data.
9. The method of claim 1 wherein determining whether any of the predetermined data sequences within the first group is present within the stream of data comprises performing a string-matching operation to determine whether a character string within the first group is present within the stream of data.
10. A signature searching apparatus comprising:
a processing unit to generate a search value obtained from a combination of header fields within a packet;
a ternary content addressable memory (CAM) to receive the search value from the processing unit and to generate a first index value that corresponds to a storage location within the ternary CAM; and
a string-match engine to determine whether the packet includes any of a plurality of data sequences indicated by the first index value.
11. The signature searching apparatus of claim 10 wherein the processing unit comprises a network processing unit.
12. The signature searching apparatus of claim 10 further comprising a storage device to store a lookup table that correlates the first index value to the plurality of data sequences.
13. The signature searching apparatus of claim 10 wherein the string match engine includes an output coupled to the processing unit to signal the processing unit if the packet includes any of the plurality of data sequences indicated by the first index value.
14. The searching apparatus of claim 10 wherein the processing unit is configured to issue a first search instruction to the ternary CAM to initiate a first comparison of the search value and a first plurality of entries within the ternary CAM, and is further configured to issue a second search instruction to the ternary CAM to initiate a second comparison of the search value a subset of the first plurality of entries within the ternary CAM.
15. The searching apparatus of claim 10 wherein the string-match engine comprises a finite state machine.
16. An apparatus for searching a stream of data to determine whether a predetermined data sequence is present in the data stream:
means for searching the contents of a tuple database to obtain a first index value that corresponds to a first group of predetermined data sequences;
means for selecting the first group of predetermined data sequences from among a plurality of groups of predetermined data sequences based, at least in part, on the first index value; and
means for determining whether any of the predetermined data sequences within the first group is present within the stream of data.
17. The apparatus of claim 16 wherein the stream of data comprises a packet and wherein the means for searching the contents of a tuple database comprises:
means for combining data from a plurality of fields within a header of the packet to generate a search value; and
means for comparing the search value with the contents of the ternary CAM.
18. The apparatus of claim 16 wherein the means for selecting the first group of predetermined data sequences from among a plurality of groups of predetermined data sequences comprises means for indexing a lookup table using the first index value to obtain an identifier of the first group of predetermined data sequences.
19. The apparatus of claim 18 further comprising means for addressing a data storage having the plurality of groups of predetermined data sequences stored therein based on an address determined, at least in part, from the identifier of the first group of predetermined data sequences.
20. The apparatus of claim 16 wherein the means for determining whether any of the predetermined data sequences within the first group is present within the stream of data comprises means for performing a string-matching operation to determine whether a character string within the first group is present within the stream of data.