# Fast Conflict Detection for Multi-Dimensional Packet Filters
## 1 Introduction  
With the rapid growth of the Internet, many advanced network services such as firewalls, differentiated services, policy-based forwarding, quality of services (QoS), and network security have been developed. To support these services, packet classification plays a crucial role in the Internet [1, 2, 3, 4]. Packet filters are the rules that routers use to classify incoming packets based on the header information. For supporting various network services, a filter typically contains five fields, including the source/destination IP addresses, the source/destination ports, and the protocol type [5]. An IP address field usually indicates a prefix. An IP address that matches a prefix indicates that the IP address contains the same prefix content. A port field usually indicates a range of values. For example, a port value \(v\) matches a range of [\(s\):\(e\)] if \(s\leq v\leq e\). The protocol field usually indicates an exact value. When the field content is expressed using *, it is regarded as a wildcard rule, indicating that the value of the field covers the entire range. For a packet \(P\) and a filter \(F\), we can say that \(P\) matches \(F\) if the corresponding fields of \(P\) match all fields of \(F\)[1]. Packet classification ambiguity occurs when a packet \(P\) matches two or more filters but the associated actions of matching filters are different [6]. In this situation, the classifier cannot correctly determine the actions that should be taken on \(P\). This may lead to incorrect packet classification and cause security vulnerabilities of firewall-similar services as well as data routing errors [6, 7, 8, 9]. When the aforementioned problems occur, a heavy burden is thrust upon Internet users. These problems also affect the transmission efficiency and reliability of the entire network. Therefore, it is essential to detect conflicts in a filter database to prevent incorrect classification [10]. An earlier study listed three possible solutions [6] that are accomplished by means of the following:Select the first filter in the database that matches \(P\). 2. Assign each filter a priority. From the set of filters that match \(P\), select the filter having the highest priority. 3. Assign each field a priority. From the set of filters that match \(P\), select the filter having the most specific field with the highest priority. However, these solutions cannot fully resolve conflicts. We use the two-dimensional (2D) filters in Table 1 for illustration. Suppose that the length of each field is 4 bits. The rectangles in Figure 1 are drawn according to the filters in Table 1, with overlapping regions indicating the conflict regions between filters. We give priority to the two conflicting filters and define \(F{\rightarrow}G\) to indicate that the priority of filter \(F\) is higher than that of filter \(G\). If a packet matches both filters \(F\) and \(G\), the packet will execute the associated action of \(F\). The priorities of the four overlapping filters in Figure 1 are set as follows: \(a{\rightarrow}b\), \(b{\rightarrow}c\), \(c{\rightarrow}d\), and \(d{\rightarrow}a\). However, the order of these four filters causes a cycle relationship. In this case, we cannot prevent conflicts by setting priorities because we cannot sort these four filters in an absolute order. Therefore, [PERSON] et al. [6] proposed a method of adding resolve filters to solve filter conflicts. In other words, the method adds a new filter to the overlapping region of two filters and assigns it a high priority to break the cycle. For example, adding a resolve filter \(e\): (001*, 001*) to the overlapping region of \(a\) and \(b\), and setting the priority of \(e\) higher than that of \(a\) and \(b\), solves the problem of filter conflicts. Although filter conflicts can be resolved by adding resolve filters, it is necessary to update the database which affects the effectiveness of database updates.