String search scheme in a distributed architecture

• US 7,293,020 B2
• Filed: 04/26/2002
• Issued: 11/06/2007
• Est. Priority Date: 07/26/1999
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Beylin, Boris
• Primary Examiner(s): Truong; Cam Y.
• Assistant Examiner(s): Ly; Anh
• Application Number:
  US10/132,926
• Publication Number:
  US 20030204493A1
• Time in Patent Office: 2,020 Days
• Field of Search: 707 3- 6, 707/2, 707/10, 707/102, 711/118, 709/223, 709/238, 709/230, 709/203, 709/228
• US Class Current: 709/201
• 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. A multi-stage search may be performed by different hardware components. In a first search stage, a first processor may perform 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 may perform a further search to determine whether the string matches one of the predetermined strings.

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 portion matching a corresponding portion 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 via a policy processor on the packet of data, wherein the second stage search compares subsequent portions 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 a network management device to indicate that at least one of the multiple potential strings of interest is a string of interest if a match exists between the subsequent portions of at least one multiple potential string of interest and the one or more predetermined strings,

wherein the first portion of the potential string of interest comprises a two-byte block of data from the received packet of data and the subsequent portions of the potential string of interest comprise at least one byte of data from the received packet of data other than the two-byte block of data.

2. The method of claim 1, wherein performing the second stage search comprises maintaining a queue having cities 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 apparatus of claim 1, wherein the first portion of the potential string of interest comprises a block of data from the received packet of data and the corresponding portion of the one or more predetermined strings comprises a beginning block of data from the one or more predetermined strings.

5. The apparatus of claim 1, wherein the corresponding portion 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.

6. An apparatus comprising:

p1 means for performing a first stage search on a packet of data received via a network, wherein the first stage search identifies multiple potential strings of interest having a first portion matching a corresponding portion of one or more predetermined strings;

means for 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;

means for performing a second stage search on the packet data, wherein the second stage search compares subsequent portions 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

means for generating a message to a network management device to indicate that at least one of the multiple potential strings of interest is a string of interest if a match exists between the subsequent portions of at least one multiple potential string of interest and the one or more predetermined strings,

wherein the first portion of the potential string of interest comprises a two-byte block of data from the received packet of data and the subsequent portions of the potential string of interest comprise at least one byte of data from the received packet of data other than the two-byte block of data.

7. The apparatus of claim 6, wherein the first stage search is performed by a first processor and the second stage search is performed by a second processor.

8. The apparatus of claim 6, wherein the first processor is a classification engine.

9. The apparatus of claim 6, wherein the second processor is a policy processor.

10. The apparatus of claim 6, wherein the first stage search and the second stage search are performed by a single processor.

11. The apparatus of claim 6, wherein the means for performing the second stage search further comprises means for maintaining a queue having entries for each potential string of interest.

12. The apparatus of claim 6, wherein one or more queue entries are maintained for multiple sets of data.

13. The apparatus of claim 6, wherein the first portion of the potential string of interest comprises a block of data from the received packet of data and the corresponding portion of the one or more predetermined strings comprises a beginning block of data from the one or more predetermined strings.

14. The apparatus of claim 6, wherein the corresponding portion 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.