String search scheme in a distributed architecture

• US 6,493,698 B1
• Filed: 07/26/1999
• Issued: 12/10/2002
• Est. Priority Date: 07/26/1999
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Beylin, Boris
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): Ly, Anh
• Application Number:
  US09/361,347
• Time in Patent Office: 1,233 Days
• Field of Search: 707/1-10, 707/102, 709/203, 709/228
• US Class Current: 1/1
• 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. An apparatus comprising:

one or more classification engines to receive network traffic, the one or more classification engines to perform a first stage search on the network traffic and to generate a first stage search report in response to the first stage search, the first stage search report to indicate multiple potential strings of interest having a first portion matching a corresponding portion of one or more predetermined strings; and

a policy processor coupled to the one or more classification engines, the policy processor to perform a second stage search on the packet, the second stage search comparing subsequent portions of the potential strings of interest from the first stage search report to the one or more predetermined strings to determine whether a match exists.

2. The apparatus of claim 1 wherein the policy processor further comprises maintain a queue having an entry for each potential string of interest compared to the one or more predetermined strings.

3. The apparatus of claim 2 wherein the policy processor maintains one or more queue entries corresponding to multiple sets of data.