標題: A Fast Scalable Automaton-Matching Accelerator for Embedded Content Processors
作者: Tseng, Kuo-Kun
Lai, Yuan-Cheng
Lin, Ying-Dar
Lee, Tsern-Huei
資訊工程學系
電信工程研究所
Department of Computer Science
Institute of Communications Engineering
關鍵字: Algorithms;Performance;Design;String matching;content filtering;automaton;Aho-Corasick;Bloom filter
公開日期: 1-Apr-2009
摘要: Home and office network gateways often employ a cost-effective embedded network processor to handle their network services. Such network gateways have received strong demand for applications dealing with intrusion detection, keyword blocking, antivirus and antispam. Accordingly, we were motivated to propose an appropriate fast scalable automaton-matching (FSAM) hardware to accelerate the embedded network processors. Although automaton matching algorithms are robust with deterministic matching time, there is still plenty of room for improving their average-case performance. FSAM employs novel prehash and root-index techniques to accelerate the matching for the nonroot states and the root state, respectively, in automation based hardware. The prehash approach uses some hashing functions to pretest the input sub-string for the nonroot states while the root-index approach handles multiple bytes in one single matching for the root state. Also, FSAM is applied in a prevalent automaton algorithm, Aho-Corasick (AC), which is often used in many content-filtering applications. When implemented in FPGA, FSAM can perform at the rate of 11.1Gbps with the pattern set of 32,634 bytes, demonstrating that our proposed approach can use a small logic circuit to achieve a competitive performance, although a larger memory is used. Furthermore, the amount of patterns in FSAM is not limited by the amount of internal circuits and memories. If the high-speed external memories are employed, FSAM can support up to 21,302 patterns while maintaining similar high performance.
URI: http://dx.doi.org/10.1145/1509288.1509291
http://hdl.handle.net/11536/7440
ISSN: 1539-9087
DOI: 10.1145/1509288.1509291
期刊: ACM TRANSACTIONS ON EMBEDDED COMPUTING SYSTEMS
Volume: 8
Issue: 3
結束頁: 
Appears in Collections:Articles


Files in This Item:

  1. 000266818500003.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.