# Fast Conflict Detection for Multi-Dimensional Packet Filters
## 1 Introduction
Some Internet service applications such as intrusion detection, stateful filtering, and customer relationship management may frequently add or update filters [7; 11], which may conflict with existing filters in the filter database. Therefore, a conflict detection algorithm must be designed to determine all potential conflicts. This is necessary to ensure the security and user QoS whenever the database is updated with any filters, even when the new filters may not produce conflicts [12]. As Internet Protocol version 6 (IPv6) gradually gains popularity and the number of filters becomes greater, it is expected that new advanced network services will constantly emerge and dynamic filter updates will be more frequent. In addition, in the new generation network, architecture known as a software-defined network (SDN) [13], 12 or more filter fields must be compared. Packet classification technology must be able \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Filter** & **Source IP Address** & **Destination IP Address** & **Action** \\ \hline \(a\) & 001* & * & Accept \\ \(b\) & * & 001* & Reject \\ \(c\) & 110* & * & Accept \\ \(d\) & * & 110* & Reject \\ \hline \hline \end{tabular}
\end{table} 
Table 1: An example of a 2D filter database. Figure 1: Rectangular presentation of filters. to cope with these great changes [14]. To improve the efficiency of packet classification, many packet classification algorithms have been proposed and they can be divided into two implementation types: software-based [3; 11; 14; 15; 16; 17; 18] and hardware-based [4; 19; 20; 21; 22; 23]. Because conflict detection can ensure the correctness of packet classification, the conflict detection process must be performed whenever filters are updated. In this case, conflict detection performance must also be considered; otherwise, it will become the bottleneck of router performance. The majority of existing conflict detection algorithms can only detect conflicts for 2D filters. For greater practicality, the following three non-prefix fields must be considered: source port, destination port, and protocol fields. To extend conflict detection from two to more than two dimensions, the first problem encountered is the inconsistent data formats of fields. Using the same data structures to store the information of different fields is difficult. When processing these non-prefix fields, the previous works restrict the field to be either exact values or a wildcard [6], or by converting all the fields into prefixes [7]. However, the port field is usually represented as a range, and range-to-prefix conversion may cause filter replication. For example, suppose that the longest prefix length is 4, the range [1:14] can be represented by as many as six prefixes: 0001, 001*, 01*, 10*, 110*, and 1110. If the port field value of a filter is [1:14], this filter must have six replications so that six new filters can indicate the same range as the original filter. As the number of filters increases, the filter replication may cause the number of filters to grow exponentially. As a result, not only larger memory space but also longer time are required to perform the conflict detection. The objectives of this study are as follows: (1) to analyze the characteristics of non-prefix fields in five-dimensional (5D) filters; (2) to investigate the rules for determining whether two 5D filters conflict based on the results of the prefix field comparisons and the non-prefix field comparisons; and (3) to propose an efficient algorithm that can be used either to extend an existing 2D conflict detection algorithm to support 5D filters, or to increase the throughput of an existing 5D conflict detection algorithm. In our proposed algorithm, we divide the 5D conflict detection process into two parts. First, we obtain comparison combinations of two filters in prefix fields then, based on these combinations, we sum up the matching combinations of non-prefix fields to ensure that conflicts occur after combined detection.