高级检索
    田大新, 刘衍珩, 李永丽, 唐 怡. 数据包过滤规则的快速匹配算法和冲突检测[J]. 计算机研究与发展, 2005, 42(7): 1128-1135.
    引用本文: 田大新, 刘衍珩, 李永丽, 唐 怡. 数据包过滤规则的快速匹配算法和冲突检测[J]. 计算机研究与发展, 2005, 42(7): 1128-1135.
    Tian Daxin, Liu Yanheng, Li Yongli, Tang Yi. A Fast Matching Algorithm and Conflict Detection for Packet Filter Rules[J]. Journal of Computer Research and Development, 2005, 42(7): 1128-1135.
    Citation: Tian Daxin, Liu Yanheng, Li Yongli, Tang Yi. A Fast Matching Algorithm and Conflict Detection for Packet Filter Rules[J]. Journal of Computer Research and Development, 2005, 42(7): 1128-1135.

    数据包过滤规则的快速匹配算法和冲突检测

    A Fast Matching Algorithm and Conflict Detection for Packet Filter Rules

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

       

      Abstract: The bottleneck of the packet filter method is produced due to a large number of filter rules to be checked. A fast matching algorithm BSLT (binary search in leafs of tries) is presented, which is based on trie construction and only stores the matching rules in the leaf nodes, and thus it consumes less memory space. The space complexity is O(NW) where N is the number of filter rules, W is the maximum number of bits specified in the destination or source fields. Binary search is used in finding the matching rule in the leaf nodes, which speeds up matching. The complexities of both searching time and matching time are O(W) and O(N) respectively. Experimental performance evaluations show that the throughput of BSLT is about 20% greater than the sequence matching algorithm. Another problem, the rule conflict, is proved and a conflict detection algorithm is given. Experiments prove that the algorithm can detect the conflict correctly.

       

    /

    返回文章
    返回