A Fast Matching Algorithm and Conflict Detection for Packet Filter Rules

Tian Daxin; Liu Yanheng; Li Yongli; Tang Yi

Journal of Computer Research and Development > 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.

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.

PDF (451 KB)

A Fast Matching Algorithm and Conflict Detection for Packet Filter Rules

1(College of Computer Science and Technology, Jilin University, Changchun 130012) 2(Department of Computer Science, Northeast Normal University, Changchun 130024)

More Information

Published Date: July 14, 2005

Graphical Abstract

Abstract

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.
- packet filters,
- trie construction,
- binary search,
- filter rules,
- conflict detection

FullText(HTML)

References (0)

[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.