Multi-stream Regular Expression Matching on FPGA
Qu Yun, Yi-Hua Edward Yang, Viktor K. Prasanna · 2011
Regular expression matching (REM) is widely used by network community for deep packet inspection and network intrusion detection. Most of the existing REM solutions on FPGA address only single-stream matching. In many real-life scenarios, however, multiple data streams are often interleaved on a high-bandwidth input to be matched by a set of regular expressions. Each data stream, for example, can consist of the payloads of a packet flow in the network. This paper presents the design and implementation of a multi-stream regular expression matching engine on FPGA. Our approach includes: (1) a flexible distributed RAM-based context storage design, (2) an efficient context switching mechanism with single-cycle switching overhead. We implemented a multi-stream REM engine on FPGA for matching against up to 96 concurrent input streams. Using our design, a state-of-the-art FPGA device can match ~1,000 regular expressions, each of length up to 100 characters, against up to 64 concurrent input streams. Place-and-route results show that our design achieves 270 MHz while matching 4 input characters per cycle, resulting in a maximum matching throughput of 8.6 Gbps.