STRING SEARCH SCHEME IN A DISTRIBUTED ARCHITECTURE

• US 20110173232A1
• Filed: 03/07/2011
• Published: 07/14/2011
• Est. Priority Date: 07/26/1999
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Beylin, Boris
• Granted Patent: US 8,321,440 B2
• Time in Patent Office: Days
• US Class Current: 707/776
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: Y10S 707/959 Network
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Methods and apparatuses for searching network data for one or more predetermined strings are disclosed. In one embodiment, the string search is a multi-stage search where the stages of the search are performed by different hardware components. In one embodiment in a first search stage, a first processor performs a comparison of blocks of incoming data to determine whether the blocks potentially represent the beginning of one of the predetermined strings. If a potential predetermined string is identified, a second processor performs a further search to determine whether the string matches one of the predetermined strings. Because the first processor searches only for the beginning of the predetermined strings, the first stage comparison can be performed quickly, which improves network performance as compared to more detailed searching. The second stage is performed by second processor, which allows the first processor to search for potential matching strings. Because many strings do not match the one or more predetermined strings, the more detailed search performed by the second processor is performed selectively, which increases network performance as compared to more detailed searches on all network data.

Claims

1. A network electronic device for searching for predetermined strings, the device comprising:

a first processor to be coupled to receive a network packet via a network and to perform a first stage search on data contained in the network packet, wherein the first processor generates a first stage search report that indicates a potential string of interest if the data contained within the network packet has a first block matching a corresponding first block of at least one of the predetermined strings; and

a second processor coupled to perform a second stage search on the data contained in the network packet in response to the first stage search report, wherein the second stage search compares a second block of the potential string of interest to a corresponding second block of the at least one predetermined string to determine whether a match exists.

2. The network electronic device of claim 1, wherein the first block of the at least one predetermined string is a beginning block of the at least one predetermined string such that the first stage search includes the first processor searching the first block of data contained in the network packet only for the beginning block of the at least one predetermined string.

3. The network electronic device of claim 1, wherein first stage search report includes a location of the potential string of interest within the data contained in the network packet.

4. The network electronic device of claim 1, wherein the second processor is further coupled to output a message to indicate that the potential string of interest is a string of interest if a match exists between the second block of data of the potential string of interest and the at least one predetermined string.

5. The network electronic device of claim 4, wherein the message includes a packet destination of the network packet.

6. The network electronic device of claim 1, wherein the second processor is to be coupled to output the network packet to the network if no potential strings of interest are identified within the data contained in the network packet.

7. The network electronic device of claim 1, wherein the second processor includes a queue to maintain entries for each potential string of interest.

8. The network electronic device of claim 1, wherein the second block of the at least one predetermined string includes data other than the first block of the at least one predetermined string.

9. The network electronic device of claim 1, wherein the network packet is a first network packet and wherein the first stage search and the second stage search are pipelined such that the first processor performs the first stage search on data contained in a subsequent network packet while the second processor performs the second stage search on the data contained in the first network packet.

10. The network electronic device of claim 1, wherein the first processor is coupled to perform the first stage search on data contained in each of a plurality of network packets received at the first processor, and wherein the second processor performs the second stage search on a data contained in a subset of the plurality network packets to provide an increase in network performance.

11. The network electronic device of claim 1, wherein the first stage search includes the first processor operating as a filter to identify locations in the network packet where potential string matches may exist, and wherein the second stage search includes the second processor performing pattern matching in the locations identified by the first processor.

12. The network electronic device of claim 1, further comprising shared memory coupled to the first processor and to the second processor.