# A Novel Prefix Cache with Two-Level Bloom Filters in IP Address Lookup
## 2 Background
### Related Works  
Several researchers explored the prefix caching schemes to enable fast IP address lookup [13; 14; 16; 17; 18; 19; 20; 21; 22]. [PERSON] proposed three prefix expansion schemes: no prefix expansion (NPE), partial prefix tree expansion (PPTE), and complete prefix tree expansion (CPTE) [13]. In NPE, only leaf prefixes can be cached. Thus, it does not require prefix expansion for the non-leaf prefixes. If a non-leaf prefix is matched in the FIB, the 32-bit IP address is cached instead. In PPTE, a non-leaf prefix is expanded one bit longer only if the expanded prefix is not overlapped with other prefixes. Thus, there may still exist some non-leaf prefixes after the expansion by PPTE. If a non-leaf prefix is matched in the FIB, the IP address is cached as in NPE. In CPTE, every non-leaf prefix is completely expanded so that no expanded prefix is overlapped with its descendants. As a result, all prefixes become leaves after the expansion by CPTE. In CPTE, the degree of each node is either 0 or 2. Both PPTE and CPTE schemes statically expand non-leaf prefixes in the FIB, so those schemes increase the size of the FIB. Moreover, it is quite complicated to update expanded prefixes. [PERSON] and [PERSON] proposed a prefix caching technique called reverse routing cache (RRC) to expand non-leaf prefixes on caching without modifying the original FIB [16]. They presented two ways to handle non-leaf prefixes: RRC with parental restrictions (RRC-PR) and RRC with minimal expansion (RRC-ME). RRC-PR caches only leaf prefixes similar to NPE. RRC-ME expands a non-leaf prefix when it needs to cache the prefix. Thus, the size of the FIB is not increased. In RRC-ME, a non-leaf LMP is expanded on the fly to be cached. However, it requires additional processing time for expansion in proportion to the expansion length. A bitmap-based prefix cache (BMcache) [17] was presented to dynamically expand non-leaf prefixes using a bitmap on a caching process with low overhead in determining the expansion length. Multi-zone caching can split a cache into multiple sections often depending on the length of the matching prefix length for the performance improvement. The short prefix expansion (SPE) was introduced to expand only prefixes shorter than 17, which decreases overhead for prefix expansion [18]. The multi-zone pipelined cache (MPC) was also developed to extend the SPE scheme to the multi-zone caching technique. In MPC, while IP address caching is used for long prefixes, prefix caching is used for short prefixes. [PERSON] et al. developed a technique to find and cache the most popular prefixes based on traffic prediction [19]. When caching the prefix, there is an additional burden of caching all its descendant prefixes to ensure the correct result. [PERSON] et al. introduced an FIB caching method to cache the popular prefixes into a limited size of ternary content addressable memory (TCAM) [20]. To resolve the incomplete caching problem, it caches a leaf prefix or a non-leaf prefix in the form of prefix expansion. The combined FIB caching and aggregation (CFCA) [21] scheme was presented to use TCAM-based cache to store frequently used prefixes. After expanding the non-leaf prefixes, it aggregates FIB prefixes according to the next-hop values. [PERSON] and [PERSON] presented a cached classification method that applies lossy compression to the packet classifier [22]. Many packets are processed according to a  
Figure 2: Example of prefix expansion to resolve the problem in Figure 1. When \(IP_{1}\) arrives, the non-leaf prefix \(p\) is expanded to \(p_{1}\), which is independent of other prefixes. small number of popular prefix rules in a fast lossy classifier, and unclassified packets are processed in a conventional exact classifier. Recently, some route prefix caching schemes [23; 24] have been studied for fast name lookup in named data networking (NDN), which is one of the representative next-generation Internet. These techniques also use the prefix expansion technique to effectively cache non-leaf prefixes without any problem.