Hardware architecture of a parallel pattern matching engine

被引:3
作者
Yadav, Meeta [1 ]
Venkatachaliah, Ashwini [1 ]
Franzon, Paul D. [1 ]
机构
[1] N Carolina State Univ, Raleigh, NC 27606 USA
来源
2007 IEEE INTERNATIONAL SYMPOSIUM ON CIRCUITS AND SYSTEMS, VOLS 1-11 | 2007年
关键词
D O I
10.1109/ISCAS.2007.378482
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Several network security and QoS applications require detecting multiple string matches in the packet payload by comparing it against predefined pattern set. This process of pattern matching at line speeds is a memory and computation intensive task. Hence, it requires dedicated hardware algorithms. In this paper we describe the hardware architecture of a parallel, pipelined pattern matching engine that uses trie based pattern matching algorithmic approach. The algorithm optimizes pattern matching process through two key innovations of parallel pattern matching using incoming content filter and multiple character matching using trie pruning. The hardware implementation is capable of performing at line-speeds and handle traffic rates upto OC-192, the underlying architecture allows for multiple patterns to be detected and for the system to gracefully recover from a failed partial match, the throughput of the system does not degrade with the increase in the number of patterns or the length of the patterns to be matched. The solution described outperforms most current implementations in terms of speed and memory requirement and outperforms TCAM based solutions in terms of power consumption, area, and cost while remaining competitive in terms of throughput and update times. We use the complete Snort rule set (2005 release) and VoIP RFC to validate our performance and achieve a throughput of 12Gbps with 6KBytes of content filter memory and 0.3 MBytes of total memory for Snort and 0.5KBytes of filter memory and 12KBytes of total memory for SIP.
引用
收藏
页码:1369 / 1372
页数:4
相关论文
共 11 条
[1]   EFFICIENT STRING MATCHING - AID TO BIBLIOGRAPHIC SEARCH [J].
AHO, AV ;
CORASICK, MJ .
COMMUNICATIONS OF THE ACM, 1975, 18 (06) :333-340
[2]  
Baker Z. K, 2004, ACM SIGDA 12 INT S F, P223
[3]  
BAKER ZK, 2004, ACM SIGDA
[4]  
CHO YH, 2005, PATTERN MATCHING COP
[5]  
CLARK CR, 2003, 13 IINT C FIELD PROG
[6]  
DHARAMPURIKAR S, 2004, DEEP PACKET INSPECTI, V24, P52
[7]  
DHARMAPURIKAR S, 2005, FAST SCALABLE PATTER
[8]   Novel hardware architecture for fast address lookups [J].
Mehrotra, P ;
Franzon, PD .
IEEE COMMUNICATIONS MAGAZINE, 2002, 40 (11) :66-71
[9]  
MEHROTRA P, 2002, MEMORY INTENSIVE ARC
[10]  
Tan L., 2005, INT S COMP ARCH