基于三态内容寻址存储器的多模式匹配算法

Multi-pattern Matching Algorithm Based on Ternary Content Addressable Memory

传统模式匹配算法在高速环境下无法实现数据包的实时处理。为此,提出一种基于三态内容寻址存储器(TCAM)的快速多模式匹配算法,通过模式移位将长模式截取为若干个子串,第1级TCAM存储子串,第2级TCAM存储子串的序列编号。搜索模式时,第1级TCAM向后端输出命中表项的编号,第2级TCAM实现序列编号的匹配,从而获得长模式的匹配信息,并通过编号空间划分方法压缩表项数目以提高资源利用率。实验结果表明,该算法可以实现网络数据的高速匹配处理,与基于hash标识的移位存储算法相比,具有空间消耗少的优势。

Traditional pattern matching algorithms can not process packet at line-speed under the high speed environment.This paper presents a fast multi-pattern matching algorithm based on Ternary Content Addressable Memory（TCAM） which cuts long pattern to short sub-string stored in the first TCAM by pattern shifting,and stores number in the second TCAM.In the search pattern process,the first TCAM returns the number of matching entry,the second TCAM matches the serial numbers and gives long pattern matching information.This paper proposes a space dividing method to compress the number of TCAM entries and improves the utilized rate of resources.Experimental results show that this algorithm can achieve high-speed packet processing and has lower space consumption compared with the pattern-shifted storing algorithm based on hash mark