String search scheme in a distributed architecture

• US 20030204493A1
• Filed: 04/26/2002
• Published: 10/30/2003
• Est. Priority Date: 07/26/1999
• Status: Active Grant

• Current Assignee: Boris Beylin
• Original Assignee: Boris Beylin
• Inventors: Beylin, Boris
• Granted Patent: US 7,293,020 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• 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 method for searching for a string of data matching a predetermined string of data, the method comprising:

performing a first stage search on a packet of data, wherein the first stage search identifies one or more potential strings of interest having a first portion matching the predetermined string;

generating a first stage search report indicating one or more potential strings of interest and a location of the one or more potential strings of interest within the packet and

performing a second stage search on the packet data, wherein the second stage search compares the one more potential strings of interest to the predetermined string to determine whether a match exists.

2. The method of claim 1 wherein the first stage search is performed by a first processor and the second stage search is performed by a second processor.

3. The method of claim 2 wherein the first processor is a classification engine.

4. The method of claim 2 wherein the second processor is a policy processor.

5. The method of claim 1 wherein the first stage search and the second stage search are performed by a single processor.

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

7. The method of claim 6 wherein one or more queue entries are maintained for multiple sets of data.

8. An apparatus comprising:

a first processor coupled to receive packets of data, the first processor to perform a first stage search on the packet to identify a potential string of interest having a first portion matching a corresponding first portion of a predetermined string; and

a second processor coupled to the first processor, the second processor to perform a second stage search on the packet, the second stage search comparing the potential string of interest to the predetermined string to determine whether a match exists.

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

10. The apparatus of claim 8 wherein the second processor is a policy processor.

11. The apparatus of claim 8, the first processor further to generate a first stage search report identifying one or more potential strings of interest.

12. The apparatus of claim 8, the second processor further to maintain a queue having an entry for each potential string of interest compared to the predetermined string.

13. An apparatus for searching for a string of data matching a predetermined string of data, the apparatus comprising:

means for performing a first stage search on a packet of data, wherein the first stage search identifies one or more potential strings of interest having a first portion matching the predetermined string;

means for generating a first stage search report indicating one or more potential strings of interest and a location of the one or more potential strings of interest within the packet and

means for performing a second stage search on the packet data, wherein the second stage search compares the one more potential strings of interest to the predetermined string to determine whether a match exists.

14. The apparatus of claim 13 wherein the first stage search is performed by a first processor and the second stage search is performed by a second processor.

15. The apparatus of claim 14 wherein the first processor is a classification engine.

16. The apparatus of claim 14 wherein the second processor is a policy processor.

17. The apparatus of claim 13 wherein the first stage search and the second stage search are performed by a single processor.

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

19. The apparatus of claim 18 wherein one or more queue entries are maintained for multiple sets of data.