# Fast Conflict Detection for Multi-Dimensional Packet Filters
## 5 Experimental Results
### Comparing Time Performance with Extended 5D Algorithms  
In this subsection, we discuss the difference in performance between our proposed algorithm and the comparison method that the SBV algorithm employs for non-prefix field conflict detection. Because the original SBV algorithm cannot detect the conflicts defined in [6], we refer to the method provided in [10] to adjust the SBV algorithm so that it can detect these conflicts. Table 13 shows the average conflict detection time for every filter in different-sized databases. The data shows that our algorithm is 10% faster than the SBV algorithm in most databases. For databases FW1, FW3, and FW5, our algorithm does not improve the efficiency as obviously as do the other databases because the characteristics of the SBV algorithm include the filtering function. The SBV algorithm creates a binary search \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Databases**} & \multicolumn{2}{c}{**Statistics**} & \multicolumn{2}{c}{**Average Number of**} & \multicolumn{2}{c}{**Percentage Distribution of the Results of**} \\  & & **Non-Prefix Field** & \multicolumn{2}{c}{**Non-Prefix Field Comparisons**} & \multicolumn{2}{c}{**Non-Prefix Field Comparisons**} \\ \cline{2-7}  & **Number** & **Non-Prefix Field** & **Comparisons** & & & **Requiring** \\  & **of Filters** & **Non-Prefix Field** & **per Filter** & **Disjoint** & **Conflict** & **Exact** \\ \hline ACL1 & 19,912 & 188,707 & 9.48 & 23.38\% & 46.46\% & 30.16\% \\ ACL2 & 18,674 & 4,686,814 & 250.98 & 19.45\% & 69.62\% & 10.93\% \\ ACL3 & 19,049 & 3,576,805 & 187.77 & 64.70\% & 12.04\% & 23.25\% \\ ACL4 & 19,221 & 3,022,216 & 157.24 & 65.46\% & 11.06\% & 23.48\% \\ ACL5 & 13,585 & 994 & 0.07 & 75.96\% & 0.00\% & 24.04\% \\ FW1 & 18,643 & 38,711,274 & 2076.45 & 67.13\% & 20.45\% & 12.42\% \\ FW2 & 19,254 & 24,533,881 & 1274.22 & 0.00\% & 68.63\% & 31.37\% \\ FW3 & 17,743 & 39,051,434 & 2200.95 & 69.93\% & 13.10\% & 16.97\% \\ FW4 & 17,333 & 23,916,573 & 1379.83 & 59.04\% & 19.57\% & 21.39\% \\ FW5 & 17,470 & 42,750,196 & 2447.06 & 60.57\% & 21.78\% & 17.65\% \\ IPC1 & 19,477 & 3,532,940 & 181.39 & 32.49\% & 50.13\% & 17.38\% \\ IPC2 & 20,000 & 12,162,906 & 608.15 & 0.00\% & 66.90\% & 33.10\% \\ \hline \hline \end{tabular}
\end{table} 
Table 11: Performance evaluation for 20 K filter databases. trie for every to-be-compared field and the algorithm searches the target node of the binary search trie during detection. When \(k\) compared fields exist, the AND logic comparison results of \(k\)-bit vectors collected finally may overlap the detecting filters. In other words, the final results may exclude the sets that do not overlap the detecting filters. The effect is the same as the disjoint results in our comparison result lookup table. Therefore, if the ratio of disjoint sets is high in the database, the SBV algorithm can also filter out a considerable number of filter sets that do not require exact comparison. Table 11 shows the high ratios (more than 60%) of disjoint sets in databases FW1, FW3, and FW5. Similarly, the performance of databases ACL3 and ACL4 is less than that of other ACL databases. Although database ACL5 contains a high ratio of disjoint sets, the impact on its performance is not obvious because this database requires only few instances of exact comparison, on average. By contrast, if the ratio of confirmed conflicts in the comparison result query is high and the ratio of disjoint sets is relatively low (less than 40%), the SBV algorithm cannot filter out most filter sets that do not require exact comparison. Therefore, our algorithm performs much better than the SBV algorithm with the databases ACL1, ACL2, FW2, IPC1, and IPC2.