## 3 Satellite IP Route Lookup Using Cuckoo Bloom Hybrid Filter  
In our previous work [30], we proposed the cuckoo Bloom hybrid filter (CBHF) structure, which can be used to accelerate a tri-based IP lookup algorithm called Tree Bitmap (TBM) [11]. The CBHF comprises three Bloom filters and a cuckoo filter based on the prefix partitioning scheme in the TBM. Specifically, a cuckoo filter for the subtries that belong to the popular level is maintained to reduce the false positive probability, while the subtries of each unpopular level are inserted in a Bloom filter. All of the filters are configured on-chip, and the proposed lookup architecture completes IP lookups by performing the TBM algorithm to access the off-chip next-hop information (NHI) table according to the query results of the CBHF. The above lookup architecture is shown in Figure 4.  
\begin{table}
\begin{tabular}{c c c} \hline \hline  & **Bloom Filter** & **Cuckoo Filter** \\ \hline False Negatives & no & no \\ False Positives & yes & yes \\ False Positive Probability & \(\left[1-\left(1-\frac{1}{m}\right)^{k\pi}\right]^{k}\) & \(1-\left(1-\frac{1}{2^{f}}\right)^{2k}\) \\ False Positive Probability \({}^{*}\) & \(\left(0.6185\right)^{\frac{\pi}{8}}\) & \(\frac{2b}{2^{f}}\) \\ Deletion Support & no & yes \\ LPM Algorithms & PBF, VBF & LACF \\ \hline \hline \end{tabular} \({}^{*}\) Approximate values under the optimal case.  
\end{table}
Table 1: Properties of the Bloom filter and cuckoo filter.  
Like most filter-based IP lookup schemes, the motivation of the proposed CBHF structure is to achieve only one off-chip memory access for a single lookup, without unnecessary access due to longest prefix matching (LPM). In addition, the proposed CBHF-based lookup architecture can provide higher memory efficiency since we utilize a trie data structure or, precisely, multi-trie in IP lookups.  
However, the TBM algorithm also has drawbacks. One of them is that a pair of bitmaps (i.e., the internal and external bitmaps) with a pointer used for each subtrie may require a considerable memory overhead, which is unpalatable in satellite IP route lookup. And the presence of pointers in the TBM also complicates the lookup operation. Hence, we must propose a new algorithm suitable for satellite IP route lookup.  
In Reference [31], we introduced a new IP lookup algorithm called Prefix-Route Trie (PR-Trie). This scheme considers a special coding concept for a hybrid of prefixes and routes, which we call Overlapping Hybrid Trie (OHT). It is important that using the OHT, the LPM process is converted into specific logic calculation instead of the pointer operation, and thus significantly reduces the lookup complexity. In addition, memory optimization for prefix partitioning is also considered in PR-Trie. However, the proposed PR-Trie architecture is implemented in parallel, and a discrete memory module is employed for each level while consuming a large amount of compute resources. Therefore, we consider introducing the CBHF into the PR-Trie algorithm to realize faster serial lookup based on the level priority, which can be more applicable in satellite IP route lookup.  
In this paper, we detail the serial version of PR-Trie architecture with a CBHF, and thus Section 4 is a completely new section. In our previous work [30], we briefly describe the parameter configuration of CBHF for typical routing tables in terrestrial networks, but the dynamic changes in these parameters are not evaluated, which has been largely supplemented in Section 5. In addition, we implement the proposed lookup architecture on FPGA, and the prototype system has been evaluated through comprehensive simulation and hardware implementation. Therefore, Section 6 is also a completely new section.