• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
Advanced Search
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

More Information
  • Published Date: July 14, 2005
  • 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.
  • Related Articles

    [1]Li Yuan, Yang Sen, Sun Jing, Zhao Huiqun, Wang Guoren. Influential Cohesive Subgraph Discovery Algorithm in Dual Networks[J]. Journal of Computer Research and Development, 2023, 60(9): 2096-2114. DOI: 10.7544/issn1000-1239.202220337
    [2]Li Xin, Liu Guiquan, Li Lin, Wu Zongda, Ding Junmei. Circle-Based and Social Connection Embedded Recommendation in LBSN[J]. Journal of Computer Research and Development, 2017, 54(2): 394-404. DOI: 10.7544/issn1000-1239.2017.20150788
    [3]Yuan Xinpan, Long Jun, Zhang Zuping, Luo Yueyi, Zhang Hao, and Gui Weihua. Connected Bit Minwise Hashing[J]. Journal of Computer Research and Development, 2013, 50(4): 883-890.
    [4]Jiao Jian, Yao Shan, Li Xiaojian. Research on Network Bidirectional Topology Discovery Based on Measurer by Spreading[J]. Journal of Computer Research and Development, 2010, 47(5): 903-910.
    [5]Jin Xin, Xiong Yan, Li Min, and Yue Lihua. A Connectible-Cell Based Topology Control Algorithm for Wireless Sensor Networks[J]. Journal of Computer Research and Development, 2008, 45(2): 217-226.
    [6]Liu Wei, Cui Li, Huang Changcheng. EasiFCCT:A Fractional Coverage Algorithm for Wireless Sensor Networks[J]. Journal of Computer Research and Development, 2008, 45(1): 196-204.
    [7]Yang Liu, Li Zhenyu, Zhang Dafang, Xie Gaogang. Topology Discovery with Smallest-Redundancy in IPv6[J]. Journal of Computer Research and Development, 2007, 44(6): 939-946.
    [8]Sun Yantao, Shi Zhiqiang, Wu Zhimei. Automatic Discovery of Physical Topology in Switched Ethernets[J]. Journal of Computer Research and Development, 2007, 44(2): 208-215.
    [9]Zhu Pengfei, Dai Yingxia, and Bao Xuhua. PKI-Based Mutual Connections Constrained with Discrepancy of Trust Domains[J]. Journal of Computer Research and Development, 2006, 43(10): 1804-1809.
    [10]Wen Yingyou, Zhao Jianli, Zhao Linliang, and Wang Guangxing. A Study of the Relationship Between Performance of Topology-Based MANET Routing Protocol and Network Coverage Density[J]. Journal of Computer Research and Development, 2005, 42(4): 684-689.
  • Cited by

    Periodical cited type(0)

    Other cited types(1)

Catalog

    Article views (1436) PDF downloads (758) Cited by(1)

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return