一种基于并行 Bloom Filter 的高速 URL 查找算法

• 作者: 付文亮 刘庆云 周舟 嵩天
• 来源期刊: 电子学报
• 学科: 工学
• 关键词: URL 查找 布鲁姆过滤器 最长前缀匹配 现场可编程门阵列
• 年，卷（期）: 2015,（9）
• 所属期刊栏目: 学术论文
• 页码范围: 1833-1840
• 页数: 8页
• 分类号: TP393
• 字数: 7330字
• 语种: 中文
• DOI: 10.3969/j.issn.0372-2112.2015.09.023

摘要

URL 查找是众多网络系统中重要的组成部分，如 URL 过滤系统、Web 缓存等．随着互联网的迅速发展， URL 查找面临的主要挑战是实现大规模 URL 集合下的高速查找，同时保证低存储和低功耗．本文提出了一种基于并行 Bloom Filter 的 URL 查找算法，CaBF．该算法高度并行化，提供大规模 URL 集合下的高速最长前缀匹配，并很好地适应集合中不同数量的 URL 组件．理论分析和真实网络数据集上的实验表明，该算法相比现有算法可以降低假阳性概率达一个数量级（或者在满足相同假阳性概率的前提下降低存储和硬件逻辑资源消耗）．此外，该方法的体系结构很容易映射到 FPGA 等硬件器件上，提供每秒超过150M次的 URL 查找速度．

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	周舟	中国科学院信息工程研究所信息内容安全技术国家工程实验室	13	92	5.0	9.0
2	嵩天	北京理工大学计算机学院	30	331	10.0	18.0
3	付文亮	北京理工大学计算机学院	3	29	2.0	3.0
4	刘庆云	中国科学院信息工程研究所信息内容安全技术国家工程实验室	10	87	5.0	9.0