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

research-article

Authors: Arish Sateesan, Jo Vliegen, Joan Daemen, Nele Mentens

Published: 01 September 2022 Publication History

Metrics

Total Citations4Total Downloads0

Last 12 Months0

Last 6 weeks0

New Citation Alert added!

This alert has been successfully added and will be sent to:

You will be notified whenever a record that you have chosen has been cited.

To manage your alert preferences, click on the button below.

Manage my Alerts

New Citation Alert!

Please log in to your account

    • View Options
    • References
    • Media
    • Tables
    • Share

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.

References

[1]

Varghese G., Network algorithmics: An interdisciplinary approach to designing fast networked devices, 2004.

[2]

Bloom B.H., Space/time trade-offs in hash coding with allowable errors, Commun. ACM 13 (7) (1970) 422–426.

Digital Library

[3]

Dharmapurikar S., Krishnamurthy P., Sproull T.S., Lockwood J.W., Deep packet inspection using parallel bloom filters, IEEE Micro 24 (1) (2004) 52–61.

Digital Library

[4]

S. Dharmapurikar, M. Attig, J. Lockwood, Design and Implementation of a String Matching System for Network Intrusion Detection using FPGA-based Bloom Filters, in: 12th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, FCCM ’04, 2004.

[5]

Broder A.Z., Mitzenmacher M., Network applications of bloom filters: A survey, Internet Math. (2004).

[6]

Luo L., Guo D., Ma RichardT.B., Rottenstreich O., Luo X., Optimizing bloom filter: Challenges, solutions, and comparisons, 2018, arXiv:1804.04777.

[7]

Estan C., Varghese G., New directions in traffic measurement and accounting: Focusing on the elephants, ignoring the mice, ACM Trans. Comput. Syst. (2003).

[8]

A. Kumar, J. Xu, J. Wang, O. Spatschek, L. Li, Space-code Bloom filter for efficient per-flow traffic measurement, in: Proceedings of the 3rd ACM SIGCOMM Conference on Internet Measurement, 2003, pp. 167–172.

[9]

H. Wu, H.C. Hsiao, Y.C. Hu, Efficient large flow detection over arbitrary windows: An algorithm exact outside an ambiguity region, in: Proceedings of the ACM SIGCOMM Internet Measurement Conference, IMC, 2014, pp. 209–222.

[10]

Stanley Simon, FPGAS & ASICs for telecom, 2015, Heavy Reading, http://www.heavyreading.com/details.asp?sku_id=3418&skuitem_itemid=1657.

[11]

Menezes A.J., van Oorschot P.C., Vanstone S.A., Handbook of Applied Cryptography, CRC Press, 2001.

[12]

Daemen J., Hoffert S., Assche G.Van, Keer R.Van, The design of xoodoo and xoofff, IACR Trans. Symmetric Cryptol. (2018) 1–38.

[13]

Qiao Y., Li T., Chen S., Fast bloom filters and their generalization, IEEE TPDS 25 (1) (2014) 93–103.

[14]

Fowler G., Noll L.C., Vo K.-P., The FNV non-cryptographic hash algorithm, 2012, https://tools.ietf.org/html/draft-eastlake-fnv-03.

[15]

A. Sateesan, J. Vliegen, J. Daemen, N. Mentens, Novel Bloom filter algorithms and architectures for ultra-high-speed network security applications, in: 2020 23rd Euromicro Conference on Digital System Design, DSD, 2020, pp. 262–269.

[17]

Reviriego P., Christensen K., Maestro J.A., A comment on fast bloom filters and their generalization, IEEE Trans. Parallel Distrib. Syst. 27 (1) (2016) 303–304.

[18]

Estébanez C., Sáez Y., Recio G., Isasi P., Performance of the most common non-cryptographic hash functions, Softw. - Pract. Exp. 44 (2014).

[19]

J. Lu, T. Yang, Y. Wang, H. Dai, L. Jin, H. Song, B. Liu, One-hashing Bloom filter, in: Proc. IEEE/ACM IWQoS, 2015.

[20]

Kirsch A., Mitzenmacher M., Less hashing, same performance: Building a better bloom filter, Random Struct. Algorithms 33 (2) (2006) 187–218.

[21]

