Fast, scalable pattern-matching engine
First Claim
Patent Images
1. A system for detecting a pattern in a data stream comprising:
- a FIFO for receiving an N-bit wide data stream and a corresponding first clock signal at a first rate, and outputting the data stream as a W times N-bit wide data stream and a corresponding second clock signal at a second rate, where W is an integer natural number and the second rate equals the first rate divided by W;
a bus splitter for splitting the W times N-bit wide data stream into W data streams of width N;
a plurality (W) of RAMs, each RAM for storing data obtained by processing the pattern and for receiving a respective one of the data streams of width N as an address and the second clock signal as a clock, and each RAM being operable to output a portion of the data on an M-bit wide output bus in accordance with a value of the address;
a processor for receiving the portions of data on each M-bit wide output bus as data and the second clock signal as a clock, and being operable to determine whether the pattern is in the data stream in dependence upon the received portions of data and the received clock, and for outputting a pattern match signal indicating detection of the pattern in the data stream; and
a channel state RAM for storing the state of the processor and running C times slower the data rate.
1 Assignment
0 Petitions
Accused Products
Abstract
A fast and scalable pattern making engine is presented. The engine represents variations on a Shift-And method capable of matching patterns in data streams having high speed data rates. In one aspect of the invention high speed is achieved by accessing the pattern RAM in parallel. In another aspect, the input is likened to TDM and individual slots or channels are accessed separately. The two aspects can also be combined to provide a scalable and high speed pattern matching engine. The engine is adaptable to streams of known length or more complex expressions such as regular expressions with arbitrary length.
96 Citations
16 Claims
-
1. A system for detecting a pattern in a data stream comprising:
-
a FIFO for receiving an N-bit wide data stream and a corresponding first clock signal at a first rate, and outputting the data stream as a W times N-bit wide data stream and a corresponding second clock signal at a second rate, where W is an integer natural number and the second rate equals the first rate divided by W; a bus splitter for splitting the W times N-bit wide data stream into W data streams of width N; a plurality (W) of RAMs, each RAM for storing data obtained by processing the pattern and for receiving a respective one of the data streams of width N as an address and the second clock signal as a clock, and each RAM being operable to output a portion of the data on an M-bit wide output bus in accordance with a value of the address; a processor for receiving the portions of data on each M-bit wide output bus as data and the second clock signal as a clock, and being operable to determine whether the pattern is in the data stream in dependence upon the received portions of data and the received clock, and for outputting a pattern match signal indicating detection of the pattern in the data stream; and a channel state RAM for storing the state of the processor and running C times slower the data rate. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A system for detecting a pattern in a data stream comprising:
-
an input stream register for receiving the data stream and a corresponding first clock signal at a first rate, and outputting the data stream and a corresponding second clock signal at a second rate; a pattern RAM for storing a pattern to be detected; a processor for receiving the data and the second clock signal as a clock, and being operable to determine whether the pattern is in the data stream in dependence upon the received data and the received clock, and for outputting a pattern match signal indicating detection of the pattern in the data stream a channel state RAM for storing the state of the processor and running C times slower the data rate a multiplexer that redirects either the contents of the processor'"'"'s register or the contents of the channel state RAM to the processor; and a channel register to switch the processor in dependence on the received data. - View Dependent Claims (9, 10, 11, 12)
-
-
13. A method of detecting a pattern in a data stream comprising:
-
receiving, at a FIFO, an N-bit wide data stream and a corresponding first clock signal at a first rate, and outputting the data stream as a W times N-bit wide data stream and a corresponding second clock signal at a second rate, where W is an integer natural number and the second rate equals the first rate divided by W; splitting the W times N-bit wide data stream into W data streams of width N; providing a plurality (W) of RAMs, each RAM for storing data obtained by processing the pattern and for receiving a respective one of the data streams of width N as an address and the second clock signal as a clock, and each RAM being operable to output a portion of the data on an M-bit wide output bus in accordance with a value of the address; receiving the portions of data on each M-bit wide output bus as data and the second clock signal as a clock at a processor, the processor being operable to determine whether the pattern is in the data stream in dependence upon the received portions of data and the received clock, and outputting a pattern match signal indicating detection of the pattern in the data stream; and a channel state RAM for storing the state of the processor and running C times slower the data rate. - View Dependent Claims (14)
-
-
15. A method of detecting a pattern in a data stream comprising:
-
receiving the data stream and a corresponding first clock signal at a first rate at an input stream register and outputting the data stream and a corresponding second clock signal at a second rate; storing a pattern to be detected at a pattern RAM; receiving the data and the second clock signal as a clock at a processor, the processor being operable to determine whether the pattern is in the data stream in dependence upon the received data and the received clock, and outputting a pattern match signal indicating detection of the pattern in the data stream; providing a channel state RAM for storing the state of the processor and running C times slower the data rate redirecting either the contents of the processor'"'"'s register or the contents of the channel state RAM to the processor; and switching the processor in dependence on the received data. - View Dependent Claims (16)
-
Specification