Deterministic high-speed root-hashing automaton matching coprocessor for embedded network processor

While string matching plays an important role in deep packet inspection applications, its software algorithms are insufficient to meet the demands of high-speed performance. Accordingly, we were motivated to propose fast and deterministic performance root-hashing automaton matching (RHAM) coprocessor for embedded network processor. Although automaton algorithms are robust with deterministic matching time, there is still plenty of room for improvement of their average-case performance. The proposed RHAM employs novel root-hashing technique to accelerate automaton matching. In our experiment, RHAM is implemented in a prevalent automaton algorithm, Aho-Corasick (AC) which is often used in many packet inspection applications. Compared to the original AC, RHAM only requires extra vector size in 48 Kbytes for root-hashing, and has about 900% and 420% outperformance for 20,000 URLs and 10,000 virus patterns respectively. Implementaion of RHAM FPGA can perform at the rate of 12.6 Gbps with the pattern amount in 34,215 bytes. This is superior to all previous matching hardware in terms of throughput and pattern set.