# Route Prefix Caching Using Bloom Filters in Named Data Networking
## 5 Conclusions  
In this paper we proposed a novel route prefix caching scheme for NDN. The fundamental idea is to use a Bloom filter to test whether there is a longer matching prefix in the FIB. The route prefix cache can be used to reduce the name lookup latency. In NDN, the name lookup process is required to find the longest matching prefix as the result. Prefix caching is challenging because the matching result from a cache would be incorrect unless all the matching prefixes are already in the cache. In the event that the longest matching prefix is not cached but the shorter one is cached, an incorrect result can be issued by the cache.  
To get around the problem, the content name itself can be simply cached instead of the matching prefix. However, in that scheme, the cache hit occurs only when the given name is exactly the same as the key. Therefore, the cache hit ratio would be much lower than for other prefix caching schemes with the same capacity. Caching only for leaf prefixes is another way to avoid incorrect prefix matching. In that scheme, non-leaf prefixes would never be cached; hence, the caching effect is restrictive. Our design goal is to cache non-leaf prefixes without incurring an incorrect result. A Bloom filter is provided for each prefix to test whether there is a longer matching prefix.  
We devised a Bloom filter-based prefix cache considering two key elements. Firstly, our design does not require much space. Non-leaf prefix caching could be made efficient just by adding a 4-bit or 8-bit Bloom filter onto each prefix. Secondly, miss penalty and hit time are not significantly affected by the Bloom filter. On a cache miss, the Bloom filter is fetched together with the matching prefix from the FIB. The miss penalty for delivering the additional 4-bit or 8-bit filter is not a heavy load. Hashing for the Bloom filter affects the hit time, but it is only one-component hashing and requires little processing time.  
The experimental result shows that the cache hit ratio of the Bloom filter-based prefix cache is superior to others even if it has small filters and few hash functions. The probability of the false positive of a Bloom filter can be analyzed through the filter size, the number of hash functions, and the number of elements. The cache miss counts due to Bloom filter's positive assertion were compared to the experiment result, and the 8-bit filter with two hash functions was considered to be suitable for our prefix caching scheme.  
Figure 11: Observations with regard to the cause of cache miss: (**a**) distribution of cache miss count; (**b**) cache miss count against the Bloom filters with size \(m\) and the number of hash functions \(k\) when the cache size is 2048.  
**Author Contributions:** Conceptualization, J.K. ([PERSON]); formal analysis, J.K. ([PERSON]) and M.S.S.; investigation, M.-C.K. and J.K. ([PERSON]); methodology, J.K. ([PERSON]); validation, M.-C.K. and M.S.S.; writing--original draft, J.K. ([PERSON]); writing--review and editing, J.K. ([PERSON]) and M.S.S. All authors have read and agreed to the published version of the manuscript.  
**Funding:** This research received no external funding.  
**Conflicts of Interest:** The authors declare no conflicts of interest.