几何布鲁姆过滤器的设计与分析

针对经典计数型布鲁姆过滤器( NCBF)存储和查询性能较低的缺陷,提出了几何布鲁姆过滤器结构GBF.该结构通过引入“哈希指纹”、布鲁姆过滤器两次分割、基于桶负载存放的方法,实现了集合元素的简洁存储、快速查询.基于“微分方程”和“概率论”的相关知识,对GBF模型进行了理论分析和求解,建立了错误概率和计算复杂度的关系表达式,论证了GBF的几何分布特性.仿真结果表明:与NCBF相比,GBF具有较低错误概率和计算复杂度的同时,也能保持较高的空间利用率.     

基于同源组合布鲁姆过滤器的早期流量抽样算法

提出一种同源组合布鲁姆过滤器结构,该结构包含流抽样（sample）和分组计数（packet）2个计数器向量组合,2个计数器向量宽度不同,以相同的散列源函数计算散列位置。基于该结构设计的早期流量抽样算法利用2个计数器向量将流抽样判断与分组计数检测分开,避免了早期流量抽样中大量抽样已经结束的流对分组计数过程的影响。分析和实验结果表明,通过调节2个计数器的宽度比α,在不增加内存空间的条件下,该算法有效降低了误判率。     

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

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

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

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

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

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

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

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

基于计数布鲁姆过滤器的集合调和算法

提出了一种基于计数布鲁姆过滤器的集合调和方法,该方法将远程节点A和B上的数据集合SA和SB分别用计数布鲁姆过滤器表示,设为CBF(SA)和CBF(SB),节点A将CBF(SA)发送给节点B,节点B进行计数布鲁姆过滤器减运算,得到差过滤器CBF(SB)CBF(SA),然后利用CBF(SB)CBF(SA)查询并获得集合SB中的差集元素SB SA,并返回SB SA给节点A,最后节点A用差集SB SA和自身集合SA进行集合并运算,完成集合调和。由于计数布鲁姆过滤器支持集合元素的删除操作,因此,该方法非常适合应用于数据集合更新频繁的分布式系统。理论分析和仿真实验结果表明,该方法既具有精确集合调和,能得到全部SB SA元素的优点,也具有近似集合调和仅需单轮消息交换的优点。     

高速低功耗深度报文检测方法

针对基于三态内容寻址存储器(TCAM,ternary content addressable memory)的深度报文检测(DPI,deep packet inspection)存在的高功耗问题,提出一种分级DPI方法BF-TCAM。第一级采用低功耗的并行布鲁姆过滤器(bloom fliter)排除无需检测的正常报文;第二级采用TCAM对真正需要检测的攻击报文和第一级的假阳性误判报文做进一步的检测。由于网络流量中大部分报文是正常报文,攻击报文在其中只占很少的部分,布鲁姆过滤器的假阴性(false negative)概率为0,可以保证不会产生漏检,假阳性概率很低,可以保证高速DPI检测的同时大大地降低功耗。     

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

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

可扩展组播及其在数据中心网络中的应用

文章认为组播协议的可扩展性一直是阻碍组播技术广泛部署的重要因素之一,为此文章探讨了互联网环境下几种可扩展组播的解决方案:基于组成员稀疏分布的可扩展组播方案、基于布鲁姆过滤器的可扩展组播方案、基于聚合组播树的可扩展组播方案;数据中心网络中可扩展组播面临的新挑战主要来自于硬件限制导致无法同时容纳大量的组播组,同时基于组成员稀疏分布的可扩展组播方案和聚合组播树的方案在数据中心网中应用受限,为此文章探讨了数据中心网络环境下混合使用组播和单播的可扩展组播方案、基于布鲁姆过滤器的可扩展组播方案。摘要: