# ITOC: An Improved Trie-Based Algorithm for Online Packet Classification
## 4 Experimental Results
### Simulation Results  
Herein, we give out the results of the simulations using different threshold values. The simulations are aimed to find out proper thresholds for the implementation and other simulations. The results are shown in Tables 1-3. The simulation used three types of rulesets, which contain 10 k rules. The results show thatthe numbers of tries generated for the rulesets change when the thresholds change. For different types of rulesets, the trend of trie number changing is different. Considering all the datasets, we finally choose the value of AVE Form as 2000. Because 2000 is the best threshold for IPC datasets and a better threshold for FW datasets and ACL datasets. For other thresholds, things are similar. We choose the WC Form threshold as 10,000 and the Form switch threshold as 2000, respectively. Then, we demonstrated the effectiveness of the trie choosing optimization of ITOC. We got the average update latency and average lookup time of the methods with and without optimization using three types of IPv4 5-tuple rulesets in three sizes generated by ClassBench-ng. We added the rule into the table and calculated the average update latency. \begin{table}
\begin{tabular}{l c c c c c c c c c} \hline \hline
**Dataset** & **100** & **200** & **500** & **800** & **1000** & **2000** & **3000** & **4000** & **5000** \\ \hline ACL & 10 & 7 & 6 & 5 & 5 & 5 & 5 & 4 & 4 \\ FW & 16 & 11 & 9 & 8 & 8 & 7 & 7 & 9 & 10 \\ IPC & 11 & 7 & 7 & 7 & 7 & 6 & 9 & 10 & 11 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Performance of different AVE Form thresholds (WC Form threshold: 10,000, Form Switch threshold: 2000). \begin{table}
\begin{tabular}{l c c c c c c c c} \hline \hline
**Dataset** & **2000** & **3000** & **4000** & **5000** & **6000** & **7000** & **8000** & **9000** & **10,000** \\ \hline ACL & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 \\ FW & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 \\ IPC & 6 & 6 & 8 & 8 & 8 & 8 & 8 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Performance of different WC Form thresholds (AVE Form threshold: 2000, Form Switch threshold: 2000). \begin{table}
\begin{tabular}{l c c c c c c c c} \hline \hline
**Dataset** & **1000** & **2000** & **3000** & **4000** & **5000** & **6000** & **7000** & **8000** \\ \hline ACL & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 \\ FW & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 \\ IPC & 6 & 6 & 8 & 8 & 8 & 8 & 8 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Performance of different Form Switch thresholds (AVE Form threshold: 2000, WC Form threshold: 10,000). Then, we tested the lookup interface using the test packets data. The test packets data are generated from the rulesets, and in the data, every rule in the rulesets could find a packet matching itself. The results are shown in Figure 5.  
According to the results, we can find that the trie choosing optimization reduced the average update latency, especially in the FW and IPC datasets. For ACL datasets, the performance of the optimization is not as good as it for the other datasets. The larger trie number led to a longer lookup time in some experimental results. We suppose that the performance of the trie choosing optimization is related to the content of rulesets. In ACL datasets, wildcards mostly exist in source port field, and most rules in ACL datasets have an exact match source IP field. Although, in FW and IPC datasets, there are many wildcards in both IP match fields. In FW datasets, over half of the rules have IP match fields of which all mask bytes are 0x00. The differences between the datasets result in different performance of the optimization. Then we compare the lookup performances of ITOC and some recent algorithmic approaches, represented by PartitionSort, TupleMerge, and TSS. The results are shown in Figure 6.  
Compared to other algorithms, ITOC achieves the shortest average lookup time or the second shortest average lookup time in most datasets. Considering ITOC could process multiple lookup requests at once while the other algorithms could not, we believe ITOC will have more advantages in actual work scenes.