A Hardware-Based String Matching Using State Transition Compression for Deep Packet Inspection
In the Deep Packet Inspection (DPI), a string matching engine is necessary to detect target patterns from packet payloads. Due to the increase in the number of target patterns and wire speed, multiple hardware-based string matchers can be adopted, wherein the matches with target patterns are recognized in parallel. The memory-based Deterministic Finite Automaton (DFA) provides both regularity and scalability in hardware-based string matching. However, memory requirements are proportional to 2n when the input consists of n bits, as shown in the Aho-Corasick algorithm. To implement the memory-based DFA with a reasonable size, the number of state transitions should be reduced.