# A New Bloom Filter Architecture
## 5 Performance Evaluation
### Comparison between Theoretic and Simulation Results  
From Label (8), the _indeterminable_ probability (\(P(I_{t})\)) for our input sets is  
\[P(I_{t})=\frac{1}{3}p_{ic}^{k}+\frac{2}{3}p_{oc}^{k} \tag{11}\]  
because \(\frac{1}{3}\) of each input set has the names included in the corresponding routing set, and the remaining \(\frac{2}{3}\) has names not included in the set. However, in the search procedure for an input, since not only is the input itself queried but also are substrings (prefixes) of the input, several queries for each input occur until the matching face is returned, and hence the probability should be calculated in consideration of the number of queries. Since some substrings are name prefixes included in the routing set while others are not included in the set, all of the substrings that are queried should be considered when calculating the probability. Table 6 shows the notation and definition of the query types. The number of queries of each type is obtained from the simulation results. Hence, the _indeterminable_ probability (\(P(I_{t})\)) for the queries of our input sets is  
\[P(I_{t})=\frac{Q_{tp}+Q_{ii}}{Q_{t}}p_{ic}^{k}+\frac{Q_{fp}+Q_{oi}+Q_{n}}{Q_{t }}p_{oc}^{k}. \tag{12}\]  
\(Q_{tp}+Q_{ii}\) refers to the queries for the hash keys (inputs and substrings) included in the routing set and \(Q_{fp}+Q_{oi}+Q_{n}\) refers to the queries for the hash keys (inputs and substrings) not included in the routing set. Simulations are carried out by only constructing the \(p\)-BF for the same routing set as the size of \(p\)-BF increases, then querying the \(p\)-BF from the longest level for an input name. According to Table 6, the _indeterminable_ rate in the simulation is defined as \begin{table}
\begin{tabular}{l l} \hline \hline
**Symbol** & **Meaning** \\ \hline \(Q_{tp}\) & Number of queries with true positives \\ \(Q_{fp}\) & Number of queries with false positives \\ \(Q_{ii}\) & Number of queries for hash keys included in routing set among queries with _indeterminable_ \\ \(Q_{oi}\) & Number of queries for hash keys not included in routing set among queries with _indeterminable_ \\ \(Q_{n}\) & Number of queries with negatives (negatives are always true) \\ \(Q_{t}\) & Number of total queries (\(Q_{tp}\)+\(Q_{fp}\)+\(Q_{ii}\)+\(Q_{oi}\)+\(Q_{n}\)) \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Notation and definition of query types. Figure 5: Worst-case number of off-chip memory accesses. \[P(I_{s})=\frac{Q_{ii}+Q_{ai}}{Q_{t}}. \tag{13}\]  
According to Table 6, the _false face return_ rate in the simulation is defined as  
\[P(F_{s})=\frac{Q_{fp}}{Q_{fp}+Q_{oi}+Q_{n}}. \tag{14}\]  
If output faces are returned for the queries (\(Q_{fp}+Q_{oi}+Q_{n}\)) for the hash keys not included in the routing set, they are false faces. Figure 6 shows the _indeterminable_ rate for the \(p\)-BF, comparing between the theoretic result (described in Section 4) and simulation result, and Figure 7 shows the _false face return_ rate for the \(p\)-BF. As shown in Figures 6 and 7, the simulation results are close to the theoretic results. As the size of the \(p\)-BF increases, the theoretical probabilities and simulation rates decrease similarly. In Figure 7a, it is shown that _false face return_ does not occur in the simulation set 1  
a matching level and the other Bloom filter for returning an output face. The number of elements programmed to the Bloom filters in our proposed architecture is minimized by applying a level-priority trie. Since the proposed architecture is sufficiently small to be stored in on-chip memories, the FIB lookup performance is greatly improved by only querying the on-chip Bloom filters without accessing the off-chip hash table. The off-chip hash table is only accessed for the case where _indeterminable_ results are returned at the second phase, and the simulation results show that more than 99.99% of the inputs obtain output faces by only querying Bloom filters stored in on-chip memories. conceptualization, H.B. and H.L. ; methodology, H.L. ; software, H.B. ; validation, H.B.