The network link speed is growing at an ever-increasing rate, which requires all network functions on routers/switches to keep pace. Bloom filter is a widely-used membership check data structure in networking applications. Correspondingly, it also faces the urgent demand of improving the performance in membership check speed. To this end, this paper proposes a new Bloom filter variant called Ultra-Fast Bloom Filters (UFBF), by leveraging the Single Instruction Multiple Data (SIMD) techniques. We make three improvements for UFBF to accelerate the membership check speed. First, we develop a novel hash computation algorithm which can compute multiple hash functions in parallel with the use of SIMD instructions. Second, we elaborate a Bloom filter's bit-test process from sequential to parallel, enabling more bit-tests per unit time. Third, we improve the cache efficiency of membership check by encoding an element's information to a small block so that it can fit into a cache-line. We further generalize UFBF, called c-UFBF, to make UFBF supporting large number of hash functions. Both theoretical analysis and extensive evaluations show that the UFBF greatly outperforms the state-of-the-art Bloom filter variants on membership check speed.

+More

bloom filters bittest process cache efficiency elements information bittests instruction multiple data simd hash computation algorithm network functions networking membership check data structure ufbf called cufbf bloom filter variants

Jianyuan LuYing WanYang LiChuwen ZhangHuichen DaiYi WangGong ZhangBin Liu,.Ultra-Fast Bloom Filters using SIMD Techniques. 30 (4),953-964.

Jianyuan LuYing WanYang LiChuwen ZhangHuichen DaiYi WangGong ZhangBin Liu,"Ultra-Fast Bloom Filters using SIMD Techniques" 30

Jianyuan LuYing WanYang LiChuwen ZhangHuichen DaiYi WangGong ZhangBin Liu,"Ultra-Fast Bloom Filters using SIMD Techniques"