A Heuristic Algorithm for Reconstructing a Packet Filter with Dependent Rules

Ken TANAKA  Kenji MIKAWA  Manabu HIKIN  

IEICE TRANSACTIONS on Communications   Vol.E96-B   No.1   pp.155-162
Publication Date: 2013/01/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.E96.B.155
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Network Management/Operation
packet filtering,  dependent rules,  filtering load reduction,  

Full Text: PDF(681KB)>>
Buy this Article

Network devices, such as routers or L3 switches, have a feature called packet-filtering for network security. They determine whether or not to pass arriving packets by applying filtering rules to them. If the number of comparisons of packets with rules increases, the time required for a determination will increase, which will result in greater communication delay. Various algorithms for optimizing filtering tables to minimize the load of packet filtering, which directly impacts the communication delay, have been proposed. In this paper, first we introduce an adaptive packet filter based on an algorithm that reconstructs the filtering table according to the frequency distribution of arrival packets. Next, we propose a new reconstruction algorithm based on grouping of dependent rules. Grouping dependent rules makes it possible to sort the rules in the table by the frequency of matching. Finally, we show the effectiveness of our algorithm by comparing it against previously reported algorithms.