基于BloomFilter的硬件字符串匹配设计与验证

布鲁姆过滤器（Bloom Filter）是一种基于多散列大数据量的数据检索分类算法,在分析布鲁姆过滤器工作原理的基础上,给出了一种基于标准布鲁姆过滤器的硬件字符串匹配检测系统模型。完成了该系统的C语言算法实现,通过实验测试与理论结果相比较,证明了其功能的正确性。在此基础上实现模型的Verilog RTL级描述,通过仿真,验证Verilog程序的功能。针对Altera CycloneⅡEP2C35F672C6FPGA（Field Programmable Gate Array）完成了逻辑综合和时序仿真,文中的硬件字符串匹配检测系统在网络入侵检测、数据库检索等方面具有一定的实用价值。     

一种新的基于LRU的大流检测算法

针对LRU(Least Recently Used)算法大流漏检率过高的问题,提出了一种采用CBF(Counting Bloom Filter)和LRU两级结构的大流检测算法。该算法根据大流占用带宽较大、持续时间较长的特点在CBF中引入时间窗口机制来滤出可能的大流,然后将流信息记录在LRU中作进一步筛选。从理论上分析了影响该算法性能的因素,考虑了在存储资源一定的条件下,如何设置参数以发挥该算法最大效能的问题。最后基于实际的互联网数据进行了对比验证。结果表明,与同类算法相比,该算法在有效降低大流漏检率的同时,提高了大流流量的测量精度。     

基于多维计数型布鲁姆过滤器的大流检测机制

高速网络环境中,实时、准确地提取大流量对于网络安全和网络管理具有重要意义。该文针对传统的流量测量方法受计算资源和存储资源的限制,提出了一种基于多维计数型布鲁姆过滤器(Multi-Dimensional Counting Bloom Fliter, MDCBF)的大流检测机制。它将1维的计数型布鲁姆过滤器(Counting Bloom Fliter, CBF)结构,扩展到支持多维业务流表示、查询和统计计数的MDCBF结构。基于Apriori原理,通过对MDCBF实施重正化,实现了用户自定义的大流检测。并能自适应地配置CBF参数,允许测量误差控制在预定义的范围内。基于计算机产生的模拟数据和实际互联网数据进行了仿真实验,结果显示:该方法既能获得较小的测量误差,又能获得较高的空间利用率。     

基于多位域的等概率随机IP流抽样算法

对IP流信息的全方位提取有助于实现网络实时监控,精细管理,有利于网络安全性能的提升。已有的等概率随机IP流抽样算法将大量的IP流重复抽样,浪费了宝贵的计算和存储资源。针对这个问题,在原有算法的基础上设计了一种新的等概率随机IP流抽样算法,该算法在Bloom Filter的基础上采用三层位域,两层同时测量,结果取交集的方法,便于实际使用并且有效减少了已被抽样的IP流被重复抽样。实验结果表明:新方法能够大幅度提高测量精度,节约了系统资源,可以适用于10 Gb/s左右的高速网络之中。     

关于布隆过滤器在BSS中应用

介绍布隆过滤器(Bloom Filter)的相关算法原理和使用说明,并阐述其在BSS领域中应用。通过与Redis缓存技术相结合,利用布隆过滤器(Boom Filter)的高效匹配、低存储等优势,提高BSS中排重效率,减少BSS对硬件扩容的需求。同时,阐述BSS排重中关于位数组的划分,以及针对布隆过滤器(Bloom Filter)对数据存在一定误判率的不足,并提出相应的应对措施。     

基于布隆过滤器的字符串模糊匹配算法的FPGA实现

深度包检测技术通过对数据包内容的深入扫描和检测,能够有效识别出隐藏在数据包有效载荷内的非法数据,但该技术存在功耗非常大的缺点。针对该问题,提出了采用Bloom Filter(布隆过滤器)进行字符串模糊匹配方式,利用Bloom Filter将信息流中大部分正常流量过滤掉,从而减轻了后端的字符串精确匹配的压力,降低了系统功耗,大大提高了处理速度。     

基于计数布鲁姆过滤器的快速多维包分类算法

本文从数据包匹配规则的聚集特性出发,将计数布鲁姆过滤器和哈希表相结合,设计并实现了一种高效的多维包分类算法CBHT(Counting Bloom filter and Hash Table).基于包匹配规则的聚集特性,对于五维包分类问题,CBHT算法首先利用计数布鲁姆过滤器的过滤功能结合单域匹配获得与前两维匹配的小规模规则集,而后在此有限规则集中对后三维进行匹配.利用计数布鲁姆过滤器提高了包匹配速度并有效支持规则库的动态更新.实验结果表明CBHT算法比现有的B2PC算法节省60%的硬件资源,包匹配访问内存次数平均低于B2PC算法22.8%.     

