Parallel DFA Architecture for Ultra High Throughput DFA-Based Pattern Matching

Yi TANG  Junchen JIANG  Xiaofei WANG  Chengchen HU  Bin LIU  Zhijia CHEN  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E93-D   No.12   pp.3232-3242
Publication Date: 2010/12/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E93.D.3232
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Parallel and Distributed Computing and Networking)
Category: 
Keyword: 
Deterministic Finite Automata (DFA),  Deep Packet Inspection (DPI),  regular expression,  parallel matching,  speedup,  

Full Text: PDF(1.3MB)>>
Buy this Article




Summary: 
Multi-pattern matching is a key technique for implementing network security applications such as Network Intrusion Detection/Protection Systems (NIDS/NIPSes) where every packet is inspected against tens of thousands of predefined attack signatures written in regular expressions (regexes). To this end, Deterministic Finite Automaton (DFA) is widely used for multi-regex matching, but existing DFA-based researches have claimed high throughput at an expense of extremely high memory cost, so fail to be employed in devices such as high-speed routers and embedded systems where the available memory is quite limited. In this paper, we propose a parallel architecture of DFA called Parallel DFA (PDFA) taking advantage of the large amount of concurrent flows to increase the throughput with nearly no extra memory cost. The basic idea is to selectively store the underlying DFA in memory modules that can be accessed in parallel. To explore its potential parallelism we intensively study DFA-split schemes from both state and transition points in this paper. The performance of our approach in both the average cases and the worst cases is analyzed, optimized and evaluated by numerical results. The evaluation shows that we obtain an average speedup of 100 times compared with traditional DFA-based matching approach.