# A Novel Prefix Cache with Two-Level Bloom Filters in IP Address Lookup
## 2 Background  
### Prefix Caching and Prefix Expansion  
A prefix cache stores the prefixes which are the destination network addresses of the incoming packets. The prefix represents a network address, i.e., a range of IP addresses. Therefore, the prefix caching scheme can effectively exploit the prefix to match several IP addresses. In other words, the prefix caching exploits spatial locality as well as temporal locality. Thus, the prefix caching achieves a higher cache hit ratio than the IP address caching. Although prefix caching is more effective, it causes the incomplete caching problem if non-leaf prefixes can be cached. Figure 1 shows an example of the incomplete caching problem that may induce a wrong lookup result when a non-leaf prefix is cached. In this figure, there are a non-leaf prefix \(p=1^{*}\) and two leaf prefixes \(a=10010^{*}\) and \(b=100110^{*}\). Let us assume that the length of the IP address is 7 bits instead of 32 for simplicity and that two packets arrive in turn. If the destination IP address of the first packet is \(IP_{1}=1000000\), the LMP becomes \(p=1^{*}\). Now, the prefix \(p\) is cached for the first time. Supposing that the address of the second packet is \(IP_{2}=1001000\), the prefix \(p\) is hit in the cache. However, the LMP for \(IP_{2}\) is not \(p=1^{*}\) but \(a=10010^{*}\), so this cache hit yields the incorrect result. If the second IP address  
were \(IP_{3}=1001100\), it could also hit the prefix \(p\) and cause the incomplete caching problem. Now, suppose that the second IP address was \(IP_{4}=1001111\). Then, the hit result \(p\) should be the correct result because the prefix \(p\) is the LMP for \(IP_{4}\). There are three ways to deal with the incomplete caching problem of non-leaf prefixes. The first way is not to cache non-leaf prefixes but to cache only leaf prefixes. In the example in Figure 1, the LMP \(p\) for the first packet should not be cached. This method may limit performance gain through caching. The second way is to cache a non-leaf prefix together with all of its descendant prefixes at the same time. In this example, when prefix \(p\) is cached, its descendant prefixes \(a\) and \(b\) should be also cached. This method significantly reduces the cache efficiency by caching a lot of unnecessary prefixes in advance. The third way is to expand the non-leaf prefix into leaves so that the expanded prefixes do not overlap with other descendant prefixes. This method is called _prefix expansion_. Most of the previous works make use of this prefix expansion technique [13; 14; 16; 17; 18]. Figure 2 illustrates an example of how to resolve the incomplete caching problem using prefix expansion. The prefix may be statically expanded in the FIB for later caching, or dynamically expanded at the time of caching. This figure shows an example to explain the dynamic prefix expansion. In Figure 2, it is depicted that the non-leaf prefix \(p\) is expanded when it is matched as the longest one in the FIB. For the address \(IP_{1}\), \(p\) is the LMP in the FIB and expanded to \(p_{1}\). As the expanded prefix \(p_{1}\) is cached instead of \(p\), it avoids the incomplete caching problem because \(p_{1}\) has no descendent prefixes. Now, the second packet arrives with \(IP_{2}=1001000\), and a cache miss occurs. In this case, the LMP \(a\) for the packet is cached without expansion because the LMP \(a\) is a leaf prefix. If the second IP address were \(IP_{4}=1001111\), a cache miss would still occur because the LMP \(p\) has not been cached and \(IP_{4}\) does not match the currently cached prefix \(p_{1}\). Note that, since the original LMP \(p\) cannot be cached in itself in the prefix expansion-based schemes, the address-spatial locality is not fully exploited. For the IP address \(IP_{4}\), the expanded prefix \(p_{2}\) should be cached even though the LMP of \(IP_{4}\) is the same as that of \(IP_{1}\).