Searching for strings in messages

• US 8,095,549 B2
• Filed: 10/05/2005
• Issued: 01/10/2012
• Est. Priority Date: 10/05/2005
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Shankara, Udaya
• Primary Examiner(s): Ali, Mohammad
• Assistant Examiner(s): TRAN, BAO G
• Application Number:
  US11/245,264
• Publication Number:
  US 20070106640A1
• Time in Patent Office: 2,288 Days
• Field of Search: 707/3, 707/4, 707/5, 707/6, 707/755, 707/796, 707/797, 715255-272, 715/853, 714/24, 375/259, 717/144
• US Class Current: 707/755
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 45/74591 using content-addressable memories [CAM]
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/2483 involving identification of individual flows
• CPC Class Codes: H04L 63/0245 Filtering by information in the payload

Abstract

A network device to determine the presence of one or more of the pre-defined strings in a message based on searching for a suffix and a reverse prefix in response to receiving a key search data indicating possible presence of any of the plurality of pre-defined strings. The network device indicates the presence or absence of one or more of the pre-defined strings in the message based on the suffix and prefix search results.

Claims

1. A method in a router to search a pre-defined string in a message, comprising:

sending a key and a key index pointing to an index element within the key to a processor in response to determining a presence of the key in the message, wherein determining the presence of the key in the message is performed in a content addressable memory,

searching for a suffix by performing a byte-by-byte comparison of the elements of the pre-defined string that occur starting from the index element with corresponding position-wise matching elements of the message in a forward direction starting from the index element,

searching for a reverse prefix by traversing a reverse prefix tree, the reverse prefix tree comprising a root node, invalid nodes, and valid nodes, wherein the invalid node of the reverse prefix tree comprises elements that do not represent a valid reverse prefix for a pre-defined string, and performing a byte-by-byte comparison of the elements of the pre-defined string that occur prior to the index element with corresponding position-wise matching elements of the message in a reverse direction starting from an element prior to the index element, wherein the reverse prefix is searched for a longest matching valid reverse prefix, and

determining that the pre-defined string is found in the message if the search for the suffix and the longest matching valid reverse prefix is successful,

wherein searching for the suffix includes searching for a longest matching valid suffix, and storing tags of the longest matching valid suffix in a memory,

wherein searching for the suffix is performed by traversing a suffix tree, wherein the suffix tree comprises a root node, invalid nodes, and valid nodes, wherein an invalid node comprises elements that does not represent a valid portion of the suffix for the pre-defined string, wherein a valid node of the suffix tree comprises elements that represent a valid portion of the suffix for the pre-defined string and a first tag, wherein the first tag includes an identifier of the pre-defined string and an identifier of the suffix tree, wherein the first tag of the valid node that matches the search in the suffix tree is stored in a first set of the memory.

2. The method of claim 1, wherein a valid node of the reverse prefix tree comprises elements that represent a valid reverse prefix for the pre-defined string and a second tag, wherein the second tag includes an identifier of the pre-defined string and an identifier of the reverse prefix tree, wherein the second tag of the valid node that matches the search in the reverse prefix tree is stored in a second set of the memory.

3. The method of claim 2, wherein the search for the pre-defined string is positive if the second tag in the second set has a corresponding first tag in the first set.

4. A network device to search a pre-defined string in a message, comprising:

a network interface to receive the message, a content addressable memory system coupled to the network interface, wherein the content addressable memory is to send a key and a key index pointing to an index element within the key to a processor in response to determining the presence of the key in the message, and the processor coupled to the content addressable memory, wherein the processor is to,

search for a suffix by performing a byte-by-byte comparison of the elements of the pre-defined string that occur starting from the index element with corresponding position-wise matching elements of the message in a forward direction starting from the index element,

