## 2 Related Work  
Rule reordering has been considered to decrease latency associated with packet classification. Studies highlighted through experimental evidence that ordered ACLs could reduce packet processing time [5]. The study did not however, consider the conflicts that may exist between different rules in an ACL. A subsequent paper does consider rule reordering, however only a simplistic treatment is given by organizing similar rules into classes, individual rule reordering and conflicts are not considered [6].  
Anomalies in firewall databases using algorithmic techniques have been identified [3] and subsequent work presented a method to introduce early rejection rules for the most commonly matched traffic, providing dynamic updates as traffic flows change [7].  
Several schemes have been proposed for storing filtering rules in alternative data structures which facilitate faster lookup times than linear lists. This is achieved by representing the rules as a decision tree [8,9]. Hash tables are also considered for packet classification using a single memory lookup however such schemes exhibit worst-case exponential space complexity which limits their use in devices with limited memory capacity [10].  
Hardware solutions to the latency problem have been developed using Ternary Content Addressable Memory (TCAMs). These evaluate all rules in the packet filter in parallel and return the rule first matching in a single memory lookup [11]. Due to their low density they are only able to handle a small number of rules [12]. TCAMs are typically only found in expensive high-end core routers [13].  
Most of the work has been carried out on individual routers and there has been comparatively little research undertaken into optimization of packet filters in a single domain. Algorithms have been proposed for identifying anomalies and implementing these in the form of a software tool which allows a network administrator to provide anomaly free policy editing and creation [14, 15, 16, 17, 18, 19, 20].  
Anomalies present in multiple packet filters traversed by a packet within a domain have been studied and several types of anomalies identified as being similar to those found for single sets of filtering rules [19]. The use of binary decision diagrams (BDD's) to search for anomalies in distributed firewalls using static analysis techniques resulted in a firewall analysis tool being produced utilizing these techniques[20].  
A protocol was developed for the detection and elimination of redundancies between two adjacent firewalls located in neighboring domains under different administrative control [21]. The protocol allows the firewalls to cooperate to exchange filtering information without revealing the content of the neighboring firewall, a potential security risk. The protocol was implemented with a variety of real-world and synthetic firewalls which showed that up to 49% of redundant rules can be safely removed.  
The significance of the definition of a security policy as the basis for an implementation was shown in [22]. Applications have been created to automate the conversion of a security policy into a set of rules for use in routers e.g., Guarddog [23] but other than manufacturer's recommendations [24] little work has been carried out on optimization within a domain.