# Fast Conflict Detection for Multi-Dimensional Packet Filters
## 4 An Efficient Conflict Detection Algorithm for Non-Prefix Fields
### Characteristic Analysis and Classification for Non-Prefix Field  
Without any pre-computed information, complete information regarding non-prefix fields of the two to-be-compared filters must be fetched prior to non-prefix field conflict detection, and the results of combined detection can be determined after a series of logic comparison processes. We call this an exact comparison. If exact comparison is used during every combined detection, it may cause too many memory accesses and increase the detection time. If the results of combined detection can be obtained based on the pre-computed information prior to executing an exact comparison, then only part of the combined detections require exact comparison, hence the number of memory accesses can be reduced. Therefore, we analyze the characteristics of the non-prefix field and use the \begin{table}
\begin{tabular}{c c} \hline \hline
**Results of Prefix** & \\
**Fields of \(F\) and \(G\)** & **Corresponding to the Combination of Non-Prefix Fields** \\ \hline Combination 1 & 3_Dset1_: \(\forall_{3_{5}\leq F\leq 5}(F[t]\ \cap\ G[t])\
eq\varnothing\) \\ Combination 2 & 3_Dset2_: \(\forall_{3_{5}\leq F\leq 5}(F[t]\ \cap\ G[t])\
eq\varnothing\ \wedge\exists_{3_{5}\leq F\leq 5 }(F[s])\) \\ Combination 3 & 3_Dset3_: \(\forall_{3_{5}\leq F\leq 5}(F[t]\ \cap\ G[t])\
eq\varnothing\ \wedge\exists_{3_{5}\leq S \leq 5}3_{3_{5}\leq S\leq 5}((s\
eq t)\wedge(F[s]\supset G[s])\wedge(F[t]\subset G[t]))\) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: All combinations for 5D filter conflict. rarely pre-computed information to design a filtering algorithm so that the number of exact comparisons can be reduced. According to [33], the values of the source/destination port field can be divided into the following five classes, while the values of the protocol field can be divided into the following four classes, as shown in Tables 4 and 5, respectively:  
When a port field value is a type of AR or EM, it can be classified as an HI or LO based on its covered region. For example, if a field value belongs to an EM category and has an exact value of 23, it can be classified as an LO; if the field value is in an AR class and has an arbitrary range [2000:5000], it can be classified as an HI. However, a special case exists in which the AR category field value covers both HI and LO regions (e.g., number range [20:5000]). Since it cannot be exactly classified as HI or LO, we classify the field values of this classes as a new class called Both. Finally, the port field values can be classified into four new classes: WC, HI, LO, and Both. According to the statistics in [24], the common values of protocol fields contain TCP, UDP, and wildcard. The other protocol values are rare, so we can classify them as a new class called Other. Finally, the protocol field values are also classified into four classes: WC, TCP, UDP, and Other. Table 6 shows the classification results of the database in Table 2.  
After port and protocol fields are classified based on their values, the comparison results of a field can have the following three relationships:  
1. Disjoint: When the two compared port field values belong to HI and LO, respectively, we can determine that the comparison results of the two filters in this field must be an empty set because the values in these two classes are disjoint. For example, we cannot find a value that is located in both regions [1024:65,535] and [0:1023]. With the same method, except the case in which the protocol value is a wildcard, different protocols are disjoint.