Pattern matching relies on deterministic finite automata (DFA) to search for predefined patterns. While a bit-DFA method is recently proposed to exploit the parallelism in pattern matching, we identify its limitations and present two schemes, Label Translation Table (LTT) and CAM-based Lookup Table (CLT), to reduce the DFA memory size by 85%, and simplify the design by requiring only four processing elements of bit-DFA instead of thousands.

Pattern matching is essential to a wide range of applications such as network intrusion detection, virus scanning, etc. Pattern matching algorithms normally rely on state machines to detect predefined patterns. Recently, parallel pattern matching engines, based on ASICs, FPGAs or network processors, perform matching with multiple state machines. The state migration in the matching procedure incurs intensive memory accesses. Thus, it is critical to minimize the storage of state machines such that they can be fit in on-chip or other fast memory modules to achieve high-speed pattern matching. This paper proposes novel optimization techniques, namely state re-labeling and memory partition, to reduce state machine storage. The paper also presents architectural designs based on the optimization strategy. We evaluate our design using realistic pattern sets, and the results show state machine memory reduction up to 80.1%.

Deep Packet Inspection (DPI) refers to examining both packet header and payload to look for predefined patterns, which is essential for network security, intrusion detection and content-aware switch etc. The increasing line speed and expanding pattern sets make DPI a challenging task. Network Processors (NPs) are chosen to perform DPI due to their packet processing performance and programmability. In this paper, we focus on achieving high performance DPI through exploitation of NP's on-chip resources (particularly memory) and inherent parallel processing capability. We study the parallelism in classical DPI algorithms and construct a memory model for different parallel matching methods. Based on the model, we find the optimal organization of state machines that requires minimal on-chip memory space and guides us to high performance NP architectures for DPI. The performance evaluation experiments show that our method can reduce the memory usage by up to 86%. With an Intel IXP28xx NP simulator, we observe that the estimated DPI throughput reaches up to 5 Gbps.