Hardware-oriented optimization of Bloom filter algorithms and architectures for ultra-high-speed lookups in network applications

Abstract

This paper optimizes Bloom filter algorithms and hardware architectures for high-speed implementation on FPGAs. A Bloom filter is a data structure that is used to check whether input search data are present in a table of stored data. Bloom filters are extensively used for monitoring network traffic. Improving the speed of Bloom filters can therefore have a significant impact on the speed of many network applications. The most important components determining the speed of Bloom filters are hash functions. While hash functions in Bloom filters do not require strong cryptographic properties, they do need a minimized computational delay. In this work, we evaluate and compare the performance and resource utilization of different Bloom filter algorithms and architectures as well as non-cryptographic hash functions on an FPGA. We also propose a new non-cryptographic hash function, called Xoodoo-NC, derived from the cryptographic permutation Xoodoo. Xoodoo-NC is a reduced-round, reduced-state version of Xoodoo, inheriting Xoodoo's desired avalanche properties and low logical depth, resulting in an ultra-low-latency non-cryptographic hash function. We evaluate the performance of Bloom filter architectures based on Xoodoo-NC on a Xilinx UltraScale+ FPGA and we compare the performance and resource occupation to existing Bloom filter implementations. We additionally compare our results to memories that use the built-in CAM cores in Xilinx UltraScale+ FPGAs. Our proposed algorithmic and architectural advances lead to Bloom filters that, to the best of our knowledge, outperform all other FPGA-based solutions.