Multi‐stride Indexing: Improve NFA for Fast and Scalable DPI. Issue 1 (1st January 2018)

• Record Type: Journal Article
• Authors: Huo, Sheng; Zhang, Dafang; Li, Yanbiao
• Is Part Of: Chinese journal of electronics. Volume 27:Issue 1(2018)
• Page Start: 86
• Page End: 92
• Publication Date: 2018-01-01
• Subjects: Regular expression matching -- Deep packet inspection (DPI) -- Non‐deterministic finite automata (NFA) -- Multi‐stride; deterministic automata -- finite automata -- indexing; multistride indexing -- NFA -- nondeterministic finite automata -- DPI -- deep packet inspection -- deterministic finite automata -- DFA -- MSI table -- on‐chip memories -- fast‐speed regular expression matching; Electronics -- Periodicals; Electronics -- China -- Periodicals; Electronics; China; Periodicals; 621.38105
• DOI: 10.1049/cje.2017.11.015
• Languages: English
• ISSNs: 1022-4653

Abstract

Abstract : 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.