基于频繁子串的报文分类算法

摘要

针对现有报文分类算法难以胜任高速网络中大规模规则的报文分类应用需求的不足，在元组空间算法的基础上提出了以频繁子串替代元组的新算法，通过压缩散列方法构建的散列表数目来减少匹配过程的表空间查找数目，达到提高匹配性能的目的。介绍了规则存放和匹配的算法细节，以及对前缀描述、任意区间描述的扩展。从存储开销、匹配时间复杂度和动态更新时间复杂度等方面，对新算法和元组空间算法进行了对比，并实验测试了两种算法的匹配用时和更新用时。最后，总结了新算法的性能以及优缺点。