Bloom Filter技术及应用

Bloom Filter采用位串向量表示数据集合,能够实现高效集合查询的数据结构。首先介绍了标准布隆过滤器的概念和工作原理,然后通过实验分析布隆过滤器的错误率、空间向量和哈希函数数量三者之间的动态相关关系,并对独立空间布隆过滤器和标准布隆过滤器性能进行对比,最后讨论了Bloom Filter的变种及应用。     

浅析Bloom Filter

Bloom Filter是一种空间和时间效率很高的二进制项量数据结构,它利用位数组很简单地表示一个集合,并能检索一个元素是否属于这个集合。Bloom Filter的高效检索是由有一定误报率换来的。因此,Bloom Filter只适合那些允许一定误报率的应用场合。     

基于Bloom Filter的路由循环实时被动检测方法

为了解决网络中路由循环的实时检测问题,提出了一种基于Bloom Filter的路由循环实时被动检测方法.这种方法利用Bloom Filter存储资源占用小和查找时间消耗少的优点快速地发现源、宿地址,源、宿端口号均相同的疑似循环路由报文,再通过对报文TTL值递减特征的判断确定循环路由现象的存在.对于Bloom Filter本身存在误判率的问题,该方法采用增大位向量的长度的方法予以解决.实验结果表明本方法可以准确地发现循环路由,与传统主被动探测路由循环方式相比,减少了对网络带宽资源的占用,同时极大提高了算法的实时性.     

分布式环境下改进的Bloom Filter过滤技术

分析了Bloom Filter技术在特殊的分布式系统———P2P系统中的应用.基于Bloom Filter提出了一种新的Division Bloom Filter(DBF)技术,DBF技术采用了一组相互独立的哈希函数来计算数据对象的地址序列,然后使用这组地址序列将数据对象存储到一个分片的位向量中,所以DBF技术可以有效减少数据对象的存储空间.实验证明,DBF不仅可以解决Bloom Filter在分布式环境下的动态更新问题,还可以有效减少BloomFilter的错误率以及改善其稳定性.最后还使用数据压缩技术进一步减少在P2P系统中使用DBF技术的结点间通信代价.     

一种去除重复URL的算法

通过对Bloom Filter算法及其改进型在Web信息采集时的去重策略进行分析,结合Dynamic Bloom Filter算法,采用动态数组对集合元素进行表示,提出了一种去重应用策略,实现了对集合中重复URL的频度查询和删除操作支持,最后使用该去重策略进行了实验并和其他策略进行了比较,实验证明该应用策略能够在误判率较低的情况下取得较好的去重效果。     

Bloom Filter和Weighted Bloom Filter的比较与研究

Bloom filter是一个简单的空间效率极高的数据结构,用于判别一个元素是否属于某个集合.Weighted Bloom filter和Bloom filter已经被建议作为共享Web cache信息的一种方式.利用Bloom filter表示共享信息的内容,大大降低了用于存储索引的空间消耗,减少了访问延迟.因为在代理之间只需传输Bloom filter而不是完整的cache目录表.分别从理论和实践方面比较了Bloom filter和Weighted Bloom filter,结果证明Bloom filter比Weighted Bloom filter更好.     

命名数据网络中基于多级计数Bloom过滤器的名字查找方法研究

针对目前NDN中大多数基于Bloom过滤器的名字查找方法仅考虑速率而忽略冲突概率的局限,提出了一种考虑名字冲突概率并基于多级计数Bloom过滤器的名字查找方法.该方法的实验结果表明:相对于目前广泛研究的计数Bloom过滤器、哈希函数和d-left计数Bloom过滤器,所提方法能有效降低冲突概率.     

一种基于Bloom Filter的正则表达式集合快速搜索算法

正则表达式搜索算法的性能与从非确定性有限状态自动机(NFA)的初始状态到终止状态的最短路径Lmin成正比,与正则表达式所表达的语言的前缀集合Pref(RE)成反比,而一般情况下Pref(RE)较大,确定Pref(RE)中的元素在目标文本中的出现位置比较困难.文中提出了一种基于Bloom Filter的正则表达式集合搜索算法,此算法利用Bloom Filter集合查询时间与集合大小无关的特点,可以快速准备定位Pref(RE)的出现位置,使得搜索速度不受Pref(RE)的影响,如果采用多个Bloom Filter并行,还可以间接增大Lmin.分析与测试结果表明,该算法较大地加快了正则表达式的搜索速度,对于正则表达式集合,算法性能改善尤其明显,在Lmin较长、Pref(RE)较大时,搜索速度可以提高数倍至数十倍,适合大规模的多正则表达式的快速搜索.     

基于联合多维动态Bloom过滤器的SDN多属性查找结构研究

