# Vectored-Bloom Filter for IP Address Lookup: Algorithm and Hardware Architectures
## 5 Behavior Simulation
### Performance Comparison with Other Structures  
Table 4 shows the comparison on Bloom filter characteristics of the proposed VBF structure with other structures such as BF-chaining with pre-computation [20] and PBF [6]. For fair comparison, the performances of each algorithm should be compared under the same amount of the on-chip memory required for constructing each Bloom filter. Based on the memory amount of the VBF shown in Table 2, in constructing Bloom filters for the BF-chaining and the PBF, sizing factor \(\alpha\) and the number of hash indexes for each structure are calculated, when the same amount of the memory is used. As sizing factor \(\alpha\) increases, the number of off-chip hash table accesses decreases because the number of the search failures decreases.Tables should be cited in sequential numerical order. Please confirm if it's invalid citation, if no, please revise the order. The VBF has the width of 8 but the number of elements for each output port is \(\frac{N}{8}\) and hence the VBF is basically the same as a standard Bloom filter as in the BF-chaining and the PBF structures. Since all nodes of a binary trie are stored in the Bloom filter of the BF-chaining, the \(k\) of the BF-chaining is smaller than \(k_{v}\). Since the PBF requires up to \(W\) independent Bloom filters [6], where \(W\) is the valid lengths of prefixes, the space efficiency is degraded. \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline \multirow{2}{*}{**Routing Set (N)**} & \multirow{2}{*}{\(\alpha\)} & \multicolumn{4}{c}{**VBF**} & \multicolumn{2}{c}{**HT**} \\ \cline{3-8}  & & \(k_{v}\) & **Depth** & **Width (bits)** & \(M_{b}\) (KBytes) & **Depth** & **Width (bits)** & \(M_{h}\) (KBytes) \\ \hline \multirow{4}{*}{1000} & 1 & 6 & 1024 & 8 & 1 & & \\  & 2 & 11 & 2048 & 8 & 2 & 2048 & 51 & 12.75 \\  & 4 & 22 & 4096 & 8 & 4 & & \\ \hline \multirow{4}{*}{5000} & 1 & 6 & 8192 & 8 & 8 & & \\  & 2 & 11 & 16,384 & 8 & 16 & 16,384 & 54 & 108 \\  & 4 & 22 & 32,768 & 8 & 32 & & \\ \hline \multirow{4}{*}{14,553} & 1 & 6 & 16,384 & 8 & 16 & & \\  & 2 & 11 & 32,768 & 8 & 32 & 32,768 & 55 & 220 \\  & 4 & 22 & 65,536 & 8 & 64 & & \\ \hline \multirow{4}{*}{30,000} & 1 & 6 & 32,768 & 8 & 32 & & \\  & 2 & 11 & 65,536 & 8 & 64 & 65,536 & 56 & 448 \\ \cline{1-1}  & 4 & 22 & 131,072 & 8 & 128 & & \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Memory requirement of proposed structure. \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Routing Set (N)** & \(\alpha\) & \(I\) & \(F\) \\ \hline \multirow{4}{*}{1000} & 1 & 0.122 & 0.444 \\  & 2 & 0.003 & 0.019 \\  & 4 & 0.000 & 0.000 \\ \hline \multirow{4}{*}{5000} & 1 & 0.017 & 0.135 \\  & 2 & 0.000 & 0.001 \\  & 4 & 0.000 & 0.000 \\ \hline \multirow{4}{*}{14,553} & 1 & 0.067 & 0.424 \\  & 2 & 0.002 & 0.013 \\  & 4 & 0.000 & 0.000 \\ \hline \multirow{4}{*}{30,000} & 1 & 0.072 & 0.451 \\  & 2 & 0.003 & 0.016 \\ \cline{1-1}  & 4 & 0.000 & 0.000 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Indeterminable and False port return rate. Table 5 shows the comparison of off-chip memory requirements. The hash table in the BF-chaining stores all of the nodes (\(T\)) in a binary trie, while the PBF and the VBF only store prefixes (\(N\)) in each routing set. Thus, the off-chip memory requirement of the PBF and the VBF is much smaller than that of the BF-chaining. Table 6 shows the comparison of the on-chip search performance in terms of the average number and the worst-case number of Bloom filter accesses, represented by \(A_{b}\) and \(W_{b}\), respectively. Since the Bloom filter querying is not performed for lengths not including any prefix, \(W_{b}\) is the number of valid prefix lengths for each set. Note that the Bloom filter querying of the BF-chaining proceeds from the shortest length, while the querying of the PBF and the VBF proceeds from the longest length.