IIAE CONFERENCE SYSTEM, The 5th IIAE International Conference on Industrial Application Engineering 2017 (ICIAE2017)

Font Size: 
Fast Conflict Detection for Two-Dimensional Packet Filters
Chun-Liang Lee, Chung-Yuan Huang, Tung-Yi Chen

Last modified: 2017-03-21

Abstract


Advanced network services such as firewall, differentiated services, and virtual private networks require network devices to perform packet classification. According to pre-defined rules (or filters), network devices classify incoming packets into different flows and execute the operation specified by the matching filter. However, two filters may overlap and leads to a conflict if the actions specified in the filters conflict. Filter conflicts may cause security breaches or quality-of-service failures. In this paper, we propose an algorithm that can efficiently detect and resolve filter conflicts. By analyzing the conditions that two conflicting filters must hold, our proposed algorithm can detect conflicts without complicated data structures. The time complexity of our proposed algorithm is O(n 2 ), and the space complexity is O(n), where n is the number of filters. Experimental results show that our proposed algorithm can reduce the average detection time per filter by 30% to 56% compared to the scalable bit vector (SBV) algorithm. Moreover, the memory required by our proposed algorithm is much smaller than that by the SBV algorithm.

Keywords


Packet Classification; Conflict detection

Full Text: PDF