# Fast Conflict Detection for Multi-Dimensional Packet Filters
## 4 An Efficient Conflict Detection Algorithm for Non-Prefix Fields
### Lookup Table Construction  
Based on the analysis in Section 4.3, we can divide all comparison results of non-prefix fields into five cases. In order to implement our proposed algorithm, for each conflict case, we create a comparison result lookup table by listing each matching result. To minimize the memory requirement for the comparison result lookup table, we use binary code to represent the list of classes for port and protocol fields, and list corresponding values for the results, as shown in Tables 8 and 9, respectively. The binary codes of two filters are combined in serial to form a 12-bit-length index value. For example, the index value is (100001, 000001) after filters \(F_{1}\) and \(F_{2}\) in Table 6 are combined. Each index value indicates the information content of the non-prefix fields of the two filters. According to the conflicting comparison combinations defined in Table 3, the corresponding values of the comparison results can be defined. During non-prefix field conflict detection, we determine whether an exact comparison action is required based on the comparison results, or determine whether conflicts exist based on the comparison results of prefix fields. Table 10 provides an example of a comparison result lookup table. Finally, we use Figure 3  
Figure 2: Five results of combined comparison. to show the overall process of our 5D conflict detection flow. When two compared filters \(F\) and \(G\) are in conflict during prefix field comparison, we must read and combine the binary code serials of \(F\) and \(G\), perform an index value search to obtain the corresponding value for a comparison result, and finally combine the detection process to obtain the final results. If the final results are disjoint, then exact comparison is not required in order to shorten the overall conflict detection time. For example, during conflict detection of filters \(F_{2}\) and \(F_{3}\) in Table 3, the comparison result of prefix fields is equal, then prefetching the binary code serials of filters \(F_{2}\) and \(F_{3}\) is (000001, 001000) which represent as (WC, WC, TCP) and (WC, LO, WC). The comparison result of index value (000001, 001000) is 100 which belongs to 3_Dset3_. Finally, we determine that filters \(F_{2}\) and \(F_{3}\) are in conflict without an exact comparison because the comparison result satisfies Combination 3 defined in Section 4.1. Similarly, we determine that filters \(F_{6}\) and \(F_{7}\) in Table 3 do not have conflict without an exact comparison because the comparison using (010010, 000001) as the index value of the lookup table result is 000. Here, we conclude that the greater the number of exact comparisons that are filtered, the faster conflict detection will be. \begin{table}
\begin{tabular}{c c} \hline \hline
**(Filter \(F\), Filter \(G\))** & **Code of Comparison Result** \\ \hline (000000, 00000) & 011 \\ (000000, 000001) & 011 \\ (00000, 000010) & 011 \\ \(\vdots\) & \(\vdots\) \\ (00001, 001000) & 100 \\ \(\vdots\) & \(\vdots\) \\ (111111, 111101) & 000 \\ (111111, 111111) & 001 \\ (111111, 111111) & 001 \\ \hline \hline \end{tabular}
\end{table} 
Table 10: The comparison result lookup table. Figure 3: The process flow of 5D conflict detection. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Port Field** & **Code** & **Protocol Field** & **Code** \\ \hline WC & 00 & WC & 00 \\ HI & 01 & TCP & 01 \\ LO & 10 & UDP & 10 \\ Both & 11 & Other & 11 \\ \hline \hline \end{tabular}
\end{table} 
Table 8: Code of port and protocol field. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Comparison Result** & **Code** & \\ \hline Disjoint & 000 & \\ Requiring exact comparison & 001 & \\ Set 3_Dset1_ & 010 & \\ Set 3_Dset2_ & 011 & \\ Set 3_Dset3_ & 100 & \\ \hline \hline \end{tabular}
\end{table} 
Table 9: Code of the combined comparison results. The size of the entire lookup table is \(2^{12}\) (the number of index values) \(\times\) 3 (the number of bits required by the matching result) = 3 \(\times\) 2\({}^{12}\) bits. In other words, only 1.5 KB is needed.