计算机研究与发展 ›› 2015, Vol. 52 ›› Issue (3): 681-690.doi: 10.7544/issn1000-1239.2015.20131255
丁麟轩1,黄昆2,张大方1
Ding Linxuan1, Huang Kun2, Zhang Dafang1
摘要: 深度包检测(deep packet inspection, DPI)是网络入侵检测与防御系统(network intrusion dete-ction and prevention system, NIDPS)的核心.基于三态内容可寻址存储器(ternary content addressable memory, TCAM)的正则表达式匹配算法提高了数据包的处理速度,成为DPI技术的一个重要研究方向.TCAM具有查找速度快、存储空间小等特性,且能耗与存储空间成正比.由于DFA的存储空间开销比较大,且存储空间大小随着DFA步长数的增加而指数倍增,基于TCAM的DFA面临高能耗的问题,特别是多步长DFA.提出一种基于并行字符索引的多步长正则表达式匹配算法(multi-stride parallel character-indexed DFA, PCIDFA),对确定型有限自动机(deterministic finite automaton, DFA)构造并行字符索引,通过比特位图取交集,减少匹配时激活的TCAM块数,显著降低TCAM能耗.实验结果表明:与多步长DFA相比,多步长PCIDFA在TCAM能耗上减少了99.8%以上,在TCAM存储空间开销上减少了48.5%~65.3%,在吞吐量上提高了1.9~2.6倍.
中图分类号: