# Scalable Name Lookup for NDN Using Hierarchical Hashing and Patricia Trie
## 4 Proposed Name Lookup Scheme
### Construction of Patricia Trie  
Since a key is a character string, a Patricia trie should be constructed for characters. However, a Patricia trie node has only two branches, so a character string is represented by a binary character  
Figure 5: The structure of the hash table and two types of hashing schemes: (**a**) hash table format, (**b**) separate chaining, and (**c**) Patricia trie-based.  
code. In a Patricia trie, all keys are placed in leaves. However, a key can be a prefix of another key, and that key has to be placed in an internal node. To resolve this issue, we appended a terminating character '\(\backslash 0\)' to every key. Since no key had '\(\backslash 0\)' in the middle of the string, there was no proper prefix of another key. Figure 6 shows an example of a Patricia trie for a set of keys, {a, ab, ac, bb, bn}. All keys were placed in leaves even though \"a\" was a prefix of \"ab.\" The number inside a Patricia node indicates a bit position to be inspected. The most significant bit position for distinguishing these keys was 6, as shown in Figure 6a. Keys \"a\", \"ab\", and \"ac\" had 0 in the 6 th bit, while keys \"bb\" and \"bn\" had 0. Thus, the root node of the Patricia trie in Figure 6b had a value of 6. Additionally, the left subtrie of the root node had the keys \"a\", \"ab\", and \"ac\", while the right subtrie had \"bb\" and \"bn.\" Since a component is a variable-length string, it could not be stored in a fixed-size leaf node. The key string was stored in an auxiliary structure, as shown in Figure 6b. Key string comparison occurred once only when it reaches a leaf node.  
Figure 7 shows the structures of a Patricia node and its auxiliary information. A Patricia node consists of four fields: _bitpos_, _aux_, _child[0]_, and _child[1]_. The first field _bitpos_ represents bit position to be checked in order to determine which one to be searched--the left or the right trie. If the size of the _bitpos_ field is \(n\) byte, the component consisting of up to \(2^{8n}/8\) characters can be handled. Even though _bitpos_ is 2 bytes long, it is possible to deal with any component with up to 8192 characters, which is practically sufficient length of a component string. The second field _aux_ is pointer to auxiliary information. A leaf node and its ancestors share this auxiliary information. The remaining fields _child[0]_ and _child[1]_ represent the left and the right child, respectively.  
Auxiliary information has three fields: _key_, _face_, and _next_, as shown in Figure 7. Since the store for a key is dynamically allocated and pointed to by _key_, and there is no restriction on the length of a key string. _face_ represents an output face number that a given packet is forwarded to. Whenever a key string is matched at leaf node, the face number _face_ is reserved as a candidate for the matching result. At each level the candidate face number is updated, and lookup continues to perform at next component level that is directed by pointer _next_.  
Figure 6: An example of key strings and its Patricia trie: (**a**) five key strings and their bit representations and (**b**) the corresponding Patricia trie to (**a**).  
Figure 7: Patricia node and auxiliary information.