# Vectored-Bloom Filter for IP Address Lookup: Algorithm and Hardware Architectures
## 5 Behavior Simulation
### Performance Comparison with Other Structures
Thus, as the size of each Bloom filter (\(M_{b}\)) increases, the average number of Bloom filter accesses (\(A_{b}\)) of the BF-chaining decreases but that of the VBF increases, because the number of _negatives_ increases. The larger number of _negatives_ results in the smaller number of hash table accesses in both structures. In case of the PBF, for the fair comparison with other structures, we assume that all of the BFs in the PBF structure are sequentially queried until the longest prefix is matched as in the VBF. Hence, the \(A_{b}\) is constant regardless of the size of the Bloom filter because Bloom filter querying always stops at the length of the matching longest prefix. In other words, starting from the longest length, the Bloom filter querying always continues until a true positive occurs and hence the average number of Bloom filter querying is not related to the size of the Bloom filter. The \(A_{b}\) of the VBF in 5 k is greater than that in other sets, because the 5 k set has many short length prefixes, such as length 16, as shown in Figure 6. Since the search procedure proceeds from the longest length, if the prefix matching occurs in a short length, the \(A_{b}\) becomes large. \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multirow{2}{*}{**Routing Set (\(N\))**} & \multirow{2}{*}{\(M_{b}\) **(KB)**} & \multicolumn{2}{c}{**BF-Chaining**} & \multicolumn{2}{c}{**PBF**} & \multicolumn{2}{c}{**VBF**} \\ \cline{3-6}  & & \(\alpha\) & \(k\) & \(\alpha\) & \(k\) & \(\alpha\) & \(k_{v}\) \\ \hline \multirow{4}{*}{1000} & 1 & 1 & 1 & 6.30 & 4 & 1 & 6 \\  & 2 & 2 & 1 & 12.60 & 9 & 2 & 11 \\  & 4 & 4 & 3 & 25.20 & 17 & 4 & 22 \\ \hline \multirow{4}{*}{5000} & 8 & 2 & 1 & 10.13 & 7 & 1 & 6 \\  & 16 & 4 & 3 & 20.24 & 14 & 2 & 11 \\  & 32 & 8 & 6 & 40.49 & 28 & 4 & 22 \\ \hline \multirow{4}{*}{14,553} & 16 & 1 & 1 & 5.11 & 4 & 1 & 6 \\  & 32 & 2 & 1 & 10.22 & 7 & 2 & 11 \\  & 64 & 4 & 3 & 20.44 & 14 & 4 & 22 \\ \hline \multirow{4}{*}{30,000} & 32 & 2 & 1 & 5.07 & 4 & 1 & 6 \\  & 64 & 4 & 3 & 10.14 & 7 & 2 & 11 \\ \cline{1-1}  & 128 & 8 & 6 & 20.28 & 14 & 4 & 22 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Comparison on Bloom filter characteristics. \begin{table}
\begin{tabular}{c c c c c} \hline \hline \multirow{2}{*}{**Routing Set (\(N\))**} & \multicolumn{2}{c}{**BF-Chaining**} & \multicolumn{2}{c}{**PBF**} & \multicolumn{1}{c}{**VBF**} \\ \cline{2-5}  & \(T\) & \(M_{b}\) **(KB)** & \(M_{b}\) **(KB)** & \(M_{b}\) **(KB)** \\ \hline
1000 & 7678 & 108 & 13 & 13 \\
5000 & 29,534 & 448 & 108 & 108 \\
14,553 & 76,708 & 1856 & 220 & 220 \\
30,000 & 127,576 & 1856 & 448 & 448 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Comparison of off-chip memory requirement. Table 7 shows the comparison on off-chip search performance in terms of the average number and the worst-case number of hash table accesses, represented by \(A_{h}\) and \(W_{h}\), respectively. The number of off-chip memory accesses is the most important performance criterion in the IP address lookup problem. To improve the IP address lookup performance, the number of off-chip accesses should be minimized. In the BF-chaining and the PBF, even if the size of the Bloom filter (\(M_{b}\)) increases, the off-chip hash table is accessed at least once in order to obtain the matching output port. However, hash table accesses occur infrequently in our proposed VBF architecture, since the Bloom filter stored in an on-chip memory returns the matching output port in every case except the _indeterminable_ cases. Only when the VBF produces an _indeterminable_ result, the hash table is accessed. It is shown that the average number of hash table accesses becomes zero as the size of the Bloom filter (\(M_{b}\)) increases.