## 3 Satellite IP Route Lookup Using Cuckoo Bloom Hybrid Filter
### Theoretical Performance Analysis on CBHF  
In this section, we discuss the theoretical performance of the proposed CBHF, including the false positive probability, the average number of subtrie accesses, and the lookup time. According to the IPv4 prefix partitioning scheme recommended in Reference [31] (i.e., Level 1 contains prefixes in /1 to /8; Level 2 contains prefixes in /9 to /16; Level 3 contains prefixes in /17 to /24; Level 4 contains prefixes in /25 to /32), Level 3 and Level 4, containing the most potential subtries (\(2^{17}\) and \(2^{25}\), respectively), are set to the popular levels in the CBHF, and the rest of levels are set to unpopular. Therefore, the CBHF in PR-Trie comprises two Bloom filters and two cuckoo filters. In Section 2, certain formulas of the false positive probability of the Bloom filter and cuckoo filter are obtained. Note that Equation (8) applies only to an almost full hash table. Now, let us consider a more general case where hash addresses are uniformly distributed, the false positive probability of the cuckoo filter can be expressed as  
\[f_{\text{CF\,max}}=1-\left(1-\frac{1}{2^{f}}\right)^{2b\cdot\alpha}\approx \frac{2b\cdot\alpha}{2^{f}}=\frac{2n}{m\cdot 2^{f}}, \tag{10}\]where all variables are referred to in Section 2 (the same applies below). Thus, the false positive probability of the proposed CBHF (seen as a whole, and the subscript \(i\) represents the level) is calculated as  
\[f_{\text{CBHF}}=1-\prod_{i=1}^{4}(1-f_{i})\approx 1-\prod_{i=1}^{2}[1-(0.6185)^{ \frac{m_{i}}{n_{i}}}]\cdot\prod_{i=3}^{4}(1-\frac{2n_{i}}{m_{i}\cdot 2^{f}}), \tag{11}\]  
where we assume that Bloom filters are always in the optimal case, and this is clearly desirable due to the dynamic reconfiguration of FPGA. The number of subtrie accesses required to compute the correct LPM for an input IP address is determined by the number of matching filters. For an IP address \(x\) matching a subtrie in Level \(l\), we will first inspect the levels of high priority if there are false positives in the levels of priority greater than Level \(l\). Therefore, the average number of additional subtrie accesses required for the input IP address \(x\) is  
\[N_{\text{add}}(l)=\sum_{i>l}^{4}f_{i}, \tag{12}\]  
considering the worst case in which \(l=0\) (i.e., \(x\) matches a default prefix) and all the filters produce false positives and, thus, the average number of total subtrie accesses per lookup can be upper bounded as  
\[N_{\text{avg\,max}}=N_{\text{add}}(0)+1=\sum_{i=0}^{4}f_{i}+1\approx\sum_{i= 1}^{2}(0.6185)^{\frac{m_{i}}{n_{i}}}+\sum_{i=3}^{4}\frac{2n_{i}}{m_{i}\cdot 2 ^{f}}+1. \tag{13}\]  
Note that Equation (13) gives the average number of subtrie accesses due to the false positives, and for the worst case mentioned above, the number of required subtrie accesses obviously is \(N_{\text{worst}}=4+1=5\) (the default prefix constitutes one access here). However, the average number of subtrie accesses is generally lower than the estimated value using Equation (13) in practical implementation, because of the relative priority of filters. In more detail, for a lookup that has been hit by the level of high priority, whether there are any false positives in the filters of lower priority makes no difference to the query results. For this reason, we define a weighting factor \(w_{i}\), which is stated as  
\[w_{i}= \begin{cases}\prod_{j=i+1}^{4}(1-f_{j}),&i=1,2,3\\ \\ 1,&i=4\end{cases} . \tag{14}\]  
Hence, the average number of subtrie accesses per lookup can be further refined as  
\[N_{\text{avg}}=\sum_{i=1}^{4}w_{i}\cdot f_{i}+1=\sum_{i=1}^{3}\prod_{j=i+1}^{ 4}(1-f_{j})f_{i}+f_{4}+1. \tag{15}\]  
In real systems, the speed for a single lookup is determined by the total time of a direct hit and additional subtrie accesses. Thus, the lookup time of our proposed architecture can be calculated as  
\[T_{\text{PR-Trie}}=T_{1}+(N_{\text{avg}}-1)\cdot T_{\text{add}}, \tag{16}\]  
where \(T_{1}\) and \(T_{\text{add}}\) denote the time of a direct hit and additional subtrie accesses, respectively.