# An Efficient Parallel Algorithm for Detecting Packet Filter Conflicts
## 1 Introduction  
Packet classification techniques play a significant role in providing advanced network services, such as packet filtering, quality of services (QoS), security monitoring, and virtual private networks [1]. The packet classifier runs on the Internet router to classify the received packets into different flows based on predefined rules called packet filters. Different network services may use different header fields to classify the packets. For example, in IPv4, five header fields are typically used in packet filters; these include the source/destination Internet protocol (IP) address, the source/destination port, and the protocol type. A filter, \(F\), with \(d\) fields is called a \(d\)-dimensional filter, expressed as \(F=\langle[1],f[2],...,f[d]\rangle\), in which the content in the \(i\)th field \(f[i]\) could be a variable-length prefix, an exact value, a range, or a wildcard, indicating that all values are valid for that field. For packet \(P\) and filter \(F\), if all selected packet headers correspond to the values in their associated fields in \(F\), we say that packet \(P\) matches filter \(F\). For example, a two-dimensional (2D) filter \(F=\{\)140.113. *, *, *\(\}\), source IP address (SA) with prefix 140.113.xxx.xxx, and any destination IP address (DA) will match \(F\). Therefore, packet \(p_{1}=\{\)140.113.1, 8.8.8.8\(\}\) matches \(F\), but \(p_{2}=\{\)140.114.1.1, 8.8.8.8\(\}\) does not. Each filter exhibits an associated action specifying how to treat those packets that match the filter. When a packet matches multiple filters with different actions, filter conflict occurs, resulting in ambiguity in packet classification. For example, Table 1 presents a 2D filter database for firewall applications. Assuming that theIP address length is four bits, incoming packet \(p_{1}\) = (0001, 1000) will match filter \(a\) and be accepted. Another incoming packet, \(p_{2}\) = (0001, 0000), matches filters \(a\) and \(b\). Because \(a\) and \(b\) exhibit different actions, they cannot decide whether the packet should be accepted or rejected, resulting in a conflict. The conflicting actions of \(a\) and \(b\) may raise security vulnerabilities, QoS failures, or routing errors [2; 3], depending on the application used. Three possible solutions can be applied to solve the conflict problem [3]. 1. Select the first matching filter in the filter database. 2. Assign each filter a priority and select the matching filter with the highest priority. 3. Assign each field a priority and select the matching filter with the most specific matching field with the highest priority. However, none of the above methods can fully solve the conflict problem. Figure 1 depicts a 2D representation based on the contents of Table 1, and the overlapped areas indicate conflicts between filters. Let \(a\to b\) indicate that when a packet matches filters \(a\) and \(b\) simultaneously, the action associated with filter \(a\) is selected. In other words, filter \(a\) has a higher priority than filter \(b\). If we set \(b\to c\), \(c\to d\), and \(d\to a\), we observe that priority setting may lead to \(a\to a\), which is a contradiction. There is no way to find a priority sequence with no conflicts. Therefore, resolve filters [3] have been developed to solve the filter-conflict problem. The idea is to add a new filter to the overlapped area of two conflicting filters and set a higher priority to resolve the conflict. In Figure 1, resolve filter \(e\) is generated for the overlapped area of filters \(a\) and \(b\). Similarly, the other three overlapped areas require associated resolve filters. For every resolve filter generated, it is necessary to ensure that it does not conflict with the other filters. In addition, some applications must update packet filters frequently [4]. For example, within one millisecond, several access controls or QoS filters may be updated, or several thousand filters may be changed, due to the dynamic creation or the deletion of the virtual routers [5].