%0 Journal Article
%T 一组提高存储效率的深度包检测算法
%A 于强？
%A 霍红卫？
%J 软件学报
%P 149-163
%D 2011
%R 10.3724/SP.J.1001.2011.03724
%X 随着深度包检测规则数目的剧烈增长,为了适应网络处理的需求,必须对表示正则表达式的dfa(deterministicfiniteautomata,确定的有限自动机)进行高效的存储.一方面,对dfa的状态点数目进行压缩,提出了一种复合的fsm(有限自动机)的构造方法,通过对正则表达转化成dfa的状态点数目复杂度的分析,将不同复杂度的正则表达式采用不同的方式构建dfa,使得所有平方级和指数级复杂度的状态点数目降低到了线性级.另一方面,对dfa的状态转移数目进行压缩,给出了一种高效的压缩算法,即wd2fa(weighteddelayedinputdfa,带权延迟dfa)算法,对于任意复杂度的正则表达式都可以将状态转移数目压缩为原来的5%左右,相对于d2fa(delayedinputdfa,延迟的dfa)有更好的压缩能力,并且使得d2fa是wd2fa在权值为0情况下的特例.实验结果表明,有限自动机的状态点数目能够控制在线性级,并且在状态点压缩的基础上将状态转移数目压缩为原来的7%.
%K 深度包检测
%K 正则表达式
%K 多模式匹配
%K 复合的fsm
%K d2fa(delayed
%K input
%K dfa)
%K wd2fa(weighted
%K delayed
%K input
%K dfa)
%U http://www.jos.org.cn/ch/reader/view_abstract.aspx?file_no=3724&flag=1