# A Distance-Encoded Bloom Filter for Fast NDN Name Lookup
## 4 Evaluation
Figure 14 shows the distribution of \(\langle sd,\,ld\rangle\) values for all nodes in R0. Nodes with \(sd=0\) are all prefix nodes. In particular, when both \(sd\) and \(ld\) are 0, the node is a leaf prefix, accounting for the largest proportion (54%) of the total. A positive result in DEB indicates there exists a matching node at the current level, which is identified by the existence of a valid \(sd\). The valid \(sd\) refers to the one that not only exists but also falls within a given range [\(L\), \(U\)]. Thus, the false positive rate (FPR) of DEB corresponds to the effective false positive probability (\(eF PPD\)) defined in Equation (6). DEB sets one or two bits per node for each hash function, resulting in a higher FPR compared to other schemes. In this context, a positive result in Bloom filters indicates that there is a matching node at the current level, regardless of whether the node is a prefix node or an intermediate node. The primary performance goal is to reduce both on-chip and off-chip memory accesses required to find the longest matching prefix. Finding the longest matching node may require more Bloom filter and hash table accesses. DEB can predict whether a node at the current level is a prefix, whereas other schemes lack this prefix prediction capability. If the \(sd\) value in the Bloom filter output \(<\)\(sd\), \(ld\)\(>\) is zero, DEB identifies the node at the current level as a prefix. This capability allows the hash table to store only prefix nodes, thereby reducing the number of off-chip memory accesses. In Figure 15, the FPR for prefix prediction in DEB is specifically marked as DEBpfx. The figure shows that DEBpfx achieves an FPR comparable to that of other schemes, even though the others focus on only node prediction. As shown in Figure 15, the FPR of DEB increases across R0, R1, and R2 with rising prefix density. It implies that FIBs with more prefixes yield higher FPRs despite having the same total number of nodes. Whereas other schemes set one bit per node for each  
Figure 14: Distribution of \(\langle sd,\,ld\rangle\) values for all nodes in R0. Figure 15: False positive rate (FPR). hash function, DEB sets either one or two bits depending on the _sd_ and _ld_ values. If _sd_ equals _ld_, only one bit is set for that node, which is referred to as single-bit-set nodes. As prefix density increases, the portion of single-bit-set nodes decreases. It leads to more set bits and, consequently, more false positives. Nevertheless, even under very high prefix density, the FPR is bounded because leaf prefixes, which constitute a large portion of the FIB, always have distances where _sd_ equals _ld_. Despite a high FPR, DEB achieves fewer on-chip and off-chip memory accesses due to the next search range information based on distance values, as illustrated in Figures 16, 17 and 19. The name lookup process involves two types of memory accesses: one to the Bloom filter in on-chip memory and the other to the hash table in off-chip memory. The average number of Bloom filter accesses and hash table accesses is compared in Figures 16 and 17, respectively. DEB outperforms all other schemes in both types of memory accesses. Since DEB determines the next search range using \(\langle\)_sd_, _ld_\(\rangle\), it requires fewer Bloom filter accesses than other schemes that rely on binary search. Figure 16 shows that in DEB, the Bloom filter is accessed 1.75 to 1.96 times, whereas in other schemes, the Bloom filter is accessed approximately three times on average. Additionally, DEB demonstrates a lower average number of hash table accesses compared to other schemes. The number of hash table accesses increases when a lookup in the hash table fails. As shown in Figure 17, schemes that store only prefix nodes in the hash table (BS-a-p and BS-m-p) require more accesses. In those schemes, a node identified as present by the Bloom filter may not necessarily be a prefix node but rather a non-prefix intermediate node.