文献类型：期刊文章

作　　者：田大新[1] 刘衍珩[1] 李永丽[2] 唐怡[1]

机构地区：[1]吉林大学计算机科学与技术学院,长春130012 [2]东北师范大学计算机科学系,长春130024

出　　处：《计算机研究与发展》

基　　金：吉林省自然科学基金项目(200305222)

年　　份：2005

卷　　号：42

期　　号：7

起止页码：1128-1135

语　　种：中文

收录情况：AJ、BDHX、BDHX2004、CSA-PROQEUST、CSCD、CSCD2011_2012、EI、IC、JST、RCCSE、SCOPUS、ZGKJHX、核心刊

摘　　要：通过分析数据包过滤技术中的性能瓶颈,提出了过滤规则的快速匹配算法BSLT.该算法采用Trie数据结构存储规则表,并只在叶节点存储相应规则,节省了存储空间,其空间复杂度为O(NW),查找的时间复杂度为O(W);在匹配时采用二分法进行查找,提高了匹配速度,匹配的时间复杂度为O(N).实验证明BSLT的吞吐率在100条规则内比顺序匹配算法提高了近20%,而且规则越多,BSLT的优势越明显.此外,分析了数据包过滤技术的另一个问题———规则冲突,给出了冲突的理论证明和查找算法.实验证明该算法能准确地检测出冲突规则.

关 键 词：数据包过滤 TRIE结构 二分查找法  过滤规则  冲突检测  

分 类 号：TP393]