Multi-stride Indexing: Improve NFA for Fast and Scalable DPI

Regular expression matching is one of the key techniques for Deep packet inspection (DPI). Generally, the Deterministic finite automata (DFA) can process regular expression matching at a very high rate but memory inefficient. By contrast, the Non-deterministic finite automata (NFA) improves the memory efficiency significantly, at the cost of low speed. To meet the increasing demands on both throughput and memory scalability, we propose a novel schema to achieve fast regular expression with reasonable and controllable memory consumption. According to observations on matching real traffic, we design a Multi-Stride Indexing (MSI) table and divide each matching into two steps, toward the MSI table and the NFA respectively. the MSI table consumes a small fixed amount of on-chip memories(it is about 20KB for 2 stride level MSI table). After the most of unnecessary matching was eliminated via MSI table, we implement the fast-speed regular expression matching with NFA.