# 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)
### Construction of a Two-Level Bloom Filter  
Although the total size of a two-level Bloom filter is fixed at 16 bits, each filter size can be adjusted. Each filter size is determined as the following rule. First, BF\({}_{2}\) can exist only if there exists some child at a distance greater than or equal to 5. Second, the number of elements contained in the BF\({}_{2}\) is restricted to a constraint. The constraint depends on the size of the BF\({}_{2}\). Third, the size of the BF\({}_{2}\) can be increased as long as the corresponding constraint is satisfied. Fourth, if the BF\({}_{2}\) cannot satisfy any constraint, then only the BF\({}_{1}\) is used.  
Figure 7 depicts the algorithm to determine the size of each filter. In the algorithm, several notations are used as follows:  
* \(n(d)\) denotes the number of children at a distance \(\leq\)\(d\).
* \(\delta(d,x)\) denotes \(n(d)\)--\(n(d\)-\(x)\).
* \(m_{1}\) denotes BF\({}_{1}\) size (in the number of bits).
* \(m_{2}\) denotes BF\({}_{2}\) size (in the number of bits).
* \(m\) denotes the total filter size (\(=m_{1}+m_{2}=16\)).
* \(d_{1}\) denotes the distance at which BF\({}_{1}\) covers all the expanded children.
* \(d_{2}\) denotes the distance at which BF\({}_{2}\) covers all the expanded children except BF\({}_{1}\) covers.
* \(I_{1}\) denotes the initial value of \(d_{1}\) (\(=\log_{2}\)\(m=4\)).
* \(I_{2}\) denotes the initial value of \(d_{2}\) (\(=5\)).
* \(c_{x}\) denotes the constraint on a given \(x\).  
In Figure 7, \(x\) represents the gap distance between the BF\({}_{1}\) and the BF\({}_{2}\). \(c_{x}\) represents the constraint for a given \(x\). The BF\({}_{1}\) size \(m_{1}\) and the BF\({}_{2}\) size \(m_{2}\) are determined according to whether the constraint \(c_{x}\) is satisfied. The maximal set size for the BF\({}_{2}\), i.e., the number of elements in the BF\({}_{2}\) should be constrained by \(c_{x}\). The BF\({}_{2}\) is used only if there is at least one element at a distance \(d_{2}\) and the number  
Figure 7: The algorithm for determining the size of each Bloom filter.  
of contained elements is less than or equal to \(c_{x}\). The BF\({}_{2}\) size depends on the satisfied \(c_{x}\), as shown in the table of Figure 7. For example, if \(x=1\) and the number of elements contained in the BF\({}_{2}\) is less than or equal to \(c_{1}\) (\(=3\)), then \(d_{1}\) is 2 and the BF\({}_{2}\) size \(m_{2}\) is 12 (\(=16-2^{d_{1}}\)). Note that if \(x=1\) and the constraint was not satisfied (\(>\)\(c_{1}\)), then BF\({}_{1}\) would be only used without BF\({}_{2}\). The constraint table is designed so that the BF\({}_{2}\) size \(m_{2}\) increases as \(c_{x}\) grows.  
Figure 8 shows examples of various filter sizes, \(m_{1}\) and \(m_{2}\), which are determined according to the positions of children and the satisfied constraint \(c_{x}\). Figure 8a-d shows the cases of \(x=0\), 1, 2, or 3. Figure 8e,f shows the cases that the BF\({}_{2}\) is not used. In Figure 8a, since \(x\) is 0 and the BF\({}_{2}\) tries to contain two elements (prefixes \(d\) and \(e\)), the number of which is less than or equal to \(c_{0}\), \(m_{1}\) and \(m_{2}\) are determined as 8 bits, respectively. On the other hand, the BF\({}_{2}\) can accommodate more elements (prefixes \(c\), \(d\), and \(e\)) in Figure 8b because \(x\) is 1 and the number of elements in the BF\({}_{2}\) is less than or equal to \(c_{1}\). In this case, \(m_{2}\) is determined as 12 bits. Note that the number of elements which is contained in the BF\({}_{2}\) is the sum of twice the number of prefixes at a distance 4 and the number of prefixes at distance 5. In this case, all prefixes are at distance 5. In another example of Figure 8d, four prefixes are contained in the BF2, but the total number of contained elements is 5 because the prefix \(d\) is expanded to two elements.