# Scalable Name Lookup for NDN Using Hierarchical Hashing and Patricia Trie
## 3 Related Works  
Most previously proposed name lookup schemes can be classified into TCAM-based [11], trie-based [12; 13; 14; 15], and hash-based [16; 17; 18; 19; 20; 21] ones. A TCAM is an associative memory that searches all the entries in parallel. Each cell can store a value of * (do not care) as well as 0 or 1, so it is fairly suitable to store and lookup variable-sized prefixes. Therefore, many IP address lookup schemes have utilized a TCAM [22; 23]. However, it is hard for a TCAM to accommodate long prefixes and a large number of prefixes, so it is restrictively used in name lookup. [PERSON] et al. proposed a name-based LPM scheme that uses content-addressable memory (CAM) [11]. After dividing every prefix into several fixed length blocks and one variable length block, it hashes the former fixed blocks and stores them in binary CAMs. The latter variable block is stored into a TCAM. Trie-based name lookup schemes may suffer overhead due to a number of memory accesses. Because a name may be a long string of characters, name lookup may need more memory accesses in a trie than an IP lookup. [PERSON] et al. tried to decrease that by path compression [12]. In [13], [PERSON] et al. proposed port information assist trie (P-trie) to prune subtries based on output interface information. [PERSON] et al. presented a high-speed name lookup scheme by mapping states in a logical trie for an FIB into physically parallel modules [14]. They also presented the name component encoding (NCE) scheme to provide a memory saving code allocation mechanism that employs two types of tries called the component character trie (CCT) and the encoded name prefix trie (ENPT) [15]. Before the name lookup, each component's code in a name can be obtained by the CCT. The ENPT is a prefix trie that uses the encoded components to represent a prefix, and it is used for the longest prefix lookup. The state transition array was developed to implement the CCT and the ENPT for saving the required memory space. Most hash-based name lookup schemes compare the name with candidate prefixes as a section of components for their effectiveness, and some of them utilize Bloom filters for efficiency. [PERSON] et al. proposed a name lookup scheme employing a two-stage Bloom filter called the NameFilter [16]. In the first stage, the length of the probing name prefix is determined by means of Bloom filters. The second stage can find the output interface by searching the merged Bloom filters that are classified by the number of output interfaces. They also proposed a hash-based LPM scheme to reduce the search space by the lookup in the order that was generated by using dynamic programming [17]. [PERSON] et al. proposed a name lookup scheme that employed the binary search of hash tables according to the number of name components based on not the real name components but their fingerprints [18]. [PERSON] et al. presented two name lookup schemes that employed on-chip Bloom filters and off-chip hash tables [19]. Recently, [PERSON] et al. presented an index data structure called the Bloom filter-aided hash table (BFAST) for NDN name lookup [20]. The BFAST can reduce the number of memory accesses by achieving the load balance among hash slots by using a counting Bloom filter. An auxiliary data structure is used to indicate the smallest counter at insertion time. They proposed a dynamic adaptation for lookup and deletion to adjust the load values, and they also proposed an indexing scheme to reduce the memory consumption. Some schemes have dealt with LPM for name lookup by employing both a hash and a trie [24; 25]. [PERSON] et al. presented a hybrid structure by using both fixed-sized counting Bloom filters for upper components and variable-sized tries for lower components to realize efficient NDN lookup [24]. After defining the exact string differentiation problem based on the speculative forwarding, [PERSON] et al. proposed a fingerprint-based Patricia trie and a fingerprint-based hash table for name prefix lookup [25].