基于抽样和哈希技术的长流测量算法研究

在互联网中理解网络行为最高效的途径即是对网络数据流量进行检测与分析,它是对已有互联网的组建、规范化和改造的依据,同时也是对Internet进行检测的重要环节.为了解决网络中的资源和高速IP流量之间的冲突问题,需要对网络流进行多种方式的处理与算法研究.本文首先提出了改进的数据抽样技术并综合论述了现阶段基于抽样技术的数据测量算法的研究.同时通过对重要数据参数的重新设置和分析,并结合使用多种数据取样的方法,探讨改进的数据空间映射技术与现阶段的各种取样方式在测量网络长流算法中的综合应用.     

基于节点动态内容流行度的缓存管理策略

针对命名数据网络中节点无法感知内容流行度变化的缺陷,提出了基于缓存内容流行度动态变化的内容管理策略.将缓存分为主缓存（Primary Cache,PC）和副缓存（Secondary Cache,SC）,分别用于识别和保护流行内容;采用标准布鲁姆过滤器（Standard Bloom Filter,SBF）过滤流行内容请求;引入滑动时间窗口算法和HASH表对副缓存内容进行细粒度的统计分析,进而管理缓存内容.仿真显示,与现有算法相比,该策略以增加少量复杂度为代价,延长高流行度内容的缓存驻留时间,提高了缓存命中率,减轻了服务器负载,并具有可扩展性,具备单线路40Gbit/s的报文处理能力.     

基于LRU_CBF的大流识别算法

对网络中的大流进行提取和分析对于网络管理和安全防御具有重要意义.文章通过把最近最久未使用(LRU)策略和计数型布鲁姆过滤器(CBF)两种结构结合起来,取其各自的优点,提出一种新的大流检测算法.该算法针对大流检测漏报率高的缺陷,将“大流过滤”和“大流判断”分离,提高了算法的准确性,降低了空间复杂度.最后通过理论分析和仿真实验进行了算法的验证.     

Performance evaluation and comparison of three counting bloom filter schemes

The Counting Bloom Filter (CBF) is a kind of space-efficient data structure that extends a Bloom filter so as to allow approximate multiplicity queries on a dynamic multi-set. This paper evaluates the performance of multiplicity queries of three simple CBF schemes–the Naïve Counting Bloom Filter (NCBF), the Space-Code Bloom Filter (SCBF) and the d-left Counting Bloom Filter (dlCBF)–using metrics of space complexity and counting error under both uniform and zipfian mul-tiplicity distributions. We compare their counting error under same space complexity, and their space complexity when similar counting errors are achieved respectively. Our results show that dlCBF is the best while SCBF is the worst in terms of both space-efficiency and accuracy. Furthermore, the per-formance gap between dlCBF and the others has a trend of being enlarged with the increment of space occupation or counting accuracy.     

基于布鲁姆过滤器算法和三态内容寻址存储器的高效范围匹配方法

该文基于布鲁姆过滤器算法和三态内容寻址存储器(Ternary Content Addressable Memory, TCAM)技术提出一种高效范围匹配方法,解决了目前TCAM范围匹配方案存在的存储利用率低、功耗大的问题。设计基于最长共同前缀的分段匹配算法(Segmented Match on Longest Common Prefix, SMLCP)将范围匹配拆分为前缀匹配和特征区间比对两步,TCAM空间利用率达到100%。根据SMLCP算法设计了BF-TCAM模型,使用布鲁姆过滤器对关键字过滤,屏蔽无关项参与比较,大幅降低功耗。使用流水线缩短关键路径长度,使查找操作在一个时钟周期内完成。研究结果表明,所提方法实现了零范围扩张,工作功耗较传统TCAM降低50%以上。     

机动目标跟踪的新算法

机动目标通常不是做恒定的运动,其运动状态会随时间的变化而变化.这就使描述系统运动的状态方程是非线性的,而且系统参数会不断变化.传统的推广卡尔曼滤波适用于定系统定参数的情况,如果运用到机动目标跟踪上会导致误差增大甚至滤波发散.基于此,将强跟踪滤波运用到机动目标跟踪上.强跟踪滤波在卡尔曼滤波的基础上引入了多重渐消因子,使强跟踪滤波具有极强的跟踪能力和较好地鲁棒性,因此可以很好地解决变系统变参数的问题.通过仿真,将强跟踪滤波与UT-BLUE滤波方法和EKF滤波方法进行比较,结果表明了该滤波方法的有效性和优越性.     

