High Throughput Regular Expression Matching Algorithm

With the rapid increase of the network bandwidth, to process high throughput regular expressions with hardware has become inevitable. This paper presents a novel NFA-based algorithm. In this paper, two theorems were proved and were used to prove the correctness of the algorithm. Our approach was based on three basic modules to construct NFA that can be easily reused in a FPGA or ASIC. The quantitative analysis of the clock cycle and throughput was presented. The experimental results shows that our algorithm can match 128 text symbols per one clock cycle and can reach the highest frequency of the FPGA. In the circumstance, the throughput of our approach is 512Gbps.