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]	Wu Haibo, Liu Hui, Sun Yi, Li Jun. A Concurrent Conflict Transaction Optimization Method for Consortium Blockchain Hyperledger Fabric[J]. Journal of Computer Research and Development, 2024, 61(8): 2110-2126. DOI: 10.7544/issn1000-1239.202220644
[2]	Yang Bo, Guo Haoran, Feng Junhui, Li Ge, Jin Zhi. A Rule Conflict Detection Approach for Intelligent System of Internet of Things[J]. Journal of Computer Research and Development, 2023, 60(3): 592-605. DOI: 10.7544/issn1000-1239.202110941
[3]	Cai Tao, Wang Jie, Niu Dejiao, Liu Peiyao, Chen Fuli. A High Throughput NVM Storage System Based on Access Request Conflict Detection[J]. Journal of Computer Research and Development, 2020, 57(2): 257-268. DOI: 10.7544/issn1000-1239.2020.20190526
[4]	Zhu Suxia, Ji Zhenzhou, Li Dong, Zhang Hao. A Cyclic Memory Race Recording Algorithm Implemented with Hardware Signatures[J]. Journal of Computer Research and Development, 2014, 51(5): 1149-1157.
[5]	Zhou Hang, Huang Zhiqiu, Hu Jun, Zhu Yi. Real-Time System Resource Conflict Checking Based on Time Petri Nets[J]. Journal of Computer Research and Development, 2009, 46(9): 1578-1585.
[6]	Zhang Xiaoqiang, Peng Lin, Peng Yuanxi, and Xie Lunguo. A Lightweight Directory Based Algorithm for STM[J]. Journal of Computer Research and Development, 2008, 45(9): 1517-1523.
[7]	Li Lin and Lu Xianliang. An Algorithm for Detecting Filters Conflicts Based on the Intersection of Bit Vectors[J]. Journal of Computer Research and Development, 2008, 45(2): 237-245.
[8]	Li Xiangjun, Meng Luoming, and Jiao Li. Problems in Results of Policy Conflict Resolutions and Detection and Resolution Methods in Network Management Systems[J]. Journal of Computer Research and Development, 2006, 43(7): 1297-1303.
[9]	Mao Tianlu, Wang Zhaoqi, Xia Shihong. An Algorithm for Collision Detection and Response Between Human Body Model and Cloth in 3D Garment Simulation[J]. Journal of Computer Research and Development, 2006, 43(2): 356-361.
[10]	Yao Jian, Mao Bing, and Xie Li. A DAG-Based Security Policy Conflicts Detection Method[J]. Journal of Computer Research and Development, 2005, 42(7): 1108-1114.