Paper Info
Title
A Pattern-Matching Scheme With High Throughput Performance and Low Memory Requirement
Abstract
Pattern-matching techniques have recently been applied to network security applications such as intrusion detection, virus protection, and spam filters. The widely used Aho-Corasick (AC) algorithm can simultaneously match multiple patterns while providing a worst-case performance guarantee. However, as transmission technologies improve, the AC algorithm cannot keep up with transmission speeds in high-speed networks. Moreover, it may require a huge amount of space to store a two-dimensional state transition table when the total length of patterns is large. In this paper, we present a pattern-matching architecture consisting of a stateful pre-filter and an AC-based verification engine. The stateful pre-filter is optimal in the sense that it is equivalent to utilizing all previous query results. In addition, the filter can be easily realized with bitmaps and simple bitwise-AND and shift operations. The size of the two-dimensional state transition table in our proposed architecture is proportional to the number of patterns, as opposed to the total length of patterns in previous designs. Our proposed architecture achieves a significant improvement in both throughput performance and memory usage.
Year
DOI
Venue
2013
10.1109/TNET.2012.2224881
IEEE/ACM Transactions on Networking (TON)
Keywords
Field
DocType
Engines,Algorithm design and analysis,Throughput,Memory management,Pattern matching,Data structures,IEEE transactions
State transition table,Deep packet inspection,Bloom filter,Computer science,Network security,Computer network,Stateful firewall,Throughput,Intrusion detection system,Pattern matching
Journal
Volume
Issue
ISSN
21
4
1063-6692
Citations 
PageRank 
References 
2
0.38
19
Authors
2
Name
Order
Citations
PageRank
Tsern-Huei Lee124430.63
Nai-Lun Huang251.48