# A Distance-Encoded Bloom Filter for Fast NDN Name Lookup
## 5 Conclusions  
In this paper, we propose a novel name lookup scheme for NDN that employs a distance-encoded Bloom filter to enhance lookup efficiency. The primary challenge in NDN name lookup is identifying the longest matching prefix in the FIB. For any given content name, multiple matching prefixes may exist, and the longest one should be identified among them.  
Figure 19: Average number of off-chip memory accesses.  
Figure 18: Hash table lookup failure rate.  
Hash table-based approaches can efficiently determine whether a given prefix matches an entry in the FIB. However, multiple hash table lookups may be required to find the longest matching prefix since these approaches cannot determine the longest prefix length in advance. Given the large size of the FIB, the hash table must be stored in off-chip memory. Therefore, it is crucial to minimize table accesses to optimize performance.  
Several pre-checking techniques using Bloom filters, which indicate the possible presence of a prefix before accessing the hash table, help reduce hash table accesses. A binary search approach in a Bloom filter can reduce the number of Bloom filter accesses, as the search range is halved each time the Bloom filter is queried.  
Our proposed approach further narrows the search range by utilizing the distance to descendant prefixes. Two types of distance values--shortest distance (_sd_) and longest distance (_ld_)--are encoded into the Bloom filter. The Bloom filter based on these distance values provides not only membership testing but also a narrower search range compared to binary search. This narrower search range reduces Bloom filter accesses required to identify the longest matching prefix. Moreover, our proposed Bloom filter can identify the matching prefix nodes, whereas conventional Bloom filters identify only the matching nodes regardless of whether they are prefix nodes or non-prefix nodes. As a result, only prefix nodes are stored in the hash table in the proposed scheme, which reduces hash collisions and minimizes overall off-chip memory accesses.  
Through experiments with large FIBs and name trace datasets, we demonstrated that the proposed distance-encoded Bloom filter significantly reduces both on-chip Bloom filter accesses and off-chip hash table accesses compared to other lookup schemes. Our results show that the proposed scheme achieves up to 44% fewer Bloom filter accesses and a lower hash table lookup failure rate. Furthermore, it stores only prefix nodes in the hash table, which reduces off-chip memory accesses and improves overall lookup performance.  
Conceptualization, J.K.; formal analysis, J.K.; investigation, M.-C.K.; methodology, M.-C.K.; validation, M.-C.K.; writing--original draft, J.K.; writing--review and editing, M.-C.K. All authors have read and agreed to the published version of the manuscript.  
This research received no external funding.  
Not applicable.  
The original contributions presented in this study are included in the article. Further inquiries can be directed to the corresponding author.  
The authors declare no conflicts of interest.  
The following abbreviations are used in this manuscript:  
NDM Named data networking  
LMP Longest matching prefix  
FIB Forward Information Base  
NPT Name prefix tree  
DEB Distance-encoded Bloom filter  
BS Binary search  
FPP False positive probability  
FPR False positive rate  
URL Uniform Resource Locator