Open AccessMulti‐stride Indexing: Improve NFA for Fast and Scalable DPI
Author(s) -
Huo Sheng,
Zhang Dafang,
Li Yanbiao
Publication year - 2018
Publication title -
chinese journal of electronics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.267
H-Index - 25
eISSN - 2075-5597
pISSN - 1022-4653
DOI - 10.1049/cje.2017.11.015
Subject(s) - stride , search engine indexing , scalability , computer science , database , information retrieval , computer security
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.