# A Distance-Encoded Bloom Filter for Fast NDN Name Lookup
## 2 Related Works and Background
### Bloom Filter-Assisted Name Lookup  
Since the hash table contains a large number of name prefixes and even includes non-prefix intermediate nodes for binary search, it resides in off-chip memory (DRAM), resulting in high access latency. To reduce the number of hash table accesses, Bloom filter-based pre-search approaches have been proposed [10; 11; 12]. A Bloom filter checks whether a specific element is in a set [9]. Such Bloom filters have been widely used to improve longest prefix matching in network applications [29; 30; 31; 32].  
Figure 4: Hash table with marker nodes (each labeled ‘M’ in a red box).  
Figure 3: Hash table and an example of binary search by length.  
Using a Bloom filter, we can efficiently check whether a matching node exists for a specific length. Since a Bloom filter is much smaller than a hash table, the length of the LMP can be identified at the speed of on-chip memory access.  
A Bloom filter is a bit vector that indicates the existence of members by setting bits indexed by multiple hash functions. Figure 5 illustrates an example where the presence of a member is tested using three hash functions (h\({}_{1}\)-h\({}_{3}\)). For /net/ndn/lookup, at least one bit specified by the hash function (h\({}_{2}\)) is not set, indicating the absence of the member. In contrast, for /net/ndn, all bits are set, suggesting the possible presence of the member.  
By performing such pre-checking techniques before searching the hash table, the number of hash table accesses can be reduced. However, since bits may be set by other members, Bloom filters can produce false positives, meaning that a non-existent member may incorrectly appear as present.  
As described in Section 2.3.2 in the context of hash tables, the binary search by length approach can also be applied to Bloom filters for membership testing. The hash table search is conducted only after the final Bloom filter access rather than after every Bloom filter access.  
In Figure 6, BF (\(m\)) means a membership test for a key of length \(m\), meaning a query to check whether a matching node exists at that length. During the binary search process, if the Bloom filter returns a positive result, the search continues for a longer length; otherwise, it proceeds with a shorter length. With each membership test, the search range halves, and the search position shifts to the midpoint of the remaining range. Once the search reaches a leaf of the search tree, a hash table search is initiated using the final length value.  
The number of Bloom filter accesses follows an O (log (\(r\))), where \(r\) is the length of the longest prefix in the FIB. Since a Bloom filter may produce false positives, the hash table search could fail, requiring backtracking.  
A Bloom filter can be constructed by including either all nodes--both prefix nodes and non-prefix nodes--or only marker nodes among the non-prefix nodes. If only marker  
Figure 5: Pre-checking using a Bloom filter membership test.  
Figure 6: Binary search by length with a Bloom filter.  
nodes are included, the number of elements in the Bloom filter is reduced, thereby lowering the false positive rate. However, since the positions of marker nodes are fixed within the given binary search tree, using marker nodes makes it difficult to dynamically adjust the initial search range.  
The hash table can store (1) all nodes, (2) prefix nodes and marker nodes, or (3) only prefix nodes. Storing only prefix nodes reduces the number of entries, which helps decrease hash collisions. However, it also increases search failures, potentially leading to a significantly higher number of hash table accesses.