Parallel string pattern searches in respective ones of array of nanocomputers

• US 6,631,466 B1
• Filed: 05/09/2000
• Issued: 10/07/2003
• Est. Priority Date: 12/31/1998
• Status: Expired due to Term

• Current Assignee: PMC-Sierra Incorporated (Microchip Technology Incorporated)
• Original Assignee: Pmc-Sierra
• Inventors: Iyer, Sundar, Yadav, Navneet, Shelat, Ajit, Chopra, Vikram, Desai, Ajay, Jiandani, Moti, Iyer, Raghunath
• Primary Examiner(s): Kim, Kenneth S.
• Application Number:
  US09/569,593
• Time in Patent Office: 1,246 Days
• Field of Search: 712/10, 712/300, 707/6, 708/212
• US Class Current: 712/300
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/355 Application aware switches, e.g. for HTTP
• CPC Class Codes: H04L 49/50 Overload detection or protection within a single switching element
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 63/0227 Filtering policies mail message filtering H04L51/212
• CPC Class Codes: H04L 63/0263 Rule management
• CPC Class Codes: H04L 63/1416 Event detection, e.g. attack signature detection
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/161 Implementation details of TCP/IP or UDP/IP stack architecture; Specification of modified or new header fields
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A high-speed parallel pattern searching system is disclosed. The high-speed parallel pattern searching system allows the body of a data packet to be searched for one or more patterns such as a string or a series of strings. These string patterns can be defined by the grammar of regular expressions. In the invention, one or more patterns are loaded into one or more nanocomputers that operate in parallel. A control system then feeds a packet body into the participating nanocomputers such that each participating nanocomputer tests for a match. The various tests performed by the nanocomputers may be combined to perform complex searches. These nanocomputer searches are performed in parallel. Furthermore, several different searches may be combined together using control statements. A combination of these searches engines can be supported such that data is also looked at in parallel.

Claims

1. A method for locating patterns in a data packet, said method comprising:

distributing a first pattern to a first nanocomputer in an array of nanocomputers; and

distributing a second pattern to a second nanocomputer in an array of nanocomputers; and

streaming data from said data packet to said array of nanocomputers;

comparing, within said first and second nanocomputers, said streamed data against said first and second patterns, respectively; and

signaling a match when at least one of said nanocomputers has detected a match.

2. The method as claimed in claim 1 wherein streaming data from said data packet starts from a defined offset in said data packet.

3. The method as claimed in claim 1 wherein streaming data from said data packet comprising streaming data from said data packet in a reverse direction.

4. The method as claimed in claim 3 wherein said first pattern and said second pattern are reversed.

5. The method as claimed in claim 1 wherein signaling a match comprises signaling a match when at least one of said first nanocomputer or said second nanocomputer has detected a match.

6. The method as claimed in claim 1 wherein signaling a match comprises signaling a match when both said first nanocomputer and said second nanocomputer have detected a match.

7. A method for locating patterns in a data packet, said method comprising:

distributing a first pattern portion of an overall pattern to a first nanocomputer in an array of nanocomputers; and

distributing a second pattern portion of said overall pattern to a second nanocomputer in an array of nanocomputers; and

streaming data from said data packet to said array of nanocomputers;

comparing, within said first and second nanocomputers, said streamed data against said first and second pattern portions, respectively; and

signaling a match when both said first nanocomputer and said second nanocomputer have detected a match.

8. The method as claimed in claim 7 wherein streaming data from said data packet starts from a defined offset in said data packet.

9. The method as claimed in claim 7 Wherein streaming data from said data packet comprising streaming data from said data packet in a reverse direction.

10. The method as claimed in claim 9 wherein said first pattern and said second pattern are reversed.

11. An apparatus for locating patterns in a data packet, said apparatus comprising:

an array of nanocomputers, each nanocomputer in said array of nanocomputers comprising

a memory,

a bus interface,

at least one arithmetic-logic unit, and

control circuitry for controlling said memory, bus interface, and arithmetic unit;

a bus distribution system, said bus distribution system for distributing information to said nanocomputers using said bus interface within each said nanocomputer;

a control unit for controlling said array nanocomputers cells, said control unit distributing a first pattern to a first nanocomputer, distributing a second pattern to a second nanocomputer, and streaming data from said data packet to said array of nanocomputers; and

match detection logic for signaling a match when at least one of said nanocomputers has detected a match.

12. The apparatus as claimed in claim 11 wherein said control unit streams data from a defined offset in said data packet.

13. The apparatus as claimed in claim 11 wherein said control unit streams data from said data packet in a reverse direction.

14. The apparatus as claimed in claim 13 wherein said first pattern and said second pattern are reversed.

15. The apparatus as claimed in claim 11 wherein signaling a match comprises signaling a match when at least one of said first nanocomputer or said second nanocomputer has detected a match.

16. The apparatus as claimed in claim 11 wherein signaling a match comprises signaling a match when both said first nanocomputer and said second nanocomputer have detected a match.

17. An apparatus for locating patterns in a data packet, said apparatus comprising:

an array of nanocomputers, each nanocomputer in said array of nanocomputers comprising

a memory,

a bus interface,

at least one arithmetic-logic unit, and

control circuitry for controlling said memory, bus interface, and arithmetic unit,

a bus distribution system, said bus distribution system for distributing information to said nanocomputers using said bus interface within each said nanocomputer;

a control unit for controlling said array nanocomputers cells, said control unit distributing a first pattern portion of an overall pattern to a first nanocomputer, distributing a second pattern portion of said overall pattern to a second nanocomputer, and streaming data from said data packet to said array of nanocomputers; and

match detection logic for signaling a match when both said first nanocomputer and said second nanocomputer have detected a match.

18. The apparatus as claimed in claim 17 wherein streaming data from said data packet starts from a defined offset in said data packet.

19. The apparatus as claimed in claim 17 wherein streaming data from said data packet comprising streaming data from said data packet in a reverse direction.

20. The apparatus as claimed in claim 19 wherein said first pattern and said second pattern are reversed.