# Route Prefix Caching Using Bloom Filters in Named Data Networking
## 4 Evaluation
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{
\begin{tabular}{c} **Cache Size** \\ **(kB)** \\ \end{tabular} } & \multicolumn{5}{c}{\(\boldsymbol{\alpha}\)} \\ \cline{2-7}  & **0.6** & **0.7** & **0.8** & **0.9** & **1.0** & **1.1** \\ \hline
20 & 0.20705 & 0.28115 & 0.37371 & 0.47811 & 0.58608 & 0.68681 \\
40 & 0.32729 & 0.40353 & 0.49149 & 0.58517 & 0.67663 & 0.75890 \\
80 & 0.50530 & 0.56871 & 0.63739 & 0.70672 & 0.77201 & 0.82941 \\
160 & 0.76262 & 0.78908 & 0.81696 & 0.84517 & 0.87268 & 0.89801 \\
320 & 0.87198 & 0.87757 & 0.88535 & 0.89524 & 0.90708 & 0.92020 \\
640 & 0.87198 & 0.87757 & 0.88535 & 0.89524 & 0.90708 & 0.92020 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Cache hit ratio in the traces generated using \(\alpha\). Figure 8: Frequency of prefixes according to their degrees in log scale. A cache miss occurs when there is no matching prefix in the cache, or when the matching prefix's Bloom filter asserts a positive. The positive assertion of a Bloom filter implies that there is possibly a longer matching prefix in the FIB other than the cache. However, the Bloom filter may misleadingly assert a positive. The probability of the false positive is affected by filter size \(m\), the number of hash functions \(k\), and the number of elements \(n\) to be contained. It is calculated as follows [26]:  
\[P_{f}=\left(1-\left(1-\frac{1}{m}\right)^{kn}\right)^{k}. \tag{2}\]  
In our scheme, the number of elements \(n\) corresponds to the degree of a prefix. Hence, it is close to 1 (94%) as previously discussed, and the mean value of it is 1.814. When the filter size \(m\) is either 4 or 8, and the number of hash functions \(k\) is 1, 2, or 3, the probability of the false positive is as summarized in Table 3. In general, the false positive ratio decreases as the filter size \(m\) increases. However, the false positive ratio does not always decrease as \(k\) increases. For instance, the false positive ratio increases as \(k\) increases for \(n\geq 2\) and \(m=4\). Table 4 shows the cache hit ratio over the parameters of the Bloom filters, \(m\) and \(k\). If \(m\) is 4, the cache hit ratio is rather lower on \(k=2\) than \(k=1\). For \(m=8\), the cache hit ratio increases as \(k\) grows. However, the gain from a Bloom filter with \(k=3\) is insubstantial when compared to a Bloom with \(k=2\) \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{\(m\)} & \multirow{2}{*}{\(k\)} & \multicolumn{5}{c}{\(n\)} \\ \cline{3-7}  & & **1** & **2** & **3** & **4** & **5** \\ \hline
4 & 1 & 0.25000 & 0.43750 & 0.57813 & 0.68359 & 0.76270 \\
4 & 2 & 0.19141 & 0.46730 & 0.67572 & 0.80980 & 0.89054 \\
8 & 1 & 0.12500 & 0.23438 & 0.33008 & 0.41382 & 0.48709 \\
8 & 2 & 0.05493 & 0.17125 & 0.30383 & 0.43085 & 0.54306 \\
8 & 3 & 0.03596 & 0.16747 & 0.34203 & 0.50928 & 0.64736 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: False positive ratio for Bloom filters with size \(m\), the number of hash functions \(k\), and the degree of a prefix \(n\). Figure 9: Comparison of caching schemes for cache hit ratio in the traces with (**a**) \(\alpha=0.7\), and (**b**) \(\alpha=1.0\). The matching type in FIB is classified into four categories, as described in Section 3.2. In Type 1, the matching prefix is the same as the content name. If the matching prefix is a leaf prefix, then it is of Type 3. If the matching prefix is a non-leaf prefix but its Bloom filter asserts a positive, it is of Type 4. The matching prefix, which is a non-leaf prefix, is of Type 2 if its Bloom filter asserts a negative. Figure 9(a) shows the distribution of each matching type in the traces with \(\alpha\) ranging from 0.6 to 1.1. Type 3 is the dominating matching type in all the traces. Type 2 and Type 4 occupy a small portion, and the packets of Type 1 are very few. Figure 9(b) shows the cache hit count in each type. The cache hit count increases as the cache size increases, especially in Type 3, because the packets of Type 3 are substantial in the trace.