search for a reverse prefix by traversing a reverse prefix tree, wherein the reverse prefix tree comprises a root node, invalid nodes, and valid nodes, wherein the invalid node of the reverse prefix tree comprises elements that does not represent a valid reverse prefix for a pre-defined string, and performing a byte-by-byte comparison of the elements of the pre-defined string that occur prior to the index element with corresponding position-wise matching elements of the message in a reverse direction starting from an element prior to the index element, wherein the reverse prefix is searched for a longest matching valid reverse prefix, and

determine that the pre-defined string is found in the message if the search for the suffix and the longest matching valid reverse prefix is successful,

wherein the processor is to search for a longest matching valid suffix and store tags of the longest matching valid suffix in a memory,

wherein the processor is to perform a search for a suffix by traversing a suffix tree, wherein the suffix tree comprises a root node, invalid nodes, and valid nodes, wherein an invalid node comprises elements that does not represent a valid portion of the suffix for the pre-defined string,

wherein a valid node of the suffix tree comprises elements that represent a valid portion of the suffix for the pre-defined string and a first tag,

wherein the first tag includes an identifier of the pre-defined string and an identifier of the suffix tree, wherein the first tag of the valid node that matches the search in the suffix tree is stored in a first set of the memory.

5. The network device of claim 4 the valid node the reverse prefix tree further comprises a second tag, wherein the second tag includes an identifier of the pre-defined string and an identifier of the reverse prefix tree, wherein the second tag of the valid node that matches the search in the reverse prefix tree is stored in a second set of the memory.

6. The apparatus of claim 5, wherein the search for the pre-defined string is positive if the second tag in the second set has a corresponding first tag in the first set.

7. A computer program product, comprising a computer usable medium having a computer readable program code embodied therein, said computer readable program code adapted to be executed to implement a method for generating a report, said method comprising:

sending a key and a key index pointing to an index element within the key to a processor in response to determining the presence of the key in the message, wherein determining the presence of the key in the message is performed in a content addressable memory,

searching for a suffix by performing a byte-by-byte comparison of the elements of the pre-defined string that occur starting from the index element with corresponding position-wise matching elements of the message in a forward direction starting from the index element,

searching for a reverse prefix by traversing a reverse prefix tree, wherein the reverse prefix tree comprises a root node, invalid nodes, and valid nodes, wherein the invalid node comprises elements that does not represent a valid reverse suffix for a pre-defined string, and performing a byte-by-byte comparison of the elements of the pre-defined string that occur prior to the index element with corresponding position-wise matching elements of the message in a reverse direction starting from an element prior to the index element, wherein the reverse prefix is searched for a longest matching valid reverse prefix, and

determining that the pre-defined string is found in the message if the search for the suffix and the longest matching valid reverse prefix is successful,

wherein searching for a longest matching valid suffix, and storing tags of the longest matching valid suffix in a memory,

wherein searching for the suffix is performed by traversing a suffix tree, wherein the suffix tree comprises a root node, invalid nodes, and valid nodes, wherein an invalid node of the suffix tree comprises elements that does not represent a valid portion of the suffix for the pre-defined string, wherein a valid node of the suffix tree comprises elements that represent a valid portion of the suffix for the pre-defined string and a first tag, wherein the first tag includes an identifier of the pre-defined string and an identifier of the suffix tree, wherein the first tag of the valid node that matches the search in the suffix tree is stored in a first set of the memory.

8. The computer program product of claim 7 wherein search for a reverse prefix is performed by traversing a reverse prefix tree, wherein the reverse prefix tree comprises a root node, invalid nodes, and valid nodes,

wherein the invalid node comprises elements that does not represent a valid reverse suffix for a predefined string,

wherein a valid node of the reverse prefix tree comprises elements that represent a valid reverse prefix for the pre-defined string and a second tag, and

wherein the second tag includes an identifier of the pre-defined string and an identifier of the reverse prefix tree, wherein the second tag of the valid node that matches the search in the reverse prefix tree is stored in a second set of the memory.

9. The computer program product of claim 8, wherein the search for the pre-defined string is positive if the second tag in the second set has a corresponding first tag in the first set.