# Route Prefix Caching Using Bloom Filters in Named Data Networking
## 3 Route Prefix Caching
### Prefix Caching Using Bloom Filters  
In our route prefix cache, non-leaf prefixes are allowed to be cached without requiring their descendants to be cached. For that purpose, we provide a Bloom filter for each non-leaf prefix. The Bloom filter is a space-efficient data structure to test the membership of a given element [20]. In our scheme, the filter is used to test, with a given name, whether there exists a longer matching prefix in the FIB, other than the current matching prefix in the cache. The Bloom filter of a non-leaf prefix is a bit-vector of \(m\) bits. We use 8 bits for the bit-vector in this explanation. For each descendant of a  
Figure 3: An example of FIB and two naïve caching approaches. non-leaf prefix, the \(i\)-th bit is set whenever the position \(i\) is indicated by a hash value for a descendant. \(k\) different hash functions are used for that purpose. Figure 4 illustrates how the Bloom filter is constructed and exploited. The non-leaf prefix \(p\) has three descendants, \(q\), \(s\) and \(t\), each of which contributes to set some bit in the Bloom filter. In Figure 3, BF\({}_{\text{P}}\) denotes the Bloom filter of the prefix \(p\). For \(p\)'s descendant prefix /ride/bike/ha (=\(q\)), the first component right after /ride (=\(p\)), is \"bike\"; thus, the hash values for \"bike\" are computed to obtain set positions in BF\({}_{\text{P}}\). Note that two hash functions, \(h_{1}\) and \(h_{2}\), are used for that purpose. The hash values are 1 and 4; hence, the first and fourth bits are set to 1 in BF\({}_{\text{P}}\). Similarly, the descendants, \(s\) and \(t\) also contribute to set the Bloom filter of \(p\). Both descendants have the first common component right after \(p\), which is \"wagon\". The hash values of \"wagon\" are 4 and 7; hence, the fourth and seventh bits are set in BF\({}_{\text{P}}\). Leaf prefixes also have Bloom filters, but they are always 0 because the leaf prefix does not have any descendants. Now, suppose that we are trying to look up a content name,/ride/bike/ha/ty, and there is \(p\) (=/ride) in the cache, but not \(q\) (=/ride/bike/ha) in the cache. If the content name was looked up in the FIB, both prefixes would be matched, and the longest matching result would be \(q\). However, only \(p\) is matched in the cache. BF\({}_{\text{P}}\) is now queried to check whether there is a descendant of \(p\) which is possibly matched with the content name. The first component of the content name right after \(p\) is \"bike\" and the bit positions of BF\({}_{\text{P}}\) indicated by \(h_{1}\) (\"bike\") and \(h_{2}\) (\"bike\") are 1 and 4, respectively. Since both bits are set to 1, which indicates there possibly exists another longer matching prefix, the cache regards \(p\) as not the longest matching result by treating it as a cache miss. Conversely, if one of the two bits was 0, there could not be any longer matching prefix. In that case, \(p\) is the longest matching result and a cache hit occurs. While all leaf prefixes are cacheable, some non-leaf prefixes are not cacheable. To segregate non-cacheable prefixes, Bloom filters and the information of the prefix length are used. Given a content name \(c\), its longest matching prefix \(p\) in the FIB is classified into four types according to \(p\)'s Bloom filter and length. Figure 5 shows the four categories of the matching prefixes in the FIB. All the prefixes corresponding to Type 1, 2, and 3 are cacheable, while those corresponding to Type 4 are non-cacheable. If the matching prefix \(p\) has a Bloom filter for which bits are all set to 0s, it is clearly a leaf prefix and considered to be of Type 3. Now, let us consider the case where \(p\) is a non-leaf prefix. Let \(p<c\) denote that the length of \(c\) is longer than that of \(p\). Furthermore, BF\({}_{\text{P}}(x)\) represents whether the bits indicated by \(k\) hash values are all 1s or not, where \(x\) is the next component after \(p\). If BF\({}_{\text{P}}(x)\) asserts a negative, this implies that some of the bits may be 0.