# 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
Thus, five elements \(\{b,\,a_{0},\,a_{1},\,a_{2},\,a_{3}\}\) are contained in BF\({}_{1}\). For the BF\({}_{1}\), a simple hash function is used, which outputs three consecutive bits after \(p\). As a result, BF\({}_{1}\)[3:7] are set to 1. In the second level, two hash functions are used, which outputs the first and the last three bits after \(p\), respectively. BF\({}_{2}\)[1], BF\({}_{2}\)[5], and BF\({}_{2}\)[6] are set to 1 as the result of the hash functions. Supposing that the size of an IP address is 7 bits, for an incoming IP address \(k=1001110\), \(k\) matches \(p\) if \(p=1^{*}\) is in the cache. Since \(h_{0}(k)=1\) and BF\({}_{1}\)[1] is 0, BF\({}_{1}\) asserts a negative for \(k\). If BF\({}_{1}\) asserted a positive, it would raise a cache miss. In case that the BF\({}_{1}\) asserts a negative, BF\({}_{2}\) should be consulted. Since \(h_{1}(k)=1\) and \(h_{2}(k)=7\), both BF\({}_{2}\)[1] and BF\({}_{2}\)[7] should be checked. BF\({}_{2}\)[7] is not 1, so the result is a negative and it raises a cache hit with the matching prefix \(p\). Figure 5 shows the structure of the two-level Bloom filter-based prefix cache (BFPC). Each prefix is stored in an associated memory, e.g., TCAM, but other information such as \(d_{1}\), a two-level Bloom filter, and a port number is stored in a conventional SRAM. When an IP address matches some prefix, the corresponding Bloom filter is extracted and consulted. If the Bloom filter asserts a negative, it raises a cache hit. Although the prefix matching in the TCAM takes more time than SRAM access, searching is enabled in parallel. The search time depends on the number of entries in the TCAM. In a prefix cache, the number of entries is small enough compared to FIB, so the search time is not very much. The BFPC can also be applied to IPv6 with 128-bit addresses. For IPv6, the TCAM should be extended in width to accommodate 64-bit prefixes, but three fields in SRAM basically remain the same  
Figure 4: An example of a two-level Bloom filter for a prefix \(p\): (**a**) a trie; and (**b**) a two-level Bloom filter. length. The two-level Bloom filter size may change if needed, which depends on the prefix distribution in IPv6 forwarding table. Figure 6 shows two algorithms for our two-level Bloom filter-based prefix cache: cache lookup and how to handle a cache miss. During the lookup process, the BFPC tries to find the longest matching prefix for a given IP address _ip_. There are two types of cache misses: TYPE-1 and TYPE-2. If there is no matching prefix, then it raises a TYPE-1 cache miss. Otherwise, it consults a two-level Bloom filter for a matching prefix \(p\) with _ip_. If it asserts a positive, i.e., there is probably some more specific prefix in the FIB, then it raises a TYPE-2 cache miss. Note that, despite the TYPE-2 cache miss, the matching prefix \(p\) could be the LMP because it was a false positive. If the Bloom filter asserts a negative, it is certainly a cache hit and the matching prefix \(p\) is the LMP. Figure 5: The structure of the two-level Bloom filter-based prefix cache (BFPC). Figure 6: The algorithms for BFPC: (**a**) cache lookup; and (**b**) processing a cache miss. If a cache miss occurs for a given IP address \(ip\), the LMP should be searched for in the FIB. The LMP and its associated Bloom filter would be inserted into the prefix cache. Before the LMP, say \(p\), is inserted into the prefix cache, the Bloom filter for \(p\) should be consulted. If the filter asserts a positive for \(ip\), it implies that a cache hit never occurs for \(ip\) even though \(p\) has been inserted into the cache. In that case, \(p\) should be expanded to a 32-bit address, i.e., \(ip\) itself should be cached.