# Fast Conflict Detection for Multi-Dimensional Packet Filters
## 5 Experimental Results
### Comparing Time Performance with Extended 5D Algorithms
\begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline \multirow{2}{*}{**Databases**} & \multicolumn{2}{c}{**5K**} & \multicolumn{2}{c}{**10K**} & \multicolumn{2}{c}{**20K**} \\ \cline{2-10}  & \multicolumn{2}{c}{**Average**} & \multicolumn{2}{c}{**Average**} & \multicolumn{2}{c}{**Average**} & \multicolumn{2}{c}{**Average**} & \multicolumn{2}{c}{**Detection Time**} & \multicolumn{1}{c}{**Speedup**} \\ \cline{2-10}  & \multicolumn{2}{c}{**SBV**} & \multicolumn{1}{c}{**Ours**} & \multicolumn{2}{c}{**SBV**} & \multicolumn{1}{c}{**Ours**} & \multicolumn{1}{c}{**SBV**} & \multicolumn{1}{c}{**Ours**} & \\ \hline ACL1 & 6.81 & 5.26 & 22.76\% & 13.59 & 11.06 & 18.62\% & 26.94 & 22.13 & 17.85\% \\ ACL2 & 7.82 & 5.72 & 26.85\% & 15.11 & 11.4 & 24.55\% & 27.61 & 22.11 & 19.92\% \\ ACL3 & 7.46 & 5.95 & 20.24\% & 13.89 & 11.5 & 17.21\% & 26.86 & 22.87 & 14.85\% \\ ACL4 & 7.43 & 6.01 & 19.11\% & 14.02 & 11.41 & 18.62\% & 26.86 & 22.65 & 15.67\% \\ ACL5 & 4.55 & 3.39 & 25.49\% & 9.9 & 7.83 & 20.91\% & 18.21 & 15.27 & 16.14\% \\ FW1 & 8.45 & 7.27 & 13.96\% & 15.82 & 14.28 & 9.73\% & 31.7 & 28.27 & 10.82\% \\ FW2 & 8.83 & 6.33 & 28.31\% & 15.93 & 12.53 & 21.34\% & 30.06 & 25.24 & 16.03\% \\ FW3 & 7.89 & 7.14 & 9.51\% & 15.76 & 14.13 & 10.34\% & 30.99 & 27.82 & 10.23\% \\ FW4 & 8.97 & 7.17 & 20.07\% & 15.82 & 13.3 & 15.93\% & 28.96 & 25.23 & 12.88\% \\ FW5 & 8.83 & 7.51 & 14.95\% & 15.99 & 14.67 & 8.26\% & 33.65 & 28.32 & 15.84\% \\ IPC1 & 7.59 & 5.85 & 22.92\% & 13.86 & 11.43 & 17.53\% & 26.41 & 22.9 & 13.29\% \\ IPC2 & 8.82 & 6.19 & 29.82\% & 15.87 & 12.51 & 21.17\% & 28.03 & 24.44 & 12.81\% \\ \hline \hline \end{tabular}
\end{table} 
Table 13: Average detection time required to detect conflicts for databases of three sizes. \begin{table}
\begin{tabular}{c c c c c c c c c c} \hline \hline \multirow{2}{*}{**Databases**} & \multicolumn{2}{c}{**5K**} & \multicolumn{2}{c}{**10K**} & \multicolumn{2}{c}{**20K**} \\ \cline{2-10}  & \multicolumn{2}{c}{**Average**} & \multicolumn{2}{c}{**Average**} & \multicolumn{2}{c}{**Average**} & \multicolumn{2}{c}{**Detection Time**} & \multicolumn{1}{c}{**Speedup**} & \multicolumn{2}{c}{**Detection Time**} & \multicolumn{1}{c}{**Speedup**} \\ \cline{2-10}  & \multicolumn{2}{c}{**Fast**} & \multicolumn{2}{c}{**Ours**} & \multicolumn{2}{c}{**Fast**} & \multicolumn{2}{c}{**Ours**} & \multicolumn{2}{c}{**Fast**} & \multicolumn{2}{c}{**Ours**} & \\ \hline ACL1 & 0.45 & 0.36 & 20.00\% & 0.69 & 0.62 & 10.14\% & 0.97 & 0.75 & 22.68\% \\ ACL2 & 8.15 & 6.83 & 16.20\% & 15.53 & 12.48 & 19.64\% & 28.59 & 23.24 & 18.71\% \\ ACL3 & 7.77 & 6.49 & 16.47\% & 12.55 & 10.7 & 14.74\% & 19.06 & 16.49 & 13.48\% \\ ACL4 & 5.77 & 5.11 & 11.44\% & 8.49 & 7.55 & 11.07\% & 16.21 & 14.44 & 10.92\% \\ ACL5 & 0.11 & 0.09 & 18.18\% & 0.13 & 0.09 & 30.77\% & 0.14 & 0.1 & 28.57\% \\ FW1 & 88.28 & 67.55 & 23.48\% & 362.74 & 232.61 & 35.87\% & 481.74 & 400.73 & 16.82\% \\ FW2 & 45.29 & 40.33 & 10.95\% & 91.31 & 79.31 & 13.14\% & 210.65 & 189.07 & 10.24\% \\ FW3 & 191.88 & 131.88 & 31.27\% & 441.27 & 353.3 & 19.94\% & 691.06 & 609.51 & 11.80\% \\ FW4 & 50.53 & 42.75 & 15.40\% & 140.17 & 119.9 & 14.46\% & 332.15 & 286.39 & 13.78\% \\ FW5 & 159.38 & 136.22 & 14.53\% & 464.03 & 395.66 & 14.73\% & 879.9 & 746.2 & 15.19\% \\ IPC1 & 4.7 & 4.17 & 11.28\% & 9.93 & 8.8 & 11.38\% & 19.69 & 17.27 & 12.29\% \\ IPC2 & 45.79 & 35.58 & 22.30\% & 109.85 & 93.73 & 14.67\% & 302.72 & 234.91 & 22.40\% \\ \hline \hline \end{tabular}
\end{table} 
Table 12: Average detection time required to detect conflicts for databases of three sizes. Remarkably, to perform 5D conflict detection, the SBV algorithm must additionally construct binary search tries and set bit vectors for these non-prefix fields. Besides additional memory space, constructing a corresponding data structure also increases the execution time. We list the execution time and memory space that the SBV algorithm requires in order to construct the additional data structure in the 20K filter databases.