# A Distance-Encoded Bloom Filter for Fast NDN Name Lookup
## 1 Introduction  
Named data networking (NDN) is a promising future Internet architecture that delivers packets based on content names rather than destination addresses [1, 2, 3, 4]. Traditional IP networks rely on host-to-host communication, which faces challenges with mobility, security vulnerabilities, and redundant data transmissions. The NDN, which delivers packets based on content name, has emerged to address the demands of recent network-enabled technologies such as the Internet of Things (IoT) and mobility [4]. Recent studies have focused on forwarding strategies in IoT and MANET [5, 6]. In NDN, forwarding a packet to the next hop requires a name lookup. For a given content name, the name lookup process aims to find the longest matching prefix (LMP) in the forwarding information base (FIB) [7]. For example, if /net/ndn/codebase/main is given as a content name and there are two matching prefixes, /net/ndn and /net/ndn/codebase, in the FIB, then /net/ndn/codebase is the best matching prefix because it is longest among them. Like IP address lookup, name lookup involves finding the longest matching prefix (LMP) but is more complex and challenging. Unlike IP addresses, which are fixed at 32 bits, content names have variable lengths, and the name space is unbounded. A lot of researchhas been conducted to achieve fast name lookup. One approach to achieving efficient lookups is to use a hash table. However, a key challenge in hash table lookup arises from the fact that the length of the key used for searching cannot be known in advance. The length of the search key should be the length of the LMP, but the LMP is determined as a result of the lookup. In the previous example, the length of the LMP is 3, meaning that taking three components from the given content name as the key would result in a successful hash table lookup. However, since the LMP is not known beforehand, the lookup process must start with the length of the longest possible prefix among all prefixes in the FIB and decrement the length iteratively until a match is found. Alternatively, a binary search by the length can be employed [8]. The hash table contains all the prefixes of the FIB and resides in off-chip memory due to its large size. Since off-chip memory has high latency, minimizing hash table accesses is crucial. A Bloom filter can help reduce these accesses by pre-checking whether the prefix of a specific length is present in the hash table. A Bloom filter is a space-efficient data structure that represents membership using bits [9]. In a Bloom filter, the membership of an element in a set may result in a false positive, but a negative result is always true. Implementing the Bloom filter in on-chip memory can improve name lookup performance by reducing the number of hash table accesses and instead relying on the faster Bloom filter. There has been extensive research on Bloom filter-assisted name lookup schemes [10; 11; 12; 13; 14]. Just as multiple lookups are required in hash tables, multiple queries to the Bloom filter may also be necessary to determine the length corresponding to the LMP. The number of these membership queries can be reduced using a binary search based on length. A positive result from a Bloom filter query indicates that a matching node may exist at the current length or at a longer length, meaning the search should continue in a longer length region. Conversely, a negative result suggests that no match exists at the current length, so the search should proceed in a shorter length region. When the length of a given content name is \(n\), the number of Bloom filter accesses in a binary search typically follows \(O\) (\(\log_{2}n\)). To further reduce both Bloom filter and hash table accesses, we propose encoding additional information in the Bloom filter, along with membership, such as the distance to the nearest (or farthest) matching prefix from the current length. The set of name prefixes in the FIB can be represented as a trie.