Methods, systems, and devices using reprogrammable hardware for high-speed processing of streaming data to find a redefinable pattern and respond thereto

• US 7,093,023 B2
• Filed: 05/21/2002
• Issued: 08/15/2006
• Est. Priority Date: 05/21/2002
• Status: Active Grant

• Current Assignee: Washington University In St Louis
• Original Assignee: Washington University In St Louis
• Inventors: Lockwood, John, Pachos, Michael L, Loui, Ronald, Moscola, James
• Primary Examiner(s): Thompson, Marc D.
• Application Number:
  US10/152,532
• Publication Number:
  US 20030221013A1
• Time in Patent Office: 1,547 Days
• Field of Search: 709/246, 709/231, 709/208, 709/221, 704/2, 704/9, 341/51, 341/52, 341/174
• US Class Current: 709/231
• CPC Class Codes: H04L 41/08 Configuration management of networks or network elements address allocation H04L61/50
• CPC Class Codes: H04L 41/0803 Configuration setting

Abstract

A reprogrammable packet processing system for processing a stream of data is disclosed herein. A reprogrammable data processor is implemented with a programmable logic device (PLD), such as a field programmable gate array (FPGA), that is programmed to determine whether a stream of data applied thereto includes a string that matches a redefinable data pattern. If a matching string is found, the data processor performs a specified action in response thereto. The data processor is reprogrammable to search packets for the presence of different data patterns and/or perform different actions when a matching string is detected. A reconfiguration device receives input from a user specifying the data pattern and action, processes the input to generate the configuration information necessary to reprogram the PLD, and transmits the configuration information to the packet processor for reprogramming thereof.

Claims

1. A method of processing a stream of network data through a programmable logic device (PLD), said method comprising:

configuring the PLD having;

a first logic circuit adapted to;

(1) determine whether a stream of network data applied thereto includes a string matching a first regular expression pattern, and

(2) perform a first responsive action if said network data stream includes the string matching said first regular expression pattern; and

a second logic circuit adapted to;

(1) determine whether the stream of network data applied thereto includes a string matching a second regular expression pattern, and

(2) perform a second responsive action if said network data stream includes the string matching said second regular expression pattern; and

processing a stream of network data through said first logic circuit of said configured PLD to;

(1) determine whether said network data stream includes the string matching said first regular expression pattern, and

(2) perform said first responsive action if said network data stream includes the string matching said first regular expression pattern; and

while the first logic circuit processes the stream of network data, processing the stream of network data through said second logic circuit of said configured PLD to;

(1) determine whether said network data stream includes the string matching said second regular expression pattern, and

(2) perform said second responsive action if said network data stream includes the string matching said second regular expression pattern;

maintaining full throughput of network data through the PLD while the first logic circuit processes the stream of network data and the second logic circuit processes the stream of network data.

2. The method of claim 1 wherein said configuring step includes:

receiving said first and second regular expression patterns;

receiving a first action command specifying the first responsive action to be performed if said network data stream includes the string matching said first regular expression pattern;

receiving a second action command specifying the second responsive action to be performed if said network data stream includes the string matching said second regular expression pattern;

generating configuration information from said received first and second regular expression patterns and said first and second received action commands, said configuration information defining a module that is operable upon being configured into said PLD to;

(1) determine whether a stream of network data applied thereto includes the string matching said first regular expression pattern,

(2) perform said first responsive action if said network data stream includes the string matching said first regular expression pattern,

(3) determine whether the stream of network data applied thereto includes the string matching said received second regular expression pattern, and

(4) perform said second responsive action if said network data stream includes the string matching said second regular expression pattern; and

configuring said PLD with said configuration information.

3. The method of claim 2 wherein at least one of said action commands of said first and second action command receiving steps specifies a data modification operation identifying how the network data stream is to be modified if the network data stream includes the corresponding matching string.

4. The method of claim 3 wherein at least one of said action commands of said first and second action command receiving steps specifies a string replacement operation identifying a replacement string to be inserted into the network data stream in place of the corresponding matching string.

5. The method of claim 2 wherein at least one of said action commands of said first and second action command receiving steps specifies a notification operation identifying a notification signal to be transmitted if the network data stream includes the corresponding matching string.

6. The method of claim 2 wherein said network data stream is a stream of packets transmitted over a computer network, each data packet including a payload portion, and said processing steps include:

