# Fast Conflict Detection for Multi-Dimensional Packet Filters
## 4 An Efficient Conflict Detection Algorithm for Non-Prefix Fields
### Combined Detection Method for 5D Conflict Detection  
The comparison results of prefix fields \(x\) and \(y\) of \(F\) and \(G\) can be divided into the following three combinations except for the empty set (Condition 1 defined in Section 3):  
**Combination 1**. : \((F[x]\subset G[x])\wedge(F[y]\supset G[y])\)__  
Because the comparison results of \(F\) and \(G\) in the prefix fields already satisfy Condition 2 defined in Section 3, the conflict conditions can be reached after the final combined detection, when the comparison results of non-prefix fields are not empty. The prefix field comparison results of filter pairs \((F_{1}\), \(F_{5})\), \((F_{1}\), \(F_{6})\), \((F_{4}\), \(F_{8})\), and \((F_{7}\), \(F_{8})\) in Table 2 belong to this type. After combined detection, \((F_{1}\), \(F_{5})\), \((F_{4}\), \(F_{8})\), and \((F_{7}\), \(F_{8})\) are conflicting filter pairs. By contrast, filter pair \((F_{1}\), \(F_{6})\) is not in conflict because \(F_{1}[\textit{Protocol}]\cap F_{6}[\textit{Protocol}]=\varnothing\). **Combination 2**. : \((F[x]\subseteq G[x])\wedge(F[y]\subset G[y])\)__  
In this combination, the values of the prefix field of \(F\) are the strict subset of \(G\), or the comparison results of \(F\) and \(G\) are equal in field \(x\), whereas \(F[y]\) is the strict subset of \(G[y]\). To reach conflict conditions after the combined detection, the comparison results of \(F\) and \(G\) in non-prefix fields must not be empty, and at least a field \(s\) causes the relationship \(F[s]\supset G[s]\) to be valid. The prefix field comparison results of filter pairs \((F_{1}\), \(F_{7})\), \((F_{2}\), \(F_{4})\), \((F_{3}\), \(F_{4})\), \((F_{5}\), \(F_{7})\), and \((F_{6}\), \(F_{7})\) in Table 2 belong to this type. After combined detection, \((F_{2}\), \(F_{4})\), \((F_{3}\), \(F_{4})\), and \((F_{5}\), \(F_{7})\) are conflicting filter pairs. Although the comparison results of filter pair \((F_{1}\), \(F_{7})\) in non-prefix fields are not empty, no field \(s\) causes the relationship \(F[s]\supset G[s]\) to be valid. Similarly, filter pair \((F_{6}\), \(F_{7})\) is not in conflict because \(F_{6}[\textit{Protocol}]\cap F_{7}[\textit{Protocol}]=\varnothing\). \begin{table}
\begin{tabular}{c c c c c c} \hline \hline \multirow{2}{*}{**Filter**} & **Source IP** & **Destination IP** & \multirow{2}{*}{**Source Port**} & **Destination Port** & **Protocol** \\  & **Address** & **Address** & & & \\ \hline \(F_{1}\) & 000* & 01* & 80 & * & TCP \\ \(F_{2}\) & 100* & 01* & * & * & TCP \\ \(F_{3}\) & 100* & 01* & * & 60 & * \\ \(F_{4}\) & 10* & 0* & * & 0–1023 & TCP \\ \(F_{5}\) & 00* & 011* & 0–1023 & * & * \\ \(F_{6}\) & 00* & 011* & 1024–65,535 & * & UDP \\ \(F_{7}\) & 0* & 0* & * & * & TCP \\ \(F_{8}\) & * & 000* & * & 1000–5000 & * \\ \hline \hline \end{tabular}
\end{table} 
Table 2: An example of a 5D filter database. **Combination 3**. : \((F[x]=G[x])\wedge(F[x]=G[x])\)  
In this combination, all values of prefix fields of \(F\) are equal to those of \(G\). To reach conflict conditions after combined detection, the comparison results of \(F\) and \(G\) in non-prefix fields must not be empty, and at least two fields \(s\) and \(t\) cause the relationship \((F[s]\supset G[s])\wedge(F[t]\subset G[t])\) to be valid. The prefix field comparison results of filter pairs (\(F_{2}\), \(F_{3}\)) and (\(F_{5}\), \(F_{6}\)) in Table 2 belong to this type. Because filter pair (\(F_{2}\), \(F_{3}\)) contain fields Destination port and Protocol, which produce \(F_{2}[\textit{Protocol}]\subset F_{3}[\textit{Protocol}]\) and \(F_{2}[\textit{Destination port}]\supset F_{3}[\textit{Destination port}]\), filter pair (\(F_{2}\), \(F_{3}\)) is in conflict. Because \(F_{5}[\textit{Source port}]\cap F_{6}[\textit{Source port}]=\varnothing\), (\(F_{5}\), \(F_{6}\)) is not in conflict.