# A Novel Prefix Cache with Two-Level Bloom Filters in IP Address Lookup
## 1 Introduction  
The Internet has been providing more and more various types of services at a high speed for several decades. Accordingly, the Internet router, which is an important component of the Internet, has also been required to provide higher performance. The router determines the next hop for each incoming packet based on its destination IP address. To make this decision, it performs the IP address lookup, which is to search for the best matching prefix in the forwarding information base (FIB). For a given IP address, there can be multiple matching prefixes in the FIB, and the longest matching prefix (LMP) among them should be selected as the best result. However, the process of finding an LMP is very complex and consumes a lot of cycles. Therefore, many researchers have been working on high-performance IP address lookup [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11]. Caching is one of the prominent techniques which can be applied to improve the performance of the IP address lookup. The caching techniques in the IP address lookup can be classified into IP address caching [12] and prefix caching [13]. The former uses only temporal locality to cache the 32-bit IP address and reuses the lookup result when the same address is given. On the other hand, the latter caches a prefix which represents a network address covering a range of IP addresses and reuses the result when one of the addresses in that range is given. In other words, it utilizes not only temporallocality but also address-spatial locality. Thus, the prefix caching can achieve better performance by utilizing locality more effectively than the IP address caching. Unfortunately, the prefix caching can cause a serious problem if non-leaf prefixes are allowed to be cached without changing. If a non-leaf prefix is cached but its longer descendant prefixes are not, it is not guaranteed that the result of a cache hit is the correct LMP because a longer matching prefix may exist in the FIB even though it is not in the cache. We call this problem the _incomplete caching problem_[14]. Prefix expansion [13] is one of the representative ways to resolve the incomplete caching problem. It is to expand a non-leaf prefix to leaf prefixes so that they become independent of other descendant prefixes. The prefix expansion in the original FIB increases the size of the FIB, making it difficult and expensive to implement. Besides, the expanded prefix is more difficult to update than the original prefix. In the case of prefix expansion in the cache, multiple expanded prefixes can be cached for one LMP, and an increase in the number of occupied entries can result in performance degradation due to capacity misses. Moreover, the expanded prefix may be less utilized in the address-spatial locality because the range of addresses it covers is narrower than the original prefix. Our scheme can cache a non-leaf prefix in itself without sacrificing the spatial locality and resolves the incomplete caching problem by using the supplementary information for each prefix to indicate the existence of its child prefixes in the FIB. The scheme uses Bloom filters [15] to represent that information. The Bloom filters have been widely used for checking a membership in the longest prefix matching [9; 10; 11], but not in the prefix caching for fast IP address lookup. In our scheme, they efficiently determine whether there exists a matchable child prefix for the current matching prefix in a cache. The drawback of the Bloom filter is misleadingly indicating there is a member even though it is not true. Moreover, the false positive ratio increases as the number of contained elements grows. In this paper, we propose a two-level Bloom filter-based prefix caching scheme which keeps a low false positive probability by controlling the number of contained elements and adjusting the size of each filter within the total size. The rest of the paper is organized as follows.