# A Novel Prefix Cache with Two-Level Bloom Filters in IP Address Lookup
## 5 Evaluation
\begin{table}
\begin{tabular}{c c c c c c c c c c} \hline \hline \multirow{2}{*}{**FIB**} & \multicolumn{3}{c}{**Num of Prefixes**} & \multicolumn{3}{c}{**Avg. Prefix Length**} & \multicolumn{3}{c}{**Avg. Length When Cached**} \\ \cline{2-10}  & **Non-Leaf** & **Leaf** & **Total** & **Non-Leaf** & **Leaf** & **All** & **Non-Leaf** & **Leaf** & **All** \\ \hline Original & 82,070 & 734,876 & 817,583 & 20.333 & 23.027 & 22.754 & - & - & - \\ CPTE & 0 & 988,828 & 988,828 & 0 & 22.817 & 22.817 & - & 22.817 & 22.817 \\ PPTE & 82,707 & 759,206 & 841,913 & 20.333 & 22.974 & 22.715 & 32.000 & 22.974 & 23.861 \\ NPE & 82,707 & 734,876 & 817,583 & 20.333 & 23.027 & 22.754 & 32.000 & 23.027 & 23.934 \\ BFPC & 82,707 & 734,876 & 817,583 & 20.333 & 23.027 & 22.754 & 20.333 & 23.027 & 22.754 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: The characteristics of FIBs used in prefix caching schemes. Figure 9: The cache miss ratio in several prefix caching schemes: (**a**) in trace-1; and (**b**) in trace-2. prefix in an FIB. If BF\({}_{1}\) or BF\({}_{2}\) asserts a positive, then a TYPE-2 cache miss arises. Figure 10 shows the distribution of cache miss reasons. The cache misses mainly arise due to TYPE-1, which accounts for 75.0-96.4% of cache misses in trace-1, and 80.4-97.3% in trace-2. The cache misses due to BF1-positive are the next most common misses, but relatively small. It seems that the relative portion of TYPE-2 increases when the cache size increases. The reason is that the actual total cache misses decreases while the cache size increases, and especially \"unmatched\" misses (TYPE-1) are relatively more reduced. Figure 11 shows the ratio that a Bloom filter asserts a negative. The negative ratio of a Bloom filter can be measured by cache hit counts among prefix matching counts in a cache. Remember that the cache hit arises only when there is a matching prefix in a cache and its Bloom filter asserts a negative. For any cache size, the negative ratio is higher than 0.986, which means, in more than 98.6% cases, the Bloom filter assures the matching prefix is the hit result. In Figure 11, the negative ratio slightly increases as the cache size increases. In BFPC, each Bloom filter size is variable, but the total Bloom filter size is fixed to 16 bits. The size of the first-level filter, \(m_{1}\), can be 0, 2, 4, 8, or 16. Figure 12 shows the first-level filter size over prefix length. There are many more cases in \(m_{1}=16\) bits in which BF\({}_{1}\) is only used. The next most common cases are in \(m_{1}=0\) in which BF\({}_{2}\) is only used. Generally, the number of non-leaf prefixes having a specific BF\({}_{1}\) size grows as the prefix length increases. Figure 11: The negative ratio of a Bloom filter. Figure 10: The distribution of cache misses according to their causes. “Unmatched” means there is no matched prefix in a cache, while “BF1-positive” (or “BF2-positive”) means there is a matched prefix but it results in a cache miss due to BF\({}_{1}\) (or BF\({}_{2}\)) positive: (**a**) in trace-1; and (**b**) in trace-2. Figure 13 shows the number of non-leaf prefixes over the number of elements which are contained in their level filters. Since the BF\({}_{1}\) size is at most 16 bits, the number of elements to be contained is also at most 16 in the figure. In the BF\({}_{1}\), there is no general trend, other than that the number of non-leaf prefixes has a peak at a power of two. On the other hand, the number of non-leaf prefixes sharply decreases, as the number of elements contained in the BF\({}_{2}\) increases. The number of elements contained in the BF\({}_{2}\) is at most 5 since it is restricted to that value. Note that the effectiveness of the BF\({}_{2}\) depends on the number of contained elements, whereas that of the BF\({}_{1}\) is independent of the number of contained elements.