AES指令集加速的网络协议高效Bloom过滤器实现

176 浏览量更新于2024-08-28 收藏 1.82MB PDF 举报

"这篇研究论文‘使用AES指令集的网络协议的高效Bloom过滤器’主要探讨了在互联网持续增长的背景下，如何优化Bloom过滤器的实施，以适应高速网络流量的需求。作者关注的问题是Bloom过滤器实现的多样性对应用的复杂性和实时协议性能的影响。他们提出了一种新的解决方案，利用AES（高级加密标准）指令集，特别是AES-NI（AES新指令），来提高Bloom过滤器的处理速度和效率。 Bloom过滤器是一种空间效率高的概率数据结构，常用于判断一个元素是否可能存在于一个大型集合中。然而，当处理高带宽流量时，即使是微小的延迟也可能显著影响其性能。为此，作者引入了基于AES的哈希函数来构建Bloom过滤器，这种方法可以确保过滤器的正确性，同时利用AES-NI来加速计算过程。 AES-NI是Intel处理器中的一组硬件加速指令，专为AES加密和解密设计，能够显著提升数据处理速度。在论文中，作者展示了如何巧妙地利用这些指令来优化Bloom过滤器的性能。通过实验，他们证明了所提方案相比其他竞争方法能提供更好的速度性能。此外，论文还强调了这种新型Bloom过滤器易于在网络节点上部署和一致使用的特性，这对于需要快速响应的实时网络协议尤其重要。通过这种方式，他们不仅解决了延迟问题，也简化了在不同环境中应用Bloom过滤器的复杂性。总结来说，这篇研究为网络协议的高效数据处理提供了一个创新的解决方案，通过结合Bloom过滤器和AES-NI指令，实现了在处理大规模数据流时的高速过滤，这对现代网络环境中的流量管理和安全应用有着重要的实际意义。" 关键词: Bloom过滤器, AES指令集, AES-NI, 网络协议, 高效数据处理, 实时性能, 哈希函数

IET Communications

Research Article

Efficient Bloom filter for network protocols

using AES instruction set

ISSN 1751-8628

Received on 26th May 2016

Revised 7th April 2017

Accepted on 17th May 2017

E-First on 25th August 2017

doi: 10.1049/iet-com.2016.0641

www.ietdl.org

Yao Zhang

1,2

, Zhiming Zheng

, Xiao Zhang

Security Technology Department, Inspur Electronic Information Industry Co., Ltd, Beijing 100083, People's Republic of China

LMIB and School of Mathematics and Systems Science, Beihang University, Beijing 100191, People's Republic of China

E-mail: 09621@buaa.edu.cn

Abstract: The Internet continues to flourish, while an increasing number of network applications are found deploying Bloom

filters. However, the heterogeneity of the Bloom filter realisations complicates the utilisation of relevant applications. Moreover,

when applying Bloom filter to traffic that usually has a gigabit capacity, even insignificant delays will accumulate and restrict the

effectiveness of the real-time protocols. In this study, the authors present a Bloom filter construction that can be easily and

consistently adopted at network nodes, with also considerable processing speed. Specifically, the authors show that AES-based

hashes are adequate to create Bloom filters correctly. Then they illustrate how AES new instructions (AES-NI) can be leveraged

to accelerate the Bloom filter realisation. According to the authors' experimental results, the proposed Bloom filter enables the

best speed performance compared to the competing approaches.

1 Introduction

Bloom filter [1] is a space-efficient data structure that can be used

to process queries by answering whether an arbitrary element

belongs to a certain set. Recently, thousands of real-time network

applications and services [2–9] (such as DDoS attack detection and

protection [2–4], multicast routing [6], cache filtering in CDN

networks [7], high-speed flow measurement [8], and data-stream

monitoring [9]) are found taking Bloom filter as a fundamental

component. The above applications make up just a tip of the entire

iceberg. Bloom filter has made attractive contributions to the

functionality of dedicated network protocols.

Yet, building Bloom filters is not always straightforward. The

realisation heterogeneity remains as one big challenge when

deploying various protocols at network nodes. With distinct

underlying hash functions, the actual realisation of a Bloom filter

differentiates. Although premium algorithms like Murmur Hash are

more likely to be selected, typical hash functions such as MD5 [10]

are still widely used [11, 12]. Such inconsistency unavoidably

