A Heuristic Algorithm for Reconstructing a Packet Filter with Dependent Rules

概要

論文の詳細を見る
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.