一组提高存储效率的深度包检测算法

随着深度包检测规则数目的剧烈增长,为了适应网络处理的需求,必须对表示正则表达式的dfa(deterministicfiniteautomata,确定的有限自动机)进行高效的存储.一方面,对dfa的状态点数目进行压缩,提出了一种复合的fsm(有限自动机)的构造方法,通过对正则表达转化成dfa的状态点数目复杂度的分析,将不同复杂度的正则表达式采用不同的方式构建dfa,使得所有平方级和指数级复杂度的状态点数目降低到了线性级.另一方面,对dfa的状态转移数目进行压缩,给出了一种高效的压缩算法,即wd2fa(weighteddelayedinputdfa,带权延迟dfa)算法,对于任意复杂度的正则表达式都可以将状态转移数目压缩为原来的5%左右,相对于d2fa(delayedinputdfa,延迟的dfa)有更好的压缩能力,并且使得d2fa是wd2fa在权值为0情况下的特例.实验结果表明,有限自动机的状态点数目能够控制在线性级,并且在状态点压缩的基础上将状态转移数目压缩为原来的7%.