# Route Prefix Caching Using Bloom Filters in Named Data Networking
## 4 Evaluation  
For the experiment, we used the route prefixes that came from a name set _dmoz_[24] because there is currently no real route prefix table for NDN. Since the name set was originated from Internet URLs, some conversions were made for the experiment. For instance, some intermediate nodes which are not prefixes were changed to prefixes randomly. Table 1 shows the FIB table containing 3,644,942 prefixes in total. The FIB table consists of leaf prefixes and non-leaf prefixes, which account for 77.6% and 22.4% of the total, respectively. Figure 8 shows the frequency of prefixes according to their degrees. The degree of a prefix represents the number of the first components appearing just after the prefix. This is related to the false positive ratio of a Bloom filter. All the leaf prefixes no doubt have a degree of 0, and most non-leaf prefixes have a degree of 1, which is 94.0% of the total non-leaf prefixes. The mean value of the degree is 2.023 for non-leaf prefixes; however, if an outlier is excluded, the mean value becomes 1.814. \begin{table}
\begin{tabular}{c c c} \hline \hline
**Leaf Prefixes** & **Non-Leaf Prefixes** & **Total** \\ \hline
2,827,582 & 817,360 & 3,644,942 \\ (77.6\%) & (22.4\%) & (100.0\%) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The number of prefixes in the FIB which was used in the experiment. Six traces were used for our experiment, each of which was generated stochastically using Zipf distribution. Internet traces are known to follow Zipf-like behavior [25]. \[P(r)\sim\frac{1}{r^{\alpha}} \tag{1}\]  
where \(r\) is the rank in the frequency of packets. When the generated traces for \(\alpha=\{0.6,\,0.7,\,0.8,\,0.9,\,1.0,\,1.1\}\) were used, the cache hit ratio in our scheme was as shown in Table 2. As \(\alpha\) increases, the high-ranking packets have a higher frequency of occurrences in a trace. Generally, a high cache hit ratio is achieved with a large cache and in the trace of a high \(\alpha\) value. In cases where the cache size is greater than 160 KB, the cache hit ratio is not affected much by the value of \(\alpha\). Non-leaf prefix caching without any supplementary method causes an incomplete prefix caching problem. A few caching schemes to avoid the problem are compared in Figure 9. Our Bloom filter-based scheme is denoted by \"bfilter\", and the Leaf-Prefix-Caching-Only scheme, which allows only leaf prefixes to be cached, is denoted by \"Ipco\". The No-Prefix-Caching scheme, which caches a content name itself instead of its matching prefix, is denoted by \"npc\". \"Ipco+npc\" denotes a scheme which caches a matching leaf prefix or a content name in cases where the matching prefix is a non-leaf prefix. The Bloom filter-based prefix cache is far superior to the other schemes in the cache hit ratio. \"npc\" no doubt shows the worst cache hit ratio because it does not cache prefixes and, thus, it does not exploit any spatial locality. The cache hit ratio of \"Ipco+npc\" is worse than that of \"Ipco\" up to the cache size of 4096 entries. The content name caching requires more cache entries to utilize a similar level of the locality. Therefore, \"Ipco+npc\" results in more conflict misses than \"Ipco\" in a small cache. However, if the cache is sufficiently large, \"Ipco+npc\" can utilize the space and reduce the cache misses, even in cases where the matching prefix is a non-leaf prefix.