# An Efficient Parallel Algorithm for Detecting Packet Filter Conflicts
## 3 Definition and Method of 5D Conflict Detection
### Conflict Detection for 5D Filters  
If two matching filters satisfy condition 1, we select any two fields to fulfill condition 2; we have 10 combinations of fields. Furthermore, because of the different formats of stored data for different fields, the conflict-detection process becomes complex and tedious if we match every combination individually. In addition, it is challenging to design an efficient data structure and algorithms to perform 5D conflict detection. Furthermore, the performance of GPU parallel computing is limited.  
To reduce the complexity of 5D conflict detection, we designed a simple detection algorithm that separated the 5D conflict-detection process into two parts, the matching of prefix fields (SA/DA, two fields) and non-prefix fields (SP/DP/Protocol, three fields). When matching two filters to verify whether they are conflicted, it first checks the prefix field matching result and matches the non-prefix field contents to determine whether a conflict will occur. By excluding the empty set, the matched result of prefix fields \(i\) and \(j\) contains three cases. For each case, we describe the combination of the non-prefix field content of filters \(f\) and \(g\) for conflict to occur.  
1. \(((f[i]\subset g[i])\wedge(g[j]\subset f[j]))\): This case indicates that the prefix fields of filters \(f\) and \(g\) conflict, as defined by [3]. Therefore, when the matched results of the non-prefix fields of \(f\) and \(g\) are all nonempty sets, \(f\) conflicts with \(g\). The filter pair \((F_{0},F_{1})\) belongs to this case because the non-prefix field matched results of \(F_{0}\) and \(F_{1}\) are all nonempty sets (Table 2).
2. \(((f[i]\subseteq g[i])\wedge(f[j]\subset g[j]))\): This case indicates that the prefix fields of \(f\) have at least one field content contained in \(g\). Thus, if the matched result of non-prefix fields of \(f\) and \(g\) are all nonempty sets, and there is a field \(s\) such that \((g[s]\subset f[s])\),\(f\) conflicts with \(g\). Both filter pairs, \((F_{0},F_{3})\) and \((F_{1},F_{2})\), belong to this case (Table 2); therefore, conflicts occurred in both cases. However, in the matching of non-prefix fields in \((F_{0},F_{3})\), it did not find any field \(s\) such that \((F_{3}[s]\subset F_{0}[s])\). Thus, \((F_{0},F_{3})\) did not have conflict.
3. \(((f[i]=g[i])\wedge(f[j]=g[j]))\): This case suggests that the contents in the prefix fields of \(f\) and \(g\) are equal. Therefore, when the matched results in the non-prefix fields of \(f\) and \(g\) are all nonempty, and we find any two fields \(s\) and \(t\) such that \(((g[s]\subset f[s])\wedge(f[t]\subset g[t]))\), then\(f\) and \(g\) have conflict. The filter pair, \((F_{2},F_{3})\), is categorized into this case because it can find the DP and protocol fields that satisfy condition 2, as defined in Section 3.1.  
Based on the above analysis, all filter pairs with conflicts should satisfy one of the above cases. In other words, we can focus on the above analysis to design a simple detection algorithm that can replace the original complicated matching process. The execution steps of the detection algorithm are as follows.  
1. It determines whether the matching result of the prefix fields of the filters satisfies any of the cases mentioned above. If it does, execute step 2; otherwise, terminate the process.
2. It matches the non-prefix field content based on the cases satisfied and then determines whether the matched result is the case for conflict to occur.