一种面向深度数据包检测的索引拆分Bloom过滤器 |
| |
引用本文: | 黄昆,;张大方.一种面向深度数据包检测的索引拆分Bloom过滤器[J].中国科学:信息科学,2010(8):1062-1077. |
| |
作者姓名: | 黄昆 ;张大方 |
| |
作者单位: | [1]湖南大学计算机与通信学院; [2]湖南大学软件学院 |
| |
基金项目: | 国家自然科学基金(批准号:90718008,60673155);国家重点基础研究发展计划(批准号:2007CB310702)资助项目 |
| |
摘 要: | 高速数据包处理迫切需要时空高效的深度数据包检测(DPI),满足其线速处理和低存储空间需求.Trie位图内容分析器(TriBiCa)采用片上位图Trie树来实现元素的最小完美Hash;但是,TriBiCa存在更新开销高和假阳性访问次数多等问题.共享节点快速Hash表(SFHT)采用片上计数Bloom过滤器(CBF)来实现硬件Hash表的快速查找;但是,SFHT存在更新开销高和存储空间需求大等问题.文中提出了一种索引拆分Bloom过滤器(ISBF).ISBF是由片上多组并行CBF和片外元素集构成,其核心思想是:元素的片外索引值被拆分成多组比特,每组比特采用多个片上并行CBF表示元素集;当查询元素时,每组并行CBF产生多个比特值,并合成候选元素的片外索引值.为了降低ISBF的更新开销,文中又提出了懒惰删除(lazyd eletion)算法和空缺插入(vacant insertion)算法,即采用一个片上删除位图,仅在片上并行CBF中删除或插入元素,而不需要调整其他元素的片外索引值.ISBF是一种时空高效的数据结构,其插入、删除和查询操作的平均片外存储器访问次数均为O(1);与TriBiCa和SFHT相比,ISBF在片上存储空间大小上分别减少2b倍和b倍,其中b为索引拆分的比特位数.实验结果表明,ISBF支持快速和存储高效的查找,即显著地减少片外存储器访问次数、处理时间以及片上和片外存储空间需求.
|
关 键 词: | 网络安全 数据包处理 深度数据包检测 Hash表 Bloom过滤器 |
本文献已被 维普 等数据库收录! |
|