软件定义网络(SDN)作为一种新型的网络架构,可以为核心网络及应用的创新提供良好的平台.作为SDN实现的关键技术Openflow在实际的应用中仍然存在一些技术瓶颈.本文提出一种联合多维动态Bloom过滤器(CMDDBF)查找结构来替代Openflow交换机中的三态内容寻址存储器(TCAM)来实现流表的转发和处理.CMDDBF解决了TCAM空间利用率低和价格昂贵的缺点,能够有效实现多字段数据的查找和处理操作,并根据流表的规模动态调整内存空间.实验表明:CMDDBF不仅可以有效实现多字段数据的查找,而且在降低误识率方面具有很好的性能.     

一种网络分组内容线速动态检测方法

针对高速网络内容检测中多模式匹配算法性能差和模式集不断动态变化的问题,提出了一种松散耦合的双通道线速动态内容检测方法.该方法包含快速通道和慢速通道两部分,快速通道利用可动态查询的并行Counting Bloom filter引擎过滤网络分组,过滤出的嫌疑分组送慢速通道利用高效动态模式匹配算法一步准确鉴别和分析,从而避免对正常分组的阻碍,达到线速检测.基于程序局部性原理,采用额定长度前缀的方法实现了对长模式的可扩展性.分析与模拟试验表明,该检测方法具有较高的吞吐性能,可以实现线速动态内容检测,同时减少了硬件资源开销,提高了可扩展性.     

基于哈希技术的流测量算法研究

基于哈希技术的流测量算法是网络测量领域的一种关键技术，对网络管理、规划和发展都有重要意义．本文对目前网络测量应用中常用的几种基于哈希技术的流测量算法进行研究比较，主要介绍了标准BF、CBF、MF、Sample and Hold、MGCBF和TCBF等几种哈希技术的工作原理、应用以及优缺点，并根据分析结果提出综合多种技术相结合的研究方向。     

基于MBF的船联网RFID数据流清洗算法

针对船联网RFID数据流因存在冗余数据而影响工作效率的问题,在传统布隆过滤器数据清洗算法的基础上构建了矩阵型布隆过滤器模型,提出了一种改进的布隆过滤器RFID冗余数据清洗算法.实验结果表明,数据流越大,算法的数据清洗效果越明显.     

一种网络内容快速动态检测方法

高速网络内容检测与过滤依赖于快速多模式匹配算法按预先定义的模式集对分组的任意位置内容进行匹配。模式集往往有成千上万条,长短不一且十分复杂。多模式匹配算法对存贮器的访问速度很敏感,算法的好坏往往成为系统的性能瓶颈。另外,新的攻击层出不穷导致模式内容不断变化,如何在检测的同时有效地更新模式集合对网络安全设备在不停机检测条件下实现规则的升级与更新尤其重要。针对上述问题,提出了一种松散耦合的双通道线速动态内容检测方法,快速通道利用可动态查询的并行Counting Bloom filter引擎过滤网络分组。过滤出的嫌疑分组送慢速通道利用高效动态模式匹配算法一步准确鉴别和分析,从而避免对正常分组的阻碍达到线速检测。基于程序局部性原理,采用了额定长度前缀的方法实现了对长模式的可扩展性。分析与模拟试验表明,检测方法具有较高的吞吐性能,可以实现线速动态深度分组检测,同时减少了硬件资源开销,提高了可扩展性。     

求解半定规划的原始对偶势下降内点算法研究

介绍了半定规划的一般模型、最优性条件及求解半定规划问题的原始对偶势下降内点算法.借助两个形象的图形分析了势下降内点算法的迭代轨迹,并对求解半定规划的Filter势下降内点算法进行了研究,提出了Filter的构造方法.在一定的条件下,该算法可避免Maratos效应和势函数海色矩阵不正定等问题的产生.     

INTERNET网防火墙的构筑与配置

本文在比较了两种基本防火墙技术以及三种防火墙结构的基础上，探讨了构筑子网过滤结构防火墙的配置方案。     

负载自适应的数据流流量测量算法

针对现有的数据流流量测量算法负载适应性不佳的问题,基于计数型布鲁姆过滤器,提出了一种负载自适应的数据流流量测量算法LACBF(load-adaptive counting bloom filter)。采用真实的网络流量数据,对LACBF算法的性能进行了仿真验证,结果表明,LACBF算法能够在网络流量动态变化的情况下获得比现有算法更小的测量误差。     

对匀速直线运动目标跟踪的转换坐标卡尔曼滤波算法

文章根据某型雷达对空间匀速直线运动目标的跟踪要求，采用了转换坐标卡尔曼滤波跟踪算法．在转换坐标卡尔曼滤波跟踪算法中，球坐标系下互相独立的观测噪声变换到直角坐标系下时将变成相关噪声，在解出此相关噪声的方差后即可按标准的卡尔曼滤波算法对目标进行跟踪，仿真结果显示，该算法收敛迅速，精度可以满足雷达对空间机动目标的跟踪要求．