基于布鲁姆过滤器的文本检索系统研究

针对目前文本检索系统出现的信息重复,冗余等问题,提出了一种将布鲁姆过滤器算法与MD5有效结合的方案。对检索关键字进行MD5预处理操作,充分利用MD5的可靠性。并发挥鲁姆过滤器降低检索算法的时间复杂度和空间复杂度的特点,大大提高了检索的快速性,相关性和完备性。     

面向大数据处理的高精度多维计数布鲁姆过滤器

分析了现有多维布鲁姆过滤器查询算法的工作原理和特点,针对大数据处理特点提出了一种基于双射函数的高精度多维计数布鲁姆过滤器(AMD-CBF)查询算法.AMD-CBF中元素表示和查找分两步进行,第1步将元素各属性哈希映射到各自对应的高精度计数布鲁姆过滤器(A-CBF)中;第2步将元素的所有属性通过双射函数转换为一个值来表示元素整体信息,然后将这个值哈希映射到联合计数布鲁姆过滤器中(C-CBF),完成元素整体的表示和查询确认.理论分析和仿真实验结果表明,AMD-CBF能够支持多维集合元素的高效表示和查询及删除,相比同类研究查询假阳性降低明显,查询精度大幅度提高.     

基于深度布隆过滤器的NDN网络三级名字查找方法

为提高命名数据网络(Name Data Networking, NDN)路由过程中内容名字查找的效率,该文提出一种基于深度布隆过滤器的3级名字查找方法。该方法使用长短记忆神经网络(Long Short Term Memory, LSTM)与标准布隆过滤器相结合的方法优化名字查找过程;采用3级结构优化内容名字在内容存储器(Content Store, CS)、待定请求表(Pending Interest Table, PIT)中的精确查找过程,提高查找精度并降低内存消耗。从理论上分析了3级名字查找方法的假阳性率,并通过实验验证了该方法能够有效节省内存、降低查找过程的假阳性。     

拆分型Bloom Filter

Bloom Filter对数据集合采用一个位串表示并能有效支持集合元素的哈希查找操作.在对Bloom Filter及其改进型进行综述性分析研究并探讨它们的实用性之后,本文提出了使用位矩阵表示数据集合的拆分型Bloom Filter并对其作了分析比较研究,以允许集合元素不断增加的分布式系统应用模型为例,证明它能缓解增长问题并能有效节省全局的集合表示空间需求量.     

An opportunistic routing mechanism for real‐time voice service in mobile ad hoc networks

The opportunistic routing mechanism can use several lossy broadcast links to support reliable transmission. In this paper, a simple opportunistic routing mechanism for real‐time multimedia services is proposed. This mechanism is based on the dynamic source routing protocol with some modifications, multiple route request, and route reply messages are used to construct the forwarder list, and the nodes within the forwarder list forward the packets which they overhear. The forwarder list is placed on the packet header in the form of a Bloom filter, which will restrict the size of the forwarder list to a constant value. There are no strict scheduling mechanisms for the forwarding order of the forwarder nodes, thus our opportunistic routing mechanism can be scalable for multiple simultaneous flows. Simulations show that our mechanism can effectively decrease the transmission times and the amount of the control messages for each packet and reduce the end‐to‐end delay for real‐time voice service, the quality of service for these services can be supported well over the unstable wireless channel. Copyright © 2009 John Wiley & Sons, Ltd.     

Reducing false rate packet recognition using Dual Counting Bloom Filter

Distributed Denial of Service (DDoS) attacks are a serious threat to Internet security. A lot of research effort focuses on having detection and prevention methods on the victim server side or source side. The Bloom filter is a space-efficient data structure used to support pattern matching problems. The filter is utilised in network applications for deep packet inspection of headers and contents and also looks for predefined strings to detect irregularities. In intrusion detection systems, the accuracy of pattern matching algorithms is crucial for dependable detection of matching pairs, and its complexity usually poses a critical performance bottleneck. In this paper, we will propose a novel Dual Counting Bloom Filter (DCBF) data structure to decrease false detection of matching packets applicable for the \(\textit{SACK}^2\) algorithm. A theoretical evaluation will determine the false rate probability of detection and requirements for increased memory. The proposed approach significantly reduces the false rate compared to previously published results. The results indicate that the increased complexity of the DCBF does not affect efficient implementation of hardware for embedded systems that are resource constrained. The experimental evaluation was performed using extensive simulations based on real Internet traces of a wide area network link, and it was subsequently proved that DCBF significantly reduces the false rate.