# A Novel Prefix Cache with Two-Level Bloom Filters in IP Address Lookup
## 5 Evaluation  
The performance of BFPC was evaluated using a real-world prefix table and two generated traces. The BGP table at 18 August 2020-04:00 was obtained from [28]. For experiments, the BGP table was converted to an FIB which has the same prefixes as the BGP table. Recently, the size of the BGP table rapidly grows by 7-9% per year [29] and has become 817,583 entries. In publicly available packet traces, IP addresses are sanitized for privacy reasons. Such IP addresses will not match the prefixes in the real-world FIB. Thus, we used randomly generated traces that match the real-world prefixes as well as reflect the locality of references. The characteristics of the FIB are shown in Table 1. The FIBs for three comparing schemes are also shown in the table. In CPTE, all non-leaf prefixes are pushed down and expanded until they become  
Figure 8: Examples of various sizes of BF\({}_{1}\) and BF\({}_{2}\): (**a–f**) cases. leaf prefixes. Thus, there are only leaf prefixes and the FIB size is much bigger than the original one (total 988,828 entries). In PPTE, the FIB size is slightly increased. In NPE and BFPC, the table size does not change. The average prefix length of CPTE is greater than any others while the prefix length of NPE is the greatest on average when the prefix is cached. NPE cannot store the non-leaf prefixes in a cache and those should be expanded to 32 bits when they are cached. BFPC can utilize a prefix in a cache without expansion, regardless of whether it is a leaf or not. Thus, the average prefix length of BFPC is the same as the original one and BFPC also has the advantage that its FIB size is the same as the original one. On the other hand, CPTE cannot utilize non-leaf prefixes in the cache even though its average prefix length on a cache is slightly greater than BFPC. In Figure 9, the cache miss ratios of the five schemes are compared using two traces. CPTE shows the lowest miss ratio, but its number of table entries is larger than in any other scheme, as shown in Table 1. In addition, the FIB update overhead can be quite high in CPTE. For instance, a non-leaf prefix can be expanded to a lot of prefixes in CPTE and those expanded prefixes should be removed when the original prefix is removed. BFPC shows the miss ratio close to that of CPTE, with the same number of table entries as the original one. The miss ratio of BFPC is merely 0.003 in trace-1 or 0.027 in trace-2, in a cache with 8192 entries. The miss ratio of PPTE is not very good, even though its table size is bigger than that of BFPC. IPCache scheme does not cache any prefix, instead just caches the incoming 32-bit IP addresses. The poor miss ratio of IPCache results from a lack of exploiting address-spatial locality and the occupancy of many entries by caching individual IP addresses. Unlike prefix expansion-based caching schemes, BFPC caches an original prefix without expansion except that its Bloom filter asserts a positive for a given IP address. The cache miss reasons of BFPC are classified into two categories: TYPE-1 cache miss and TYPE-2 cache miss. The TYPE-1 cache misses are conventional and result from the absence of a matching prefix in the cache. Even though there is a matching prefix in the cache, the cache miss can still arise if a matching child prefix probably exists but is not cached yet. In such cases, BF\({}_{1}\) and BF\({}_{2}\) play a role in testing if there exists some matching child