Title :
Variable-Stride Multi-Pattern Matching For Scalable Deep Packet Inspection
Author :
Hua, Nan ; Song, Haoyu ; Lakshman, T.V.
Author_Institution :
Coll. of Comput., Georgia Inst. of Technol., Atlanta, GA
Abstract :
Accelerating multi-pattern matching is a critical issue in building high-performance deep packet inspection systems. Achieving high-throughputs while reducing both memory-usage and memory-bandwidth needs is inherently difficult. In this paper, we propose a pattern (string) matching algorithm that achieves high throughput while limiting both memory-usage and memory-bandwidth. We achieve this by moving away from a byte-oriented processing of patterns to a block-oriented scheme. However, different from previous block-oriented approaches, our scheme uses variable-stride blocks. These blocks can be uniquely identified in both the pattern and the input stream, hence avoiding the multiplied memory costs which is intrinsic in previous approaches. We present the algorithm, tradeoffs, optimizations, and implementation details. Performance evaluation is done using the Snort and ClamAV pattern sets. Using our algorithm, the throughput of a single search engine can easily have a many-fold increase at a small storage cost, typically less than three bytes per pattern character.
Keywords :
content management; pattern matching; search engines; ClamAV; Snort; block-oriented processing; content inspection systems; memory-bandwidth; memory-usage; scalable deep packet inspection; search engine; variable-stride multipattern matching; Automata; Communications Society; Costs; Educational institutions; Engines; Inspection; Intrusion detection; Pattern matching; Pipeline processing; Throughput;
Conference_Titel :
INFOCOM 2009, IEEE
Conference_Location :
Rio de Janeiro
Print_ISBN :
978-1-4244-3512-8
Electronic_ISBN :
0743-166X
DOI :
10.1109/INFCOM.2009.5061946