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

作　　者：HUO Sheng ZHANG Dafang LI Yanbiao 

机构地区：[1]College of Information Science and Engineering, Hunan University

出　　处：《Chinese Journal of Electronics》2018年第1期86-92,共7页电子学报（英文版）

基　　金：supported by the National Science Foundation of China(No.61472130);the National Basic Research Program of China(973)(No.2012CB315805);the Prospective Research Project on Future Networks of Jiangsu Future Networks Innovation Institute(No.BY2013095-1-05)

摘　　要：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 20 KB 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.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 20 KB 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.

关 键 词：Regular expression matching Deep packet inspection(DPI) Non-deterministic finite automata(NFA) Multi-stride 

分 类 号：TN[电子电信]