Design and Implementation of a Partial-Parallel Regular Expression Matching Engine Based on FPGA

Start-of-the-art deep packet inspection (DPI) system uses deterministic finite automata (DFA) algorithms to perform regular expression matching. Nevertheless, the serial iterative matching process of DFA that read characters byte-by-byte severely affects the performance improvement of DPI. Although the multi-stride DFA algorithm can process multiple characters per time, the memory consumption problem makes it difficult to apply to FPGAs with scarce on-chip resources. In this paper, we propose a partial-parallel regular expression matching algorithm called P2DFA, and design a three-level memory system architecture based on this algorithm, which is implemented by Xilinx's virtex-7 XC7V690T chip. Experimental results show that, compared to the original DFA algorithm, P2DFA can bring about the maximum 60 times performance improvement while under the premise of parallel processing to 64 characters. In addition, in the view of memory compression, a method of mapping the memory address with the state transition table is designed, which achieves a compression ratio of 50% or more without affecting the matching performance of the entire system.