ISSN 1000-1239 CN 11-1777/TP

• Paper • Previous Articles     Next Articles

A Fast Matching Algorithm and Conflict Detection for Packet Filter Rules

Tian Daxin1, Liu Yanheng1, Li Yongli2, and Tang Yi1   

  1. 1(College of Computer Science and Technology, Jilin University, Changchun 130012) 2(Department of Computer Science, Northeast Normal University, Changchun 130024)
  • Online:2005-07-15

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.

Key words: packet filters, trie construction, binary search, filter rules, conflict detection