J. Lu, Y. Wan, Y. Li, C. Zhang, H. Dai, Y. Wang, G. Zhang, B. Liu, Ultra-fast Bloom filters using SIMD techniques, in: Proc. IEEE/ACM IWQoS, 2017.

[22]

K. Huang, et al., A Multi-partitioning Approach to Building Fast and Accurate Counting Bloom Filters, in: IEEE 27th International Symposium on Parallel and Distributed Processing, 2013, pp. 1159–1170.

[23]

Mitzenmacher M., Reviriego P., Pontarelli S., OMASS: One memory access set separation, IEEE Trans. Knowl. Data Eng. 28 (7) (2016) 1940–1943.

[24]

T. Wada, N. Matsumura, K. Nakano, Y. Ito, Efficient Byte Stream Pattern Test using Bloom Filter with Rolling Hash Functions on the FPGA, in: 2018 Sixth International Symposium on Computing and Networking, 2018, pp. 66–75.

[25]

I. Kaya, T. Kocak, A low power lookup technique for multi-hashing network applications, in: IEEE Computer Society Annual Symposium on Emerging VLSI Technologies and Architectures, 2006.

[26]

M.J. Lyons, D. Brooks, The design of a Bloom filter hardware accelerator for ultra low power systems, in: Proceedings of the 2009 ACM/IEEE International Symposium on Low Power Electronics and Design, 2009, pp. 371–376.

[27]

J. Harwayne-Gidansky, D. Stefan, I. Dalal, FPGA-based SoC for real-time network intrusion detection using counting Bloom filters, in: IEEE Southeastcon 2009, Atlanta, GA, 2009, pp. 452–458.

[29]

Z. Martinasek, J. Hajny, D. Smekal, L. Malina, D. Matousek, M. Kekely, N. Mentens, 200 Gbps Hardware Accelerated Encryption System for FPGA Network Cards, in: Proceedings of the 2018 Workshop on Attacks and Solutions in Hardware Security, 2018, pp. 11–17.

[30]

Arish Sateesan, Jo Vliegen, Simon Scherrer, Hsu-Chun Hsiao, Adrian Perrig, Nele Mentens, Speed records in network flow measurement on FPGA, in: 2021 31st International Conference on Field-Programmable Logic and Applications, FPL, IEEE, pp. 219–224.

[31]

Claesen Thomas, Sateesan Arish, Vliegen Jo, Mentens Nele, Novel non-cryptographic hash functions for networking and security applications on FPGA, in: 2021 24th Euromicro Conference on Digital System Design, DSD, IEEE, 2021, pp. 347–354.

[32]

Xilinx User Guide, Ternary content addressable memory (TCAM) search IP for SDNet, https://www.xilinx.com/support/documentation/ip_documentation/tcam/pg190-tcam.pdf.

Cited By

View all

  • Hassan MVliegen JPicek SMentens NLi XHandl J(2024)A Systematic Exploration of Evolutionary Computation for the Design of Hardware-oriented Non-cryptographic Hash FunctionsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654009(1255-1263)Online publication date: 14-Jul-2024

    https://dl.acm.org/doi/10.1145/3638529.3654009

  • Zeng ZXiao RLin XLuo TLin J(2023)Double locality sensitive hashing Bloom filter for high-dimensional streaming anomaly detectionInformation Processing and Management: an International Journal10.1016/j.ipm.2023.10330660:3Online publication date: 1-May-2023

    https://dl.acm.org/doi/10.1016/j.ipm.2023.103306

  • Hassan MSateesan AVliegen JPicek SMentens N(2023)Evolving Non-cryptographic Hash Functions Using Genetic Programming forHigh-speed Lookups inNetwork Security ApplicationsApplications of Evolutionary Computation10.1007/978-3-031-30229-9_20(302-318)Online publication date: 12-Apr-2023

    https://dl.acm.org/doi/10.1007/978-3-031-30229-9_20

  • Show More Cited By

