Browsing by Author "Tseng, Kuo-Kun"

Now showing 1 - 5 of 5

A Fast Scalable Automaton-Matching Accelerator for Embedded Content Processors
(2009-04-01)
Tseng, Kuo-Kun
;
Lai, Yuan-Cheng
;
Lin, Ying-Dar
;
Lee, Tsern-Huei
;
資訊工程學系
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.
A platform-based SoC design and implementation of scalable automaton matching for deep packet inspection
(2007-12-01)
Lin, Ying-Dar
;
Tseng, Kuo-Kun
;
Lee, Tsern-Huei
;
Lin, Yi-Neng
;
Hung, Chen-Chou
String matching plays a central role in packet inspection applications such as intrusion detection, anti-virus, anti-sparn and Web filtering. Since they are computation and memory intensive, software matching algorithms are insufficient to meet the high-speed performance. Thus, offloading packet inspection to a dedicated hardware seems inevitable. This paper presents a scalable automaton matching (SAM) coprocessor that uses Aho-Corasick (AC) algorithm with two parallel acceleration techniques, root-indexing and pre-hashing. The root-indexing can match multiple bytes in one single matching, and the pre-hashing can be used to avoid bitmap, AC matching which is a cycle-consuming operation. In the platform-based SoC implementation of the Xilinx ML310 FPGA, the proposed hardware architecture can achieve almost 10.7 Gbps and support over 10,000 patterns for virus, which is the largest pattern set from among the existing works. On the average, the performance of SAM is 7.65 times faster than the original bitmap AC. Furthermore, SAM is feasible for either internal or external memory architecture. The internal memory architecture provides high performance, while the external memory architecture provides high scalability in term of the number of patterns. (C) 2007 Elsevier B.V. All rights reserved.
Modeling and Analysis of Core-Centric Network Processors
(2009-01-01)
Lin, Yi-Neng
;
Lin, Ying-Dar
;
Tseng, Kuo-Kun
;
Lai, Yuan-Cheng
;
交大名義發表
Network processors can be categorized into two types, the coprocessors-centric model in which the data-plane is handled by coprocessors, and the core-centric model in which the core processes most of the data-plane packets yet offloading some tasks to coprocessors. While the former has been properly explored over various applications, researches regarding the latter remain limited. Based on the previous experience of prototyping the virtual private network (VPN) over the IXP425 network processor, this work aims to derive design implications for the core-centric model performing computational intensive applications. From system and IC vendors' perspectives, the continuous-time Markov chain and Petri net simulations are adopted to explore this architecture. Analytical results prove to be quite inline with those of the simulation and implementation. With subsequent investigation we find that appropriate process run lengths can improve the effective core utilization by 2.26 times, and by offloading the throughput boosts 7.5 times. The results also suggest single process programming since context switch overhead impacts considerably on the performance.
Modeling and analysis of core-centric network processors
(2008-07-01)
Lin, Yi-Neng
;
Lin, Ying-Dar
;
Lai, Yuan-Cheng
;
Tseng, Kuo-Kun
;
交大名義發表
Network processors can be categorized into two types, the coprocessors-centric model in which data-plane is handled by coprocessors, and the core-centric model in which the core processes most of the data-plane packets yet offloading some tasks to coprocessors. While the former has been properly explored over various applications, research regarding the latter remain limited. Based on the previous experience of prototyping the virtual private network (VPN) over the IXP425 network processor, this work aims to derive design implications for the core-centric model performing computational intensive applications. From system and IC vendors' perspectives, the continuous-time Markov chain and Petri net simulations are adopted to explore this architecture. Analytical results prove to be quite inline with those of the simulation and implementation. With subsequent investigation, we find that appropriate process run lengths can improve the effective core utilization by 2.26 times, and by offloading the throughput boosts 7.5 times. The results also suggest single-process programming, since context-switch overhead impacts considerably on the performance.
Solution of Skip Distance Constraint on Sub-linear Time String-matching Architecture
(2013)
Huang, Nai-Lun
;
Lee, Tsern-Huei
;
Tseng, Kuo-Kun
;
交大名義發表
;
National Chiao Tung University
Pre-filters are well-known techniques used to speed up string-matching process. The skip-based pre-filters make it possible to achieve sub-linear time complexity. However, they have a common constraint that their skip distances are bounded by the shortest keyword length. If the shortest keyword length is small, then this constraint will be a bottleneck problem in string-matching throughput. This paper provides a solution that the skip distance can be longer than the shortest keyword length. Also, a matching strategy based on the solution is proposed. This strategy can not only solve the bottleneck problem, but also reduce the operations in the sub-linear time string-matching procedure.