# A Novel Prefix Cache with Two-Level Bloom Filters in IP Address Lookup
## 6 Conclusions  
IP address lookup is a very crucial function in forwarding packets, and prefix caching is one of the techniques to enhance the lookup performance effectively. In general, a prefix cache can achieve better performance than an IP cache. The prefix cache exploits address-spatial locality as well as temporal locality, whereas the IP cache can exploit only temporal locality. However, if a non-leaf prefix is allowed to be cached, it incurs an incorrect result. The reason for such an incorrect result is that another longer matching prefix may exist in an FIB when a non-leaf prefix in the cache is matched. To resolve the problem, all the descendants should be cached together with the non-leaf prefix, or it should be assured that all the cacheable prefixes are disjoint to each other. The prefix expansion is one of the techniques which can obtain a set of cacheable disjoint prefixes. However, the prefix expansion technique increases the FIB size as well as makes the prefix to be expanded. The expanded prefix represents a more specific prefix and covers a smaller range of addresses. Thus, the exploitable spatial locality is reduced in those schemes.  
Figure 12: The number of non-leaf prefixes with a BF\({}_{1}\) size \(m_{1}\) in log scale.  
Figure 13: The number of non-leaf prefixes according to the number of elements contained in their filters in log scale.  
This paper proposes the Bloom filter-based prefix caching scheme (BFPC). While most of the existing prefix caching techniques are based on prefix expansion, BFPC improves the caching technique so that non-leaf prefixes can be cached without the prefix expansion. A Bloom filter for each prefix plays a role in a membership test whether there exists another longer matching prefix. A prefix is stored in a cache entry together with its Bloom filter. If some prefix is matched in the cache during cache lookup, then its Bloom filter is consulted. The positive assertion of the Bloom filter implies that there is possibly another longer matching prefix, i.e., a cache miss occurs.  
Generally, the Bloom filter size is relatively small compared to the number of all possible containable elements. However, the probability of false positive increases as the number of contained elements grows. Our design goal is to reduce the false positive by using a two-level Bloom filter. The two-level Bloom filter scheme adjusts the size of each level filter to reduce the false positives. The filter size is adjusted according to the number of elements to be contained in the second-level filter. The second-level filter can accommodate a limited number of child prefixes at a long distance to reduce the false positives. On the other hand, the first-level filter can accommodate a maximum number of child prefixes at a short distance.  
The experimental result shows that BFPC achieves a very low cache miss ratio without increasing the number of FIB entries. The cache miss reasons are also observed in the experiment. Most cache misses are due to no matching prefix, and there are not many misses due to the positive assertion of the Bloom filters. In addition, the membership tests of the Bloom filters are observed to be negative assertions in most cases. It implies that, when the original prefixes are cached without expansion in BFPC, they can be effectively hit using the descendant test of BFPC.  
Conceptualization, J.K. ([PERSON]); Formal analysis, J.K. ([PERSON]) and J.K. ([PERSON]); Investigation, M.-C.K. and M.S.S.; Methodology, J.K. ([PERSON]); Validation, M.-C.K. and M.S.S.; Writing--original draft, J.K. ([PERSON]); and Writing--review and editing, J.K. ([PERSON]) and J.K. ([PERSON]). All authors have read and agreed to the published version of the manuscript. This research received no external funding. The authors declare no conflict of interest.