Yet another paper on regular expression optimization (see previous post - here and here) - this time by Yi-Hua E. Yang, Hoang Le and Viktor K. Prasanna (picture)- all from Ming Hsieh Dept. of Electrical Eng, University of Southern California.Abstract
Dictionary-Based String Matching (DBSM) is used in network Deep Packet Inspection (DPI) applications virus scanning [1] and network intrusion detection [2]. We propose the Pipelined Affix Search with Tail Acceleration (PASTA) architecture for solving DBSM with guaranteed worst-case performance.
Our PASTA architecture is composed of a Pipelined Affix Search Relay (PASR) followed by a Tail Acceleration Finite Automaton (TAFA). PASR consists of one or more pipelined Binary Search Tree (pBST) modules arranged in a linear array. TAFA is constructed with the Aho-Corasick goto and failure functions [3] in a compact multi-path and multi-stride tree structure. Both PASR and TAFA achieve good memory efficiency of 1.2 and 2 B/ch (bytes per character) respectively and are pipelined to achieve a high clock rate of 200 MHz on FPGAs.
Because PASTA does not depend on the effectiveness of any hash function or the property of the input stream, its performance is guaranteed in the worst case. Our prototype implementation of PASTA on an FPGA with 10 Mb on-chip block RAM achieves 3.2 Gbps matching throughput against a dictionary of over 700K characters.
This level of performance surpasses the requirements of next-generation security gateways for deep packet inspection.
Posts
Amazing article with complete knowledge. Thanks for sharing. I want to share information about the Hybrid app developers in Pune. As hybrid app developers based in Pune, we deeply understand the importance of seamlessly integrating functionality and aesthetics. Whether your goal is to boost user engagement, streamline business operations, or expand your online presence, our skilled team stands ready to collaborate closely with you. Together, we'll brainstorm, design, and create a custom hybrid app solution specifically tailored to exceed your expectations.
ReplyDelete