標題: A Pattern-Matching Scheme With High Throughput Performance and Low Memory Requirement
作者: Lee, Tsern-Huei
Huang, Nai-Lun
傳播研究所
Institute of Communication Studies
關鍵字: Aho-Corasick (AC) algorithm;Bloom filter;deep packet inspection;pattern matching
公開日期: 1-八月-2013
摘要: 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.
URI: http://dx.doi.org/10.1109/TNET.2012.2224881
http://hdl.handle.net/11536/22587
ISSN: 1063-6692
DOI: 10.1109/TNET.2012.2224881
期刊: IEEE-ACM TRANSACTIONS ON NETWORKING
Volume: 21
Issue: 4
起始頁: 1104
結束頁: 1116
顯示於類別:期刊論文


文件中的檔案:

  1. 000323513000007.pdf