基于TCAM的低能耗正则表达式匹配算法  

Low-power TCAM for regular expression matching

作　　者：丁麟轩[1] 黄昆[2] 张大方[1] 

机构地区：[1]湖南大学信息科学与工程学院,湖南长沙410082 [2]中国科学院计算技术研究所,北京100190

出　　处：《通信学报》2014年第8期162-168,178,共8页Journal on Communications

基　　金：国家重点基础研究发展规划("973"计划)基金资助项目(2012CB315805);国家自然科学基金资助项目(61173167;61100171)~~

摘　　要：提出一种基于字符索引的正则表达式匹配算法,对确定型有限自动机(DFA,deterministic finite automaton)的字母表和状态进行分离存储,构建字符索引,减少匹配时激活的TCAM块数,显著降低TCAM能耗。实验结果表明:与DFA相比,基于字符索引的DFA(CIDFA,character-indexed DFA)在能耗上平均减少了92.7%,在存储空间开销上平均减少了32.0%,在吞吐量上平均提高了57.9%。A character-indexed regular expression matching algorithm was presented to address the limitations of TCAM power consumption. This algorithm used the idea of separating the alphabet table from the states in deterministic finite automaton （DFA） for building a character index, in order to reduce the number of activated TCAM blocks, which in turn translated low TCAM power. Experimental results showed that proposed algorithm reduces the TCAM power by 92.7% on average as well as the TCAM space usage by 32.0% on average, and improves the matching throughput by 57.9% on average compared to previous solutions based on DFA.

关 键 词：正则表达式匹配 字符索引 分块存储 低能耗 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]