A Fast and Accurate Hardware String Matching Module with Bloom Filters

Date

2017-02-01

Author

Zengin, Salih
Schmidt, Şenan Ece

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

242
views

0
downloads

Many fields of computing such as Deep Packet Inspection (DPI) employ string matching modules (SMM) that search for a given set of positive strings in their input. An SMM is expected to produce correct outcomes while scanning the input data at high rates. Furthermore the string sets that are searched for are usually large and their sizes increase steadily. Bloom Filters (BFs) are hashing data structures which are fast but their false positive results require further processing. That is, their speed can be exploited for Standard Bloom Filter SMMs (SBFs) as long as the positive probability is low. Multiple BFs in parallel can further increase the throughput. In this paper, we propose the Double Bloom Filter SMM (DBF) which achieves a higher throughput than the SBF and maintains a high throughput even for large positive probabilities. The second Bloom Filter of DBF stores a small enough subset of the positive strings such that its false positive probability is approximately zero. We develop an analytical model of the DBF and show that the throughput advantage of DBF over SBF becomes more prominent if the positive probability and the fraction of matches in the second Bloom Filter increase. Accordingly, we propose a heuristic algorithm that stores the strings that are more frequently matched in the second Bloom Filter according to localities identified in the input. Our numerical results are obtained using realistic values from an FPGA implementation and are validated by SystemC simulations.

Subject Keywords

Signal Processing, Hardware and Architecture, Computational Theory and Mathematics

URI

https://hdl.handle.net/11511/41014

Journal

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS

DOI

https://doi.org/10.1109/tpds.2016.2577033

Collections

Department of Electrical and Electronics Engineering, Article

Suggestions

OpenMETU
Core

A Distributed Fault-Tolerant Topology Control Algorithm for Heterogeneous Wireless Sensor Networks Bagci, Hakki; KÖRPEOĞLU, İBRAHİM; Yazıcı, Adnan (Institute of Electrical and Electronics Engineers (IEEE), 2015-04-01) This paper introduces a distributed fault-tolerant topology control algorithm, called the Disjoint Path Vector (DPV), for heterogeneous wireless sensor networks composed of a large number of sensor nodes with limited energy and computing capability and several supernodes with unlimited energy resources. The DPV algorithm addresses the k-degree Anycast Topology Control problem where the main objective is to assign each sensor's transmission range such that each has at least k-vertex-disjoint paths to superno...
A high performance Sigma-Delta readout circuitry for mu g resolution microaccelerometers Ocak, Ilker E.; Kepenek, Reha; Külah, Haluk; Akın, Tayfun (Springer Science and Business Media LLC, 2010-08-01) This paper reports a second order electromechanical sigma-delta readout for micro-g resolution accelerometers in addition to other high-sensitivity capacitive microsensors with large base capacitance. The chip implements a switched-capacitor readout front-end and an oversampled sigma-delta modulator, and hence can be used for both open-loop analog readout and closed-loop control and readout with direct digital output. The readout circuit has more than 115 dB dynamic range and can resolve less than 3 aF/root...
Fast, efficient and dynamically optimized data and hardware architectures for string matching Zengin, Salih; Güran, Hasan Cengiz; Schmidt, Şenan Ece; Department of Electrical and Electronics Engineering (2014) Many fields of computing such as network intrusion detection employ string matching modules (SMM) that search for a given set of strings in their input. An SMM is expected to produce correct outcomes while scanning the input data at high rates. Furthermore, the string sets that are searched for are usually large and their sizes increase steadily. In this thesis, motivated by the requirement of designing fast, accurate and efficient SMMs; we propose a number of SMM architectures that employ Bloom Filters to ...
A nested iterative scheme for computation of incompressible flows in long domains Manguoğlu, Murat; Tezduyar, Tayfun E.; Sathe, Sunil (Springer Science and Business Media LLC, 2008-12-01) We present an effective preconditioning technique for solving the nonsymmetric linear systems encountered in computation of incompressible flows in long domains. The application category we focus on is arterial fluid mechanics. These linear systems are solved using a nested iterative scheme with an outer Richardson scheme and an inner iteration that is handled via a Krylov subspace method. Test computations that demonstrate the robustness of our nested scheme are presented.
A tearing-based hybrid parallel sparse linear system solver NAUMOV, Maxim; Manguoğlu, Murat; SAMEH, Ahmed (Elsevier BV, 2010-09-15) We propose a hybrid sparse system solver for handling linear systems using algebraic domain decomposition-based techniques. The solver consists of several stages. The first stage uses a reordering scheme that brings as many of the largest matrix elements as possible closest to the main diagonal. This is followed by partitioning the coefficient matrix into a set of overlapped diagonal blocks that contain most of the largest elements of the coefficient matrix. The only constraint here is to minimize the size ...

Citation Formats

S. Zengin and Ş. E. Schmidt, “A Fast and Accurate Hardware String Matching Module with Bloom Filters,” IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, pp. 305–317, 2017, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/41014.