String Search Scheme in a Distributed Architecture

• US 20080059465A1
• Filed: 11/05/2007
• Published: 03/06/2008
• Est. Priority Date: 07/26/1999
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Beylin, Boris
• Granted Patent: US 7,917,509 B2
• Time in Patent Office: Days
• US Class Current: 707/6
• 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 preformed by the second processor is performed selectively, which increases network performance as compared to more detailed searches on all network data.

Claims

1. A method comprising:

receiving a packet of data via a network at one or more classification engines;

performing a first stage search at the one or more classification engines on the packet of data, wherein the first stage search identifies multiple potential strings of interest having a first block of data matching a corresponding block of data of one or more predetermined strings;

generating a first stage search report indicating multiple potential strings of interest and a location of the multiple potential strings of interest within the packet of data;

performing a second stage search on the packet of data, wherein the second stage search compares a second block of data of the multiple potential strings of interest indicated in the first stage search report to the one or more predetermined strings to determine whether a match exists; and

generating a message to indicate that at least one of the multiple potential strings of interest is a string of interest if a match exists between the second block of data of at least one multiple potential string of interest and the one or more predetermined strings.

2. The method of claim 1, wherein performing the second stage search comprises maintaining a queue having entries for each potential string of interest.

3. The method of claim 2, wherein one or more queue entries are maintained for multiple sets of data.

4. The method of claim 1, wherein the second block of data includes data other than the first block of data.

5. An article of manufacture, comprising:

a machine-accessible medium including data that, when accessed by a machine, cause the machine to perform operations comprising,

performing a first stage search on a packet of data received via a network, wherein the first stage search identities multiple potential strings of interest having a first block of data matching a corresponding block of data of one or more predetermined strings;

generating a first stage search report indicating multiple potential strings of interest and a location of the multiple potential strings of interest within the packet;

performing a second stage search on the packet data, wherein the second stage search compares a second block of data of the multiple potential strings of interest indicated in the first stage search report to the one or more predetermined strings to determine whether a match exists; and

generating a message to indicate that at least one of the multiple potential strings of interest is a string of interest if a match exists between the second block of data of at least one multiple potential string of interest and the one or more predetermined strings.

6. The article of manufacture of claim 5, wherein machine includes a first processor and then machine-accessible medium further includes data that, when accessed by the first processor, causes the first processor to generate the first stage search report identifying one or more potential strings of interest.

7. The article of manufacture of claim 6, wherein the machine includes a second processor and the machine-accessible medium further includes data that, when accessed by the second processor, causes the second processor to perform the second stage search.

8. The article of manufacture of claim 5, wherein the machine-accessible medium further includes data that, when accessed by a single processor, causes the single processor to perform the first stage search and the second stage search.

9. The article of manufacture of claim 5, wherein performing the second stage search further comprises maintaining a queue having entries for each potential string of interest.

10. The article of manufacture of claim 5, wherein the corresponding block of data of the one or more predetermined strings comprises a beginning block of data from the one or more predetermined strings.

11. The article of manufacture of claim 5, wherein the corresponding block of data of the one or more predetermined strings comprises a first and a second one-byte entry stored in a look-up table, the first and second one-byte entries representative of a beginning two bytes of the one or more predetermined strings.

12. The article of manufacture of claim 5, wherein the corresponding block of data of the one or more predetermined strings comprises a first and a second one-byte entry stored in a look-up table, the first and second one-byte entries representative of a beginning two bytes of the one or more predetermined strings.

13. The article of manufacture of claim 5, wherein the second block of data includes data other than the first block of data.