共 4 条
数据包过滤规则的快速匹配算法和冲突检测
被引：13
作者：
田大新
刘衍珩
李永丽
唐怡
机构：
[1] 吉林大学计算机科学与技术学院
[2] 东北师范大学计算机科学系
来源：
关键词：
数据包过滤;
Trie结构;
二分查找法;
过滤规则;
冲突检测;
D O I：
暂无
中图分类号：
TP393.08 [];
学科分类号：
0839 ;
1402 ;
摘要：
通过分析数据包过滤技术中的性能瓶颈,提出了过滤规则的快速匹配算法BSLT.该算法采用Trie数据结构存储规则表,并只在叶节点存储相应规则,节省了存储空间,其空间复杂度为O(NW),查找的时间复杂度为O(W);在匹配时采用二分法进行查找,提高了匹配速度,匹配的时间复杂度为O(N).实验证明BSLT的吞吐率在100条规则内比顺序匹配算法提高了近20%,而且规则越多,BSLT的优势越明显.此外,分析了数据包过滤技术的另一个问题———规则冲突,给出了冲突的理论证明和查找算法.实验证明该算法能准确地检测出冲突规则.
引用
收藏
页码：1128 / 1135
页数：8
相关论文