increases the complexity of the deployment when taking multiple

protocols into account. The other concern is the processing

performance. Facing potentially large numbers of element queries

(summarised in Table 1), slight processing delays will accumulate

and significantly constrain the effectiveness of the relevant

applications. The speed optimisation of a Bloom filter thus

becomes critical, while the simplicity of the data structure itself

barely leaves space for possible acceleration.

As a remedy, this paper presents a fast and lightweight Bloom

filter that can be effectively adopted by end hosts and intermediate

routers in a consistent manner. Rather than using legacy hash

functions, we employ advanced encryption standard (AES) [13] for

creating the required hashing streams in a Bloom filter. AES is a

standard and widely-used block cipher that guarantees both high

capabilities in terms of security and speed. In particular, since AES

is supported by most of the microprocessors, Bloom filter

realisation that is driven by AES can be easily unified. Basically,

our approach leverages AES new instructions (or AES-NI) [14,

15], a cryptographic microprocessor instruction set proposed by

Intel. We employ AES counter mode [16] to achieve efficient hash

function generation, and we illustrate how to enable Bloom filter

functions with corresponding AES-NI operations. According to our

experimental results, the processing time of such AES-NI

supported Bloom filter can be reduced significantly. We summarise

the main contributions of the paper as follows:

• We present a novel lightweight Bloom filter construction based

on AES counter mode and its realisation method conducted by

AES-NI. Namely, only AES-based one-way functions are

involved to build a Bloom filter. The microprocessor-supported

feature of our approach naturally unifies the Bloom filter

realisations and facilitates the deployment of relevant

applications.

• We theoretically prove the feasibility and correctness of the

proposal. According to our analysis, our AES-based Bloom

filter satisfies all required hashing properties.

• We implement the proposed Bloom filter as well as other four

popular Bloom filters in a common framework. Based on the

comprehensive comparison results, our Bloom filter outperforms

all competing methods in terms of processing time.

The rest of the paper is organised as follows. We illustrate how

a standard Bloom filter works in Section 2. Then we present our

detailed design in Section 3, followed by a formal analysis of our

method in Section 4. We show the evaluation results in Section 5

and give our remarks in Section 6. Related work is presented in

Section 7 and we conclude the paper in Section 8.

2 Background: Bloom filter

In this section we briefly introduce the standard form and the

mathematical preliminaries behind a Bloom filter. More complete

specifications can be found in [11, 17].

Table 1 Bloom filter applications and the scale of the

potential element queries

Application cases Insertion/query

elements

Potential query

scale

DDoS protection [4] packet information

multicast routing [6] forwarding address

cache filtering [7] web objects

flow measurement [8] flow identifier

data monitoring [9] data value

IET Commun., 2017, Vol. 11 Iss. 11, pp. 1815-1821

1815

下载后可阅读完整内容，剩余6页未读，立即下载

weixin_38687648

粉丝: 2
资源: 937

AES指令集加速的网络协议高效Bloom过滤器实现

Bloom过滤器学习笔记

Bloom过滤器的C++实现

bloomf:Bloomf-用于OCaml的高效Bloom过滤器

dumbloom:用PLpgSQL编写的Postgres Bloom过滤器的Bloom过滤器的愚蠢实现

bloom:使用 dabloom 的 Rcpp 绑定实现 R Bloom 过滤器

PSI:基于ECDH和Bloom过滤器的私有集交叉点基数协议

Distributed-Systems-Bloom-Filters-Coded-Bloom-Filter-Counting-Bloom-Filter:在此项目中，我实现了Bloom Bloom过滤器，编码Bloom Bloom过滤器，Counting Bloom Filter计数。 这些用于Google Bigtable，Apache HBase，Apache Cassandra和PostgreSQL等系统中

pantopoda:快速高效的网络蜘蛛，使用bloom过滤器访问给定域中的所有链接，以存储访问的链接和多个线程以实现并发

bloom：Go包实现Bloom过滤器

bloomfilter-rs:用Rust制造的Bloom Bloom过滤器

最新资源

Distributed-Systems-Bloom-Filters-Coded-Bloom-Filter-Counting-Bloom-Filter:在此项目中，我实现了Bloom Bloom过滤器，编码Bloom Bloom过滤器，Counting Bloom Filter计数。这些用于Google Bigtable，Apache HBase，Apache Cassandra和PostgreSQL等系统中