采用集合切分编码的大容量模式匹配算法

摘要：

针对现有模式匹配算法无法实现大容量模式集快速搜索的不足,提出了一种基于TCAM多字节状态机的模式匹配算法.利用TCAM的掩码特性,切分具有相同匹配字符串的状态集,提出了一种编号编码压缩机制.通过理论证明,集合切分编码利用状态机的已匹配信息将编号存储改变为编号段存储,大幅压缩了具有相同转移字符串和目的状态的交叉转移路径,减少了TCAM表项数目.经理论分析和实验仿真,该算法不仅具有高搜索速率,而且可以减少大量相似表项,降低TCAM存储资源消耗,从而支持大容量的模式集.

关键词：模式匹配、三态内容寻址存储器(TCMA)、集合切分、有限状态机

所属期刊栏目：28

分类号：TP393(计算技术、计算机技术)

资助基金：国家"863"计划资助项目2009AA01A346;国家"973"计划资助项目20070B307102

在线出版日期：2011-09-21（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：2067-2069