# Scalable Name Lookup for NDN Using Hierarchical Hashing and Patricia Trie
## 5 Experiment
### Experiment Results  
All name prefixes were obtained from a dmoz name set. The original data set was in the form of URLs such as \"[[http://www.google.com/words](http://www.google.com/words)]([http://www.google.com/words](http://www.google.com/words))\", but we converted it into the form of an NDN name like \"/com/google/www/words.\" The number of components in a name ranges from 1 to 8, as shown in Figure 8. The dominant component level was 3, and the number of components of that level was 1,883,555, which was 75.7% of the total. This implied that hierarchical hashing from the first level was more favorable than flat-style hashing starting from the last level.  
The performance of our scheme was evaluated with throughput that was measured in packets per second (pps), as shown in Figure 9. The throughput is inversely proportional to the maximum load factor \(\beta\). As explained in Section 4.2, \(\beta\) is the upper bound of the actual load factor of a hash table. The higher \(\beta\) value allows more keys to be accommodated in a hash table. This implies there can be more chances of hash collision.  
There was a growing tendency for performance as \(\beta\) decreased, but a high memory usage was expected when \(\beta\) was set to low value. Figure 10 shows a trade-off between memory usage and lookup latency. The lookup latency was calculated by dividing the elapsed time by the number of processed packets. The memory usage was drastically decreased till \(\beta\) reached 1.0, whereas it kept stable after that point. Thus, latency and memory usage could compromise at around \(\beta\) = 1.0.  
Figure 8: Distribution of component level in a dmoz name set.  
Figure 9: Throughput according to load factor.  
For \(\beta<1.0\), the size of hash table should be higher than the number of stored keys. For example, if \(\beta=0.5\) and the number of stored keys becomes 5, then the hash table size should be set as higher than or equal to 10. This implies that half of the hash buckets were likely unoccupied. Figure 11 shows that the number of hash buckets gradually approached the number of occupied buckets as \(\beta\) went higher.  
Figure 12 compares the Patricia trie with a linked list in maximum depth. The depth of the Patricia trie was much lower than that of the linked list. The depth of the linked list was approximately proportional to \(\beta\), whereas that of the Patricia trie very slowly increased as \(\beta\) went higher. Since the depth value accounted for lookup time in the worst case, it was expected that a worst-case lookup takes less time in the Patricia trie than a linked list.  
Figure 11: Comparison on the hash table size and the number of occupied buckets.  
Figure 10: The lookup latency and required memory size.  
Figure 13 compares the Patricia trie with the linked list in regards to the average number of node accesses and the memory usage. The lookup time highly depended on the number of memory accesses. Thus, it took more time when the average number of node accesses was higher. It is shown in Figure 13a that the Patricia trie was better than the linked list as \(\beta\) increased. However, there was a trade-off between the number of node accesses and the memory usage. The Patricia trie used more memory than the linked list because the Patricia trie required intermediate nodes, unlike the linked list. The memory usage of both is compared in Figure 13b.