# A Distance-Encoded Bloom Filter for Fast NDN Name Lookup
## 4 Evaluation  
The proposed name lookup scheme was evaluated using FIBs and name trace data constructed as follows. The FIBs were built using URL data provided by dmoz [35]. Each URL in the dataset was converted into a name prefix according to a predefined naming rule. For example, [[http://cs.some.edu/courseA/syllabus](http://cs.some.edu/courseA/syllabus)]([http://cs.some.edu/courseA/syllabus](http://cs.some.edu/courseA/syllabus)) was transformed into /edu/some/cs/courseA/syllabus. The characteristics of the generated FIB data are shown in Table 1. The total number of prefixes is 2.9 million, and when including non-prefix intermediate nodes, the total number of nodes reaches 5.2 million. This dataset was named R0. Additionally, two more datasets, R1 and R2, were generated. In R1 and R2, 10% and 20% of the non-prefix nodes were, respectively, selected and converted into prefix nodes. As a result, the number of prefix nodes increased, but the total number of nodes remained the same across all datasets. The name trace data used as input for name lookup consists of a collection of randomly generated content names, amounting to 10 million entries. To ensure that each generated \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Type of Nodes** & **R0** & **R1** & **R2** \\ \hline Prefixes & 2,900,962 & 3,135,491 & 3,370,019 \\ Leaf prefixes & 2,836,521 & 2,836,521 & 2,836,521 \\ Non-leaf prefixes & 64,441 & 298,970 & 533,498 \\ Intermediate nodes & 2,345,281 & 2,110,752 & 1,876,224 \\ Markers & 1,830,872 & 1,672,280 & 1,507,044 \\ Non-marker nodes & 514,409 & 438,472 & 369,180 \\ Total no. of nodes & 5,246,243 & 5,246,243 & 5,246,243 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Characteristics of FIBs. content name has a matching prefix in the FIB, a prefix was first randomly selected from the FIB, and a suffix was then appended by randomly generating a component. The character strings of the suffix components were not generated uniformly at random; instead, they were produced using a 3 g model trained on the distribution of component strings in the FIBs [36]  
Table 2 compares the characteristics of the six name lookup schemes used in the experiment. DEB is the proposed scheme that utilizes a distance-encoded Bloom filter. BS employs a conventional Bloom filter based on binary search, where all nodes in the trie are stored in both the Bloom filter and the hash table. Other schemes with the 'BS-' prefix are differentiated based on whether they include prefixes and markers in the Bloom filter and the hash table. A key feature, prefix prediction, allows the Bloom filter to indicate whether a prefix exists at the current level. Among all schemes, only DEB supports this feature. Marker-based schemes (BS-m-m and BS-m-p) must use a fixed search tree rather than dynamically adjusting the search range, regardless of the content name length to take advantage of markers. Four hash functions were used for the Bloom filters (\(k=4\)). Additionally, the sizes of the Bloom filter and hash table are 64 Mbits and 32 million entries, respectively. Figure 13 shows the ratio of different node types used in the experiment. At levels 1 and 2, non-prefix intermediate nodes are the most common, whereas leaf prefixes dominate at other levels. In R1 and R2, the proportion of non-leaf prefix nodes increases as 10% and 20% more of these nodes are added, respectively. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Scheme** & **Elems in BF** & **Nodes in Hash Table** & **Fixed Search Tree** & **Prefix Prediction** \\ \hline DEB & All & Prefixes & – & Yes \\ BS & All & All & No & No \\ BS-a-p & All & Prefixes & No & No \\ BS-m-m & Prefixes, markers & Prefixes, markers & Yes & No \\ BS-m-p & Prefixes, markers & Prefixes & Yes & No \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Comparison of name lookup schemes. Figure 13: The ratio of leaf prefix, non-leaf prefix, and non-prefix nodes in different FIBs: (**a**) R0; (**b**) R1; and (**c**) R2.