# ITOC: An Improved Trie-Based Algorithm for Online Packet Classification
## 3 The Proposed Algorithm
### Update Latency Prediction  
To evaluate the potential update latency, we design a latency prediction algorithm. The algorithm predicts the latency by calculating the number of potential changing nodes in the trie merging process. As we know, the trie merging process is an iteration of the node merging process, and the process will call itself several times. Each time the process calling itself, one more node will be changed. If we mark the iteration time as \(N\) and the self-calling time as \(A\), the time complexity of the trie merging process is  
\[ \begin{split} T_{m}&=T_{N}\\ &=A_{N}*T_{N-1}+T\\ &=A_{N}*(A_{N-1}*T_{N-2}+T)+T\\ &=\sum_{i=0}^{N}\prod_{j=0}^{i}A_{j}*T\\ &=O(NA^{N})\end{split}  \tag{1}\]  
where \(A\) is the average time of self-calling in each iteration. However, it could take a long time for us to get the exact \(A_{j}\) number, so we design a prediction formula. As the number \(A_{j}\) is determined by the new rule node content, current node number, and child node number of current nodes, so our prediction will consist of these parameters. The first element is new rule node content. We divide the rule contents into two types: catch-all and exact match. We introduce a parameter called wildness to describe the contents. Wildness is a parameter of the match fields in rules. The wildness parameters of different types of fields are calculated in different ways. The definition of rule wildness is as following. \[Wildness= \begin{cases}\frac{Num_{0}}{Num_{0}},&\text{for ternary field;}\\ \frac{MAX-MIN}{KANCE},&\text{for range field;}\\ \frac{Length_{prefix}}{Length_{field}},&\text{for prefix field.}\end{cases}  \tag{2}\]  
To simplify the problem, we will only consider the ternary case in the following sections, and we will treat every byte of the rule as a match field. In this paper, we will treat a byte as a catch-all byte if the wildness is bigger than 0 and treat a byte as an exact match byte if the wildness is 0. The rule content type influences the number of child nodes that will be involved in trie merging. In the trie merging process, an exact byte will involve only one child node, and a catch-all node will involve all child nodes of current nodes. The second element is current node number. In trie merging process, current node number of this iteration is just the result of the last iteration. Therefore in the formula, we will calculate and remember the current number of each level, and the result of this level will be used in the next calculation. The last element is the child node number of current nodes. It is easy to get the node number of each level in the trie. However, it is difficult to get the child node number of current nodes. To simplify the question, we only consider two typical child node distributions: uniform distribution and extremely skewed distribution. Uniform distribution means that all nodes in this level have the same number of child nodes. We suppose that an empty trie is with uniform distribution of child node. With more rules added into the trie, the child node distribution becomes skew gradually. Comparing with uniform trie models, skewed trie models are more accurate but complex. We should know the skew of every node to calculate the expectation. So we first put forward the prediction of uniform distribution case. When a rule is added to a trie with uniform distribution, the prediction value in each level is  
\[F_{0}=1,F_{i}= \begin{cases}F_{i-1},&W_{i}=0;\\ F_{i-1}\times\frac{N_{i}}{N_{i-1}},&W_{i}>0.\end{cases}  \tag{3}\]  
\(N_{i}\) is the node numbers in each level of the trie, and \(F_{i}\) is the predicted value in the i-th level of the trie. So the total value is  
\[F_{total}=\sum F_{i} \tag{4}\]  
The actual child node distribution of the trie is not uniform generally, so when we use this formula for uniform cases to predict update latency, there will be a difference between the actual changing node number and the calculated one. When the distribution is slightly skewed, the difference is small, and we can still use the formula to predict update latency.