# An Efficient Parallel Algorithm for Detecting Packet Filter Conflicts
## 1 Introduction
Therefore, conflict detection must be executed for every newly added or updated filter to prevent conflicts and ensure the correctness of the packet classification. Consequently, the efficiency of conflict detection influences network performance. It has been demonstrated that determining the minimum number of resolve filters in a filter database is an NP-hard problem [3; 6]. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Filter** & **Source IP Address** & **Destination IP Address** & **Action** \\ \hline \(a\) & 00* & * & Accept \\ \(b\) & * & 00* & Reject \\ \(c\) & 11* & * & Accept \\ \(d\) & * & 11* & Reject \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Example of 2D filter database. Figure 1: Rectangular presentation of filters. Diversified network services will appear continuously, due to the development trend of the Internet, and the transmission speed and data volume will continue to increase. Regarding the filter database in routers, the number of filters will increase significantly. In addition, due to the deployment of IPv6 and the development of software-defined networks [7], filters should deal with more content, and the number of fields to match in conflict detection is much greater than the number of fields in traditional network architecture. These new types of network protocols or services may increase conflict-detection complexity. Currently, most conflict-detection algorithms can only handle 2D conflict detection, and for practical operation, additional dimensions other than the source/destination IP address must be included. Although some 2D conflict-detection algorithms can be extended to handle more dimensions for conflict detection, they require a large memory space. Therefore, designing an efficient conflict-detection algorithm is still a challenge. In packet classification applications, the classification process for each packet is independent. Due to the development trend of CPUs, researchers have investigated packet classification on multicore CPUs [8; 9; 10; 11; 12]. However, from the viewpoint of parallelism, the number of cores is not sufficiently high, and the scale of performance improvement is limited. Compared with a CPU, a general-purpose GPU has a large number of cores and can offer a superior parallel computing capability. Because the reduced dependence of data and control makes them more appropriate for the parallelism on multi-core and many-core systems. Many researchers have attempted to use GPUs to solve computing intensive problems in related domains [13; 14; 15; 16; 17; 18; 19; 20; 21; 22; 23; 24; 25]. Similarly, each filter is independent while executing conflict detection, and the field content matching does not require complex computations. Thus, conflict detection can be executed in parallel to improve performance significantly. In this study, we propose two parallel algorithms that can solve five-dimensional (5D) filter conflict problems. First, we formally defined the conflict-detection problem. To develop efficient conflict-detection algorithms, we divided a 5D filter into two parts based on the field format. We then derived the conditions under which both filters must hold if they conflict. Based on these conditions, we developed a filtering mechanism that reduced the number of comparisons for each filter during conflict detection. With the proposed filtering mechanism, each filter experienced different comparisons, resulting in inefficient parallel processing in the GPU because of workload imbalance among threads. Therefore, we propose a scheme for workload balancing to further improve the parallel computing performance. The remainder of this paper is organized as follows. Section 2 reviews existing conflict-detection algorithms and briefly introduces the GPU architecture. In Section 3, we propose a simple 5D conflict-detection algorithm. In Section 4, we present our proposed general parallel conflict-detection algorithm (the GPCDA) and enhanced parallel conflict-detection algorithm (the EPCDA).