Optimising Rule Order for a Packet Filtering Firewall

A heuristic approximation algorithm that can optimise the order of firewall rules to minimise packet matching is presented. It has been noted that firewall operators tend to make use of the fact that some firewall rules match most of the traffic, and conversely that others match little of the traffic. Consequently, ordering the rules such that the highest matched rules are as high in the table as possible reduces the processing load in the firewall. Due to dependencies between rules in the rule set this problem, optimising the cost of the packet matching process, has been shown to be NP-hard. This paper proposes an algorithm that is designed to give good performance in terms of minimising the packet matching cost of the firewall. The performance of the algorithm is related to complexity of the firewall rule set and is compared to an alternative algorithm demonstrating that the algorithm here has improved the packet matching cost in all cases.