receiving a stream of network data packets;

identifying the payload portion of each received data packet; and

processing the payload portion of each received data packet through said configured PLD to;

(1) determine whether the payload portion includes the string matching said first regular expression pattern,

(2) perform said first responsive action if said a payload portion includes the string matching said first regular expression pattern,

(3) determine whether the payload portion of includes the string matching said second regular expression pattern, and

(4) perform said second responsive action if said payload portion includes the string matching said second regular expression pattern.

7. The method of claim 6 wherein said step of configuring said PLD with said configuration information includes transmitting said configuration information over said computer network to said PLD.

8. A device for generating configuration information operable to configure a programmable logic device (PLD) with a data processing module operable to receive and process a stream of network data through said PLD to determine whether said network data stream includes a regular expression pattern while maintaining full throughput of network data through the PLD and, if so, perform a responsive action, said device comprising:

an input operable to receive a plurality of regular expression patterns and a plurality of action commands from a user, each of said plurality of action commands specifying an action to be performed if said network data stream includes a string matching a corresponding regular expression pattern of said plurality of regular expression patterns;

a compiler operable to generate configuration information from said regular expression patterns and said action commands, said configuration information defining a plurality of data processing modules, each of said modules being operable upon being configured into said PLD to;

(1) determine whether a stream of network data applied thereto includes a string matching at least one of said plurality of regular expression patterns, and

(2) perform said corresponding action if said network data stream includes the matching string, said configuration information being operable to configure said PLD with said data processing modules.

9. The device of claim 8 wherein each of said action commands comprises a modification command specifying a modification operation to be performed on said network data stream if said network data stream includes the matching string, and said compiler is operable to generate said configuration information from said modification command such that said module defined thereby is operable upon being configured into said PLD to perform said modification operation on said network data stream if said network data stream includes the matching string.

10. The device of claim 9 wherein said compiler is operable to process each of said regular expression patterns through a lexical analyzer generator thereby to generate a logical representation of a pattern matching state machine that is operable to determine whether a stream of network data applied thereto includes a string that matches said received regular expression pattern, said pattern matching state machine representation at least in part defining said module.

11. The device of claim 10 wherein said modification operation specified by said modification command comprises a string replacement operation, said modification command includes a replacement string, and said compiler is also operable to process said received modification command thereby to generate a logical representation of a string replacement machine that is operable to replace the matching string in said network data stream with said replacement string, said string replacement machine representation at least in part defining said module.

12. The device of claim 11 wherein said compiler is operable to process said regular expression patterns through said lexical analyzer generator such that said pattern matching state machine representation comprises at least one deterministic finite automaton (DFA).

13. The device of claim 12 wherein said network data stream is a packet stream comprising a plurality of data packets transmitted over a computer network, and said device further comprises a transmitter interfacing said compiler with said computer network, said transmitter being operable to receive said configuration information from said compiler and transmit said configuration information over said network to a configuring device in communication with said PLD, said configuring device being operable to configure said PLD with said module defined thereby.

14. The device of claim 13 wherein each packet in said packet stream includes a payload portion, and wherein said compiler is further operable to generate said configuration information such that said module defined thereby is also operable upon being configured into said PLD to determine whether at least one of said payload portions of said packets includes a string matching at least one of said regular expression patterns.

15. The device of claim 8 further comprising a protocol wrapper operative to receive network data from a computer network and process said network data to generate said network data stream therefrom.

16. A method of configuring a programmable logic device (PLD) to process a stream of network data, said method comprising:

receiving a plurality of regular expression patterns;

receiving a plurality of action commands, each of said action commands corresponding to at least one of said plurality of regular expression patterns and specifying an action to be performed if said stream of includes a string matching at least one of said plurality of regular expression patterns;

generating configuration information from said received plurality of regular expression patterns and said received plurality of action commands that is operable to configure said PLD with a data processing module that is operable upon being configured into said PLD to;

(1) determine whether a network data stream applied thereto includes a string matching at least one of said plurality of regular expression patterns,

(2) perform said action specified by said corresponding action command if said network data stream includes the matching string, and

(3) maintain full throughput of network data through the PLD; and

communicating said configuration information to a configuring device in communication with said PLD, said configuring device being operable to configure said PLD with said configuration information.

