# A Distance-Encoded Bloom Filter for Fast NDN Name Lookup
## 2 Related Works and Background  
### Related Works  
Most NDN name lookup schemes can be classified into trie-based [15; 16; 17], hash table-based [8; 18; 19; 20], and Bloom filter-based [10; 11; 12; 13; 14] approaches, among others [21; 22; 23; 24; 25; 14]. In the trie-based approach, name prefixes are stored in a hierarchical tree structure, called a trie, where each node represents a name component. In the name prefix tree (NPT), the algorithm traverses from the root to the leaves to find the longest matching name prefix. However, it suffers from low performance due to the large number of sequential memory accesses, which depend on the length of each input name. To improve throughput, [PERSON] et al. proposed parallel name lookup (PNL) [15]. The PNL processes multiple input names concurrently by dividing the NPT structure into several groups, which are mapped onto parallel modules. Additionally, they introduced name component encoding (NCE) to reduce memory usage, utilizing two types of tries: the component character trie (CCT) and the encoded name prefix trie (ENPT) [16]. The NPT contains many non-prefix internal nodes, which are referred to as empty nodes. [PERSON] et al. observed that these empty nodes not only waste memory space but also increase the number of memory accesses required to find the longest matching prefix [17]. To address this issue, they proposed Priority-NPT, which stores longer prefixes in empty nodes. This approach not only reduces memory usage but also enables finding the longest matching prefix with fewer memory accesses. In hash table-based lookup, all name prefixes are stored in the hash table. A hash table search for a given key can be completed in a single access if there are no collisions. However, since the key length is unknown in advance, multiple attempts are required to find the longest matching prefix. [PERSON] et al. proposed a greedy strategy that determines the next prefix length to search in the hash table based on the popularity distribution of leaf prefixes [20]. This approach is compared to CCNx, which performs a linear search from the longest prefix downward. In the case of hash collisions, searching requires traversing the chain within the corresponding bucket and performing key comparisons, which increases lookup time. To mitigate this, [PERSON] et al. proposed storing a Bloom filter in each bucket to maintain membership information, indicating whether the key exists in the chain. This allows for fast lookups without requiring a chain walk [18]. Additionally, they replace a name string with a 64-bit hash value in each bucket, significantly reducing comparison time for long name strings. Similarly, [PERSON] et al. proposed using fingerprints to reduce comparison time in both hash tables and Patricia trie lookups [19]. In another study, they introduced a binary search by length to optimize hash table-based lookup [8]. Most Bloom filter-based approaches are used in combination with or as an auxiliary component of other lookup techniques. Several studies have explored the use of on-chip Bloom filters to pre-check the presence of a prefix before performing a hash table lookup in off-chip memory [10; 11; 12]. [PERSON] et al. proposed a method that progressively increases the prefix length and iteratively accesses the on-chip Bloom filter to determine the length of the longest matching prefix [10]. This approach reduces the number of off-chip hash table accesses. [PERSON] et al. introduced an optimization that applies a binary search by prefix length to minimize the number of Bloom filter accesses [11]. In another study, [PERSON] et al. proposed a dual-load Bloom filter, which contains two types of information within a single cell to assist hash table lookups [12]. One piece of information is membership, similar to a conventional Bloom filter, while the other represents a skip value in a path-compressed trie, indicating the length of a compressed path. [PERSON] et al.