# ITOC: An Improved Trie-Based Algorithm for Online Packet Classification
## 4 Experimental Results
### Simulation Results
Finally, we compared the performance of ITOC with the DPDK ACL library using the IPv4 ruleset datasets. We measured memory footprint, lookup time, and update latency of ITOC and DPDK ACL. After comparing the basic performances, we simulated and compared the overall performances of the two algorithms in online work scenes. In brief, ITOC had a bigger memory footprint, the same level lookup speed, and much shorter update latency comparing with DPDK ACL. So in online work scenes, ITOC has a better overall performance than DPDK ACL algorithm. Figure 5: Performance of online trie-based method with and without optimization. The memory footprint comparison is as following. As the trie structures are the main reason for the memory usage, we counted the nodes in tries. The implementations of ITOC and DPDK ACL use huge page memory provided by DPDK to achieve faster memory access. So we can compare the memory footprints using the APIs. The results are shown in Figure 7.  
As shown in Figure 7, ITOC has a larger memory footprint and more trie nodes. In most cases, ITOC only consumed 2 to 5 times more memory. Only in special cases, the memory footprints are bigger. ITOC consumes more memory due to the more nodes in the tries. Fortunately, since the memory is not the bottleneck of the implementation of our algorithm, the memory usage will not affect our algorithm. The lookup performance comparison is shown in Figure 8. As both DPDK ACL and ITOC provide two lookup interfaces, we compared four interfaces in the experiment. Figure 6: Lookup performance comparison. Figure 7: Node number and memory comparison. Figure 8 shows that the batch lookup interface of DPDK ACL is the fastest lookup interface. Our online method, ITOC, has the same level of lookup speed. In some cases, the single lookup interface of ITOC is faster than DPDK ACL. Meanwhile, for batch interface, the batch lookup interface of ITOC performs poorer than DPDK ACL in most of the datasets. Briefly, In some datasets, the batch interface performance of ITOC is close to or equivalent to DPDK ACL. Considering the online work scenes, we think the performance gap from the batch interface in the other datasets is acceptable. Then we compared the update latency of the two methods. The rules were added into tables in the same order. The results are shown in Figure 9.  
Figure 8: Average lookup time comparison. Figure 5.0 Average update latency comparison. As we know, the update process of ITOC, trie updating, is much simpler than the update process of DPDK ACL, trie rebuilding. The optimization which we designed for ITOC avoided huge update latency during the update process. So in the average update latency comparison, the performance of ITOC is much better than DPDK ACL. In the best case, the update latency of ITOC is only 6.85% of DPDK ACL. The result reveals attractive advantage of ITOC on update performance over DPDK ACL. At last, we designed a simulation to compare the overall lookup performances. In the simulation, the mixed input consists of lookup requests and update requests, which is similar to the actual online work scenes. We compared the processing time taken by each algorithm. The mixed inputs contain 10,000 requests, and the ratio of lookup requests to update requests in the inputs was set into three values: 1000:1, 100:1, and 10:1. As shown in Figure 10, the processing time of DPDK ACL is much longer than ITOC. With the ratio of the update requests in the mixed input increasing, the processing time difference became larger. The results show that, the small sacrifice in lookup speed is acceptable as it brings considerable better lookup update performance improvement and eventually provides better overall lookup performance in online work scenes.