17. The method of claim 16 wherein each of said plurality of action commands comprises a modification command specifying a modification operation to performed on said network data stream if said network data stream includes the matching string, and said generating step includes generating said configuration information such that said module defined thereby is operable to perform said modification operation on said network data stream if said network data stream includes the matching string.

18. The method of claim 17 wherein said modification operation comprises a string replacement operation, said modification command includes a replacement string, and said generating step includes generating said configuration information such that said module defined thereby is operable to perform said string replacement operation by replacing the matching string in said network data stream with said replacement string.

19. The method of claim 18 wherein said generating step includes processing each of said plurality of regular expression patterns through a lexical analyzer generator to create a logical representation of a pattern matching state machine therefrom, said pattern matching state machine at least in part defining said module and being operable to determine whether a stream of network data applied thereto includes the matching string.

20. The method of claim 19 wherein said generating step includes creating a logical representation of a string replacement machine from each of said received modification commands, said string replacement machine at least in part defining said module and being operable to replace the matching string in said network data stream with said replacement string.

21. The method of claim 20 wherein said network data stream is a packet stream comprising a plurality of data packets transmitted over a computer network, and said communicating step includes communicating said configuration information over said network to said configuring device.

22. The method of claim 21 wherein each of said data packets includes a payload portion, and wherein said generating step includes generating said configuration information such that said module defined thereby is also operable upon being configured into said PLD to determine whether any of said payload portions of said packets comprising said packet stream include the matching string.

23. A device for processing a stream of network data, said device comprising a programmable logic device (PLD) configured to receive a stream of network data and process said network data stream through a plurality of redefinable logic circuits, each logic circuit being configured to recognize a corresponding redefinable regular expression pattern, determine whether a string is present in said processed network data stream matching the corresponding regular expression pattern in the logic circuit, store a corresponding redefinable action, and perform the corresponding redefinable action if said processed network data stream includes the string matching the corresponding regular expression pattern in the logic circuit, said PLD maintaining full throughput of said network data while said logic circuits determine whether the string is present and perform the corresponding redefinable action.

24. The device of claim 23 wherein each redefinable action comprises a string replacement operation, each string replacement operation including a replacement string, wherein each logic circuit is operable to replace the matching string with the corresponding replacement string.

25. The device of claim 24 wherein said PLD comprises a field programmable gate array (FPGA) in communication with a computer network, and said network data stream comprises a stream of data packets transmitted over said computer network.

26. The device of claim 23 wherein at least one of said logic circuits comprises a deterministic finite automaton (DFA).

27. A reprogrammable system for processing a stream of network data, said system comprising:

a reprogrammable data processor for receiving a stream of network data and processing said received network data stream through a programmable logic device (PLD) configured with at least one deterministic finite automaton (DFA) to determine whether said network data stream includes a string matching a first regular expression pattern while maintaining full throughput of said network data; and

a reconfiguration device in communication with said data processor that is operable to reconfigure said PLD with a different DFA to determine whether said network data stream includes a string matching a second regular expression pattern.

28. The device of claim 27 wherein the processor is operable to store a redefinable action command specifying an action to be performed if said network data stream includes a string matching said first regular expression pattern and perform the action if said network data stream includes the string matching said first regular expression pattern.

29. A network processor for processing a stream of data packets transmitted over a computer network while maintaining full throughput of said network data, said network processor comprising:

a protocol wrapper operative to receive data from said computer network and process said data to generate a stream of data packets therefrom, said packet stream comprising a stream of words, each word including a plurality of bytes;

a matching path operative to receive said packet stream from said protocol wrapper and detect whether said packets include a string matching a regular expression pattern;

a controller in communication with said matching path that is operative to determine a starting byte position and an ending byte position of each matching string detected by said matching path; and

a data path in communication with said controller that is operative to receive said packet stream from said protocol wrapper and process each starting byte position and ending byte position of each matching string determined by said controller to;

(1) output each byte of said packet stream that does not correspond to the matching string, and

(2) replace the bytes of said packet stream that correspond to the matching string with a replacement string;

wherein said matching path, said controller, and said data path are implemented on a programmable logic device (PLD) capable of maintaining full throughput of said network data.

30. The network processor of claim 29 wherein said protocol wrapper is implemented on said PLD.