# A Novel Prefix Cache with Two-Level Bloom Filters in IP Address Lookup
## 3 Bloom Filter-Based Prefix Caching  
The prefix expansion limits the lookup performance due to the increase in the number of entries caused by expansion as well as the limited exploitation of locality from the expanded more specific prefixes. If it is possible to know whether the current matching prefix in a cache has a matchable child prefix in an FIB, the prefix cache can be utilized more effectively by eliminating the prefix expansion. Our scheme employs a Bloom filter to check the existence of child prefixes for each prefix. A Bloom filter is widely used to check membership and is represented by an \(m\)-bit array for a set \(S\) of \(n\) elements. All bits in the filter are initialized to 0. After some element \(x\) is inserted into the filter, some bits \(h_{i}(x)\), \(1\leq i\leq k\) and \(x\in S\), are set to 1 where \(h_{1}\),..., \(h_{k}\) are \(k\) independent hash functions. Now, the membership of \(y\) is tested by checking whether \(h_{i}(y)\), \(1\leq i\leq k\), are all 1s. If so, \(y\) is probably an element of \(S\) (positive), otherwise \(y\) is clearly not an element of \(S\) (negative). Unfortunately, since hash functions can cause collisions, the filter can induce false positives with some probability. A false positive means that \(y\) is asserted to be an element of the target set, but it is not actually an element. The probability of the false positive must be lowered to increase the performance of the system employing the Bloom filter. In our prefix caching, when an LMP is found in the FIB, the LMP is cached together with the corresponding Bloom filter which represents the existence of its child prefixes. Each element in a Bloom filter is identified by a bit string which represents the path from a prefix to its child. The prefix caching scheme using a single Bloom filter is illustrated in Figure 3. Because the LMP for the first IP address \(IP_{1}=1000000\) is \(p=1^{*}\), the prefix \(p\) is cached with the corresponding Bloom filter BF as shown in the figure. In this example, the higher 5-bit string of the path from the prefix \(p\) to its child is used to represent a member for the BF. The child prefix length may differ according to children. We choose the higher bits to represent each child member, since those can be extracted without knowing the length. If the distance from a prefix to its child prefix is less than 5, then the child prefix is expanded to distance 5. For example, the distance from the prefix \(p=1^{*}\) to its child prefix a \(=10010^{*}\) is 4, the bit strings 00100 and 00101, which are the paths from prefix \(p\) to \(a_{0}\) and \(a_{1}\), respectively, are used as members for the BF. Note that, in our scheme, only the child prefix is expanded in its length to be a member and the original prefix \(p\) is not actually expanded, unlike other prefix expansion schemes. Because the bit string from the prefix \(p=1^{*}\) to the prefix \(b=100110^{*}\) is 5-bit \(00110\), the whole set becomes \(\{00100,\,00101,\,00110\}\), which corresponds to the prefixes \(a_{0}\), \(a_{1}\), and \(b\), respectively. In addition, the Bloom filter in this example uses two hash functions: \(h_{1}(c_{0}c_{1}c_{2}c_{3}c_{4})=c_{0}c_{1}c_{2}\) and \(h_{2}(c_{0}c_{1}c_{2}c_{3}c_{4})=c_{2}c_{3}c_{4}\), where \(c_{i}\) denotes the \(i\)th bit of an element. To construct the BF, \(h_{1}(a_{0})\), \(h_{1}(a_{1})\), \(h_{2}(a_{1})\), \(h_{1}(b)\), and \(h_{2}(b)\) are calculated. For example, \(h_{1}(a_{0})=h_{1}(\mathbf{00100})=001\) and \(h_{2}(a_{0})=h_{2}(\mathbf{00100})=100\). As a result, the 1 st, 4 th, 5 th, and 6 th bits of the BF are set to 1, while the other bits remain 0s. In Figure 3, the Bloom filter BF for the prefix \(p\) is consulted when \(p\) is matched in the cache. Suppose that the destination IP address of the second packet is \(IP_{2}=1001000\). It matches \(p=1^{*}\) in the cache, and our scheme ignores the matching result of the cache and regards it as a cache miss through the BF test result.