# A Novel Prefix Cache with Two-Level Bloom Filters in IP Address Lookup
## 4 A Proposed Caching Scheme: Two-Level Bloom Filter-Based Prefix Caching (BFPC)  
### A Two-Level Bloom Filter-Based Prefix Cache  
For the matching prefix in a cache, the existence of their child prefix which matches a given incoming IP address can be tested with a Bloom filter. However, the Bloom Filter can misleadingly assert a positive, which means the positive is considered as the existence of a child even though there is no matching child. In turn, it raises a cache miss though the matching prefix is the correct result. The probability of false positive is introduced in [25]. For the filter size \(m\), the number of hash functions \(k\), and the number of elements \(n\) in the filter, it can be approximated by  
\[\left(1-\left(1-\frac{1}{m}\right)^{kn}\right)^{k} \tag{1}\]  
The probability increases as \(n\) grows. If the number of children for a matching prefix is large, the probability that the Bloom filter falsely asserts a positive is also high. For example, when we have a 16-bit filter and two hash functions, the false positive probability would be about 0.05 for \(n=2\), but 0.53 for \(n=10\). For the best membership testing, the number of elements to be contained in a filter should be controlled. However, for a given matching prefix, the number of children cannot be changed. We propose a two-level Bloom filter that controls the number of elements to be contained. In the scheme, the first level is a false-positive free filter, and the second level is a filter in which the number of elements is restricted according to the filter size. There is a set of hash functions that make a Bloom filter false-positive free if the number of elements \(n\) is bounded by some value [26,27]. In addition, if the filter size \(m\) is equal to the size of the universe set which is the set of all possible elements, the Bloom filter can be false-positive free by  
Figure 3: Prefix caching using a single Bloom filter with two hash functions. one-to-one correspondence. For example, there are at most eight children at a distance 3, so the 8-bit filter can be false-positive free up to distance 3. In our two-level Bloom filter, the first-level filter, BF\({}_{1}\), provides a membership test up to distance \(d_{1}\), and the second-level filter, BF\({}_{2}\), up to distance \(d_{2}\). BF\({}_{1}\) has a size of \(2^{d_{1}}\) to be false-positive free. However, the value of \(d_{1}\) is restrictive because the filter size grows by the powers of two. In our scheme, the upper bound of \(d_{1}\) is 4, i.e., the size of BF\({}_{1}\) can be up to 16 bits. The value of \(d_{2}\) is fixed to 5, but the size of BF\({}_{2}\) is not 32 bits, therefore BF\({}_{2}\) is not false-positive free. The size of BF\({}_{2}\) is determined according to the number of elements to be contained so that the false-positive ratio is low. The total filter size is fixed, so the size of BF\({}_{1}\) is obtained by subtracting the size of BF\({}_{2}\) from the total size. Note that the scheme supports a membership test up to the distance 5, but we just use a total filter size of 16 bits. The BF\({}_{1}\) provides a membership test without a false positive up to a distance \(d_{1}\), whereas the BF\({}_{2}\) can do it for the limited number of elements to the greater distance. Figure 4 illustrates an example of a two-level Bloom filter for a prefix \(p\). In this example, the sizes of BF\({}_{1}\) and BF\({}_{2}\) are 8 bits, i.e., \(d_{1}=3\). In Figure 4a, the prefix \(p\) has four children, \(\{a,\,b,\,c,\,d\}\). The children \(\{c,\,d\}\) are contained in BF\({}_{2}\) because their distance is longer than \(d_{1}\). The size of BF\({}_{2}\) is determined as 8 bits because the number of elements to be contained is less than a constraint (three in this example). The children \(\{a,\,b\}\) are contained in BF\({}_{1}\) because their distances from \(p\) are not longer than \(d_{1}\). In the first level, there are two children \(\{a,\,b\}\), but \(a\) is expanded to the distance \(d_{1}\).