# Fast Conflict Detection for Multi-Dimensional Packet Filters
## 4 An Efficient Conflict Detection Algorithm for Non-Prefix Fields
### Relationships of Non-Prefix Field Combined Comparison  
After defining the comparison results of two filters in a single non-prefix field, all comparison result combinations of all non-prefix fields can be classified into the following three sets:  
1. Disjoint: In these compared non-prefix fields, the comparison results of at least one field are disjoint. When the compared non-prefix fields belong to the combination of this type, no conflict exists after combined detection regardless of the combination to which the comparison results of the prefix fields of filters \(F\) and \(G\) belong. For example, the non-prefix field combinations of filter pair (\(F_{1}\), \(F_{6}\)) are (LO, WC, TCP) and (HI, WC, UDP). Filter pair (\(F_{1}\), \(F_{6}\)) is not in conflict because the comparison results in fields Source port and Protocol are disjoint. 2. Overlap: The comparison results of these compared non-prefix fields all overlap. When these compared non-prefix fields belong to the combinations of a set that is the same as the 3_Det1_ set listed in Table 3 (i.e., the comparison result of prefix fields of filters \(F\) and \(G\) is Combination 1 defined in Section 4.1), it will conflict with the non-prefix field combination in this set after combined detection. In Section 4.1, we discussed the relationship between these three sets: 3_Det1_, 3_Det2_, and 3_Det3_. Therefore, in this set we can also find a set of three field combinations that matches 3_Det2_ and 3_Det3_. The set of non-prefix field combinations that these two sets match is derived as follows. 3_Det2_: In the non-prefix fields of \(F\) and \(G\) comparison, at least one field \(s\) exists and the value of \(F[s]\) is a wildcard, but not the value of \(G[s]\) (e.g., the destination port field of filter pair (\(F_{2}\), \(F_{4}\)) are WC, LO in Table 6). 3_Det3_: In \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Relationship** & **Disjoint** & **Overlap** & **Requiring Exact Comparison** \\ \hline \multirow{8}{*}{(**F, G**)} & **Port Field** & **Protocol Field** & **Port Field** & **Protocol Field** & **Port Field** & **Protocol Field** \\ \cline{2-6}  & & (TCP, UDP) & & & (HI, HI) & \\  & & (TCP, Other) & & (WC, *) & (IL, Both) & \\ \cline{1-1}  & (HI, LO) & (UDP, TCP) & (WC, *) & (*, WC) & (LO, LO) & \\ \cline{1-1}  & (LO, HI) & (UDP, Other) & (*, WC) & (TCP, TCP) & (Both, HI) & \\ \cline{1-1}  & & (Other, TCP) & & (UDP, UDP) & (Both, LO) & \\ \cline{1-1}  & & (Other, UDP) & & & (Both, Both) & \\ \hline \hline \end{tabular}
\end{table} 
Table 7: All comparison combinations of two filters \(F\) and \(G\) in a single non-prefix field. the non-prefix fields of \(F\) and \(G\) comparison, at least two fields \(s\) and \(t\) exist, the value of \(F[s]\) is wildcard, and the value of \(G[s]\) is not; or the value of \(F[t]\) is not wildcard and the value of \(G[t]\) is wildcard (e.g., the destination port and protocol fields of filter pair (\(F_{7}\), \(F_{8}\)) are (WC, Both) and (TCP, WC) in Table 6). 3. Requiring exact comparison: In these compared non-prefix fields, the comparison results of at least one field require exact comparison, whereas the comparison results of other fields overlap. When the compared non-prefix fields belong to the combination of this set, exact comparison is required after combined detection regardless of the combination to which the comparison results of the prefix fields of filters \(F\) and \(G\) belong. For example, if the combinations of filter pair (\(F_{1}\), \(F_{5}\)) are (LO, WC, TCP) and (LO, WC, WC), the comparison results of filter pair (\(F_{1}\), \(F_{5}\)) can be determined only after exact comparison of the source port field. To distinguish among three sets 3_Dset_1, 3_Dset_2, and 3_Dset_3, we divide the overlapped set of three compared fields into three disjoint sets. The method selects the combinations that satisfy the conditions of 3_Dset_3 set as distinguished from 3_Dset_1 set and includes them in an independent set 3_Dset_3'.