Index Terms

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

    1. Hardware

      1. Integrated circuits

        1. Very large scale integration design

          1. Application-specific VLSI designs

      Index terms have been assigned to the content through auto-classification.

      Recommendations

      • Application and Research on Weighted Bloom Filter and Bloom Filter in Web Cache

        WMWA '09: Proceedings of the 2009 Second Pacific-Asia Conference on Web Mining and Web-based Application

        A Bloom filter is a simple space-efficient randomized data structure for representing a set in order to support membership queries. Bloom filters and their generalizations, weighted Bloom filters and compressed Bloom filters have been suggested as a ...

        Read More

      • An Analysis oftheHardware-Friendliness ofAMQ Data Structures forNetwork Security

        Security, Privacy, and Applied Cryptography Engineering

        Abstract

        Field-programmable gate arrays (FPGA) are increasingly used in network security applications for high-throughput measurement solutions and attack detection systems. One class of algorithms that are heavily used for these purposes, are approximate ...

        Read More

      • The Bloom paradox: when not to use a Bloom filter

        In this paper, we uncover the Bloom paradox in Bloom Filters: Sometimes, the Bloom Filter is harmful and should not be queried. We first analyze conditions under which the Bloom paradox occurs in a Bloom Filter and demonstrate that it depends on the a ...

        Read More

      Comments

      Information & Contributors

      Information

      Published In

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

      Microprocessors & Microsystems Volume 93, Issue C

      Sep 2022

      396 pages

      ISSN:0141-9331

      Issue’s Table of Contents

      Elsevier B.V.

      Publisher

      Elsevier Science Publishers B. V.

      Netherlands

      Publication History

      Published: 01 September 2022

      Author Tags

      1. Bloom filter
      2. FPGA
      3. Network security
      4. Approximate membership query
      5. Non-cryptographic hash

      Qualifiers

      • Research-article

      Contributors

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

      Other Metrics

      View Article Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • 4

        Total Citations

        View Citations
      • Total Downloads

      • Downloads (Last 12 months)0
      • Downloads (Last 6 weeks)0

      Reflects downloads up to 28 Nov 2024

      Other Metrics

      View Author Metrics

      Citations

      Cited By

      View all

      • Hassan MVliegen JPicek SMentens NLi XHandl J(2024)A Systematic Exploration of Evolutionary Computation for the Design of Hardware-oriented Non-cryptographic Hash FunctionsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3638529.3654009(1255-1263)Online publication date: 14-Jul-2024

        https://dl.acm.org/doi/10.1145/3638529.3654009

      • Zeng ZXiao RLin XLuo TLin J(2023)Double locality sensitive hashing Bloom filter for high-dimensional streaming anomaly detectionInformation Processing and Management: an International Journal10.1016/j.ipm.2023.10330660:3Online publication date: 1-May-2023

        https://dl.acm.org/doi/10.1016/j.ipm.2023.103306

      • Hassan MSateesan AVliegen JPicek SMentens N(2023)Evolving Non-cryptographic Hash Functions Using Genetic Programming forHigh-speed Lookups inNetwork Security ApplicationsApplications of Evolutionary Computation10.1007/978-3-031-30229-9_20(302-318)Online publication date: 12-Apr-2023

        https://dl.acm.org/doi/10.1007/978-3-031-30229-9_20

      • Sateesan AVliegen JMentens N(2022)An Analysis oftheHardware-Friendliness ofAMQ Data Structures forNetwork SecuritySecurity, Privacy, and Applied Cryptography Engineering10.1007/978-3-031-22829-2_16(287-313)Online publication date: 9-Dec-2022

        https://dl.acm.org/doi/10.1007/978-3-031-22829-2_16

      View Options

      View options

      Login options

      Check if you have access through your login credentials or your institution to get full access on this article.

      Sign in

      Full Access

      Get this Publication

      Media

      Figures

      Other

      Tables

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

      References

      Top Articles
      Latest Posts
      Recommended Articles
      Article information

      Author: Carlyn Walter

      Last Updated:

      Views: 5285

      Rating: 5 / 5 (70 voted)

      Reviews: 93% of readers found this page helpful

      Author information

      Name: Carlyn Walter

      Birthday: 1996-01-03

      Address: Suite 452 40815 Denyse Extensions, Sengermouth, OR 42374

      Phone: +8501809515404

      Job: Manufacturing Technician

      Hobby: Table tennis, Archery, Vacation, Metal detecting, Yo-yoing, Crocheting, Creative writing

      Introduction: My name is Carlyn Walter, I am a lively, glamorous, healthy, clean, powerful, calm, combative person who loves writing and wants to share my knowledge and understanding with you.