# ITOC: An Improved Trie-Based Algorithm for Online Packet Classification
## 3 The Proposed Algorithm
### Optimization: Choose a Trie  
With the two prediction formulas, we design an optimization method for the trie update process. The optimization is aimed to avoid high update latency. With the merging predictions, we can know whether the latency would be high when a rule is added to a trie. Now the question is how to shorten the time when we know the time consuming would be too long. The idea is that although we cannot decide the order of rules, we can decide which trie the rule will be inserted into. In practice, a trie-based method will build another trie when the number of nodes in the trie is too big. As a result, there would be more than one trie. So we can build several tries in the build-up process. When we insert a rule, we choose one from the tries according to the latency predictions. For a trie, we will first use AVE Form to predict the latency. When we find the prediction is much less than the actual value, we will mark the trie as a bad trie and use WC Form to calculate latency predictions for it again. By finding a trie with a latency prediction lower than a threshold, we can avoid high update latency. Figure 4 shows the new insertion process, and the pseudocode of the new insert process is shown in Algorithm 1. ```
Input: the insert rule R, ruleset \(\mathbb{S}\) with tries \(\{T_{1}\ T_{2}\dots\ T_{n}\}\), threshold \(N_{t}\) Output: ruleset \(\mathbb{S}\) with tries
1 for\(T_{i}\) in \(\mathbb{S}\)do
2 if\(T_{i}\) is fullthen
3 continue;
4 elseif\(T_{i}\) is Goodthen
5 calculate prediction time \(N_{p}\) of R and \(T_{i}\) in AVE Form;
6 else
7 calculate prediction time \(N_{p}\) of R and \(T_{i}\) in WC Form;
8
9 end if
10 if\(N_{p}<N_{t}\)then
11 choose \(T_{i}\);
12
13 end if
14
15 end for
16 ifno\(T\) is chosenthen
17 init new trie \(T_{n+1}\) in \(\mathbb{S}\);
18 choose \(T_{n+1}\);
19
20 end if
21 insert R into the chosen \(T_{c}\);
22 generate lookup array of \(\mathbb{S}\);
23 get actual node operation time \(N_{a}\);
24 if\(N_{a}<N_{t}\)then
25 change \(T_{c}\) status into Bad;
26
27 end if
```  
**Algorithm 1**Insertion process with trie choosing. Although our optimization could shorten the latency of trie merging, we also need to consider the time cost of the optimization. Luckily, the time complexity of our optimization is negligible compared with the time complexity of trie merging. Our optimization consists of two steps: wildness calculation and prediction calculation. For wildness calculation, as the wildness is calculated for every byte individually, the time complexity \(T_{w}\) is:  
\[T_{w}=O(N) \tag{6}\]  
Figure 4: The update process of ITOC. where \(N\) is the number of bytes in the rule match fields. For prediction calculation, the prediction is the sum of the prediction of each level, and we calculate the prediction for all the tries in the worst case. So the time complexity of prediction calculation \(T_{p}\) is:  
\[T_{p}=kO(N) \tag{7}\]  
The time complexity of our optimization is the sum of the two steps, so the time complexity of our optimization \(T_{o}\) is:  
\[T_{o} =T_{w}+T_{p} \tag{8}\] \[=O(N)+kO(N)\]  
Because \(k\) is a limited value, the time complexity of our optimization is O(N). As calculated before, the time complexity of trie merging \(T_{m}\) is \(O(NA^{N})\) where A is the average time of self-calling in each iteration. As \(A\) is a value from [1; 255], the time complexity of trie merging is much bigger than our optimization. The operations in trie merging functions will take much more time than the calculations in our optimization. So we can conclude that the time cost of our optimization will not influence the update latency of the method. Additionally, the influence of our optimization on the lookup performance is slight. Our optimization does not change the lookup process and the lookup data structure, so the only factor of lookup performance changing is the number of tries. Generally, online trie-based methods will build more trie structures than offline ones.