Fast and memory efficient conflict detection for multidimensional packet filters

Chun Liang Lee*, Guan Yu Lin, Yaw-Chung Chen

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review


Packet classification plays an important role in supporting advanced network services such as Virtual Private Networks (VPNs), quality-of-service (QoS), and policy-based routing. Routers classify incoming packets into different categories according to pre-defined rules, which are called packet filters. If two or more filters overlap, a conflict may occur and leads to ambiguity in packet classification. In this paper, we propose an algorithm which can efficiently detect and resolve filter conflicts. The proposed algorithm can handle filters with more than two fields, which is more general than algorithms designed for two-dimensional filters.We use the synthetic filter databases generated by ClassBench to evaluate the proposed algorithm. Compared with the bit-vector algorithm, simulation results show that the proposed algorithm can reduce the detection times by over 84% for 10 out of 12 filter databases, and only uses less than 26% of memory space.

Original languageEnglish
Pages (from-to)205-211
Number of pages7
JournalAdvances in Intelligent and Soft Computing
Volume145 AISC
Issue numberVOL. 2
StatePublished - 2 Jul 2012
Event2011 2nd International Congress on Computer Applications and Computational Science, CACS 2011 - Bali, Indonesia
Duration: 15 Nov 201117 Nov 2011

Fingerprint Dive into the research topics of 'Fast and memory efficient conflict detection for multidimensional packet filters'. Together they form a unique fingerprint.

Cite this