## 5 Optimization and Evaluation on CBHF
### Performance Evaluation  
Since the satellite IP route lookup architecture is implemented on FPGA, the CBHF structure can be easily modified. In other words, it allows upgrading the configuration of filters in space missions. Hence, the performance of filters is affected by the routing table the satellite IP router maintains. Figure 11 shows the data of the prefix length distribution in each routing prefix set for testing.  
Figure 10: Illustration of a counting Bloom filter querying the membership of elements \(x\), \(y\), and \(z\).  
First, we extract subtries to generate the PR-Trie data structure for each routing prefix set. The number of subtries in each level and the total subtries in each set are shown in Table 2. It is shown that there are many more subtries that need to be maintained in Level 3 than other levels, which is consistent with the filter strategies that we have assumed previously. Note that there are a few subtries in Level 4, but it is desirable to use the cuckoo filter, since it has a higher space efficiency. In more detail, considering the case in which there are many potential subtries (in lookup), but few stored in the filter, we should maintain a large enough array but few elements have been inserted if using the Bloom filter.  
Table 3 reports the detailed configuration of the CBHF structure. As shown, for the Bloom filters of Level 1, there are at most two elements due to the one-bit subtrie index (i.e., IP [31]), which makes these filters safely work without the counters, and thus the width is \(1+0=1\) bit (array \(+\) counter). For the cuckoo filters of Level 3 and Level 4, the number of hash functions (\(N\)) is always \(1+1=2\) (\(h_{1}()\) and \(f()\)), and the widths are \(4\times 8=32\) bits and \(4\times 16=64\) bits (cell \(\times\) fingerprint) accordingly. In addition, all the hash indexes in the system are generated by the family of cyclic redundancy check (CRC) functions, including the CRC-12, CRC-16, CRC-32, CRC-48, CRC-64, etc., which can be easily implemented with a shift register and some exclusive-OR gates on FPGA. The total memory requirement for a CBHF is shown as well.  
According to Equations (2) and (10), we can obtain the theoretical false positive probability of each filter in the CBHF. Furthermore, we compute the false positive probability of the CBHF using Equation (11). Table 4 shows the above false positive probability according to the configuration of the CBHF. In addition, a simulation is run for each system configuration, where we perform lookups of all the remaining elements (which have not been inserted) for Level 1 and Level 2, and 100 k lookups for different random elements that have not been inserted in Level 3 and Level 4. The results are also summarized in Table 4.  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Routing** & \multicolumn{5}{c}{**Level**} \\ \cline{2-6}
**Prefix Set** & **1 (1–8 Bits)** & **2 (9–16 Bits)** & **3 (17–24 Bits)** & **4 (25–32 Bits)** & **Total Subtries** \\ \hline
1 k & 1 & 129 & 895 & 4 & 1029 \\
5 k & 2 & 352 & 3279 & 64 & 3697 \\
25 k & 2 & 266 & 14,648 & 76 & 14,992 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Number of subtries in each level for testing routing prefix sets.  
Figure 11: Prefix length distribution of testing routing prefix sets.  
Note that, in fact, the results for Level 1 are free from false positives, thus we recalculate the theoretical false positive probability of the CBHF. The results show that each filter in the CBHF remains a stable false positive probability through dynamic reconfiguration, which adopts the conventions that the Bloom filter will be reconstructed when its occupancy exceeds 60%, and the occupancy is 90% for the cuckoo filter. In theory, the CBHF structure can achieve an accuracy rate of almost 95% with less storage space. And, our simulation results show that higher accuracy rates can be reached in practical configurations.