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

doi:10.3969/j.issn.0372-2112.2015.09.023

电子学报 ›› 2015, Vol. 43 ›› Issue (9): 1833-1840.DOI: 10.3969/j.issn.0372-2112.2015.09.023

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

周舟¹, 付文亮², 嵩天², 刘庆云¹

1. 中国科学院信息工程研究所信息内容安全技术国家工程实验室, 北京 100093;
2. 北京理工大学计算机学院, 北京 100081

收稿日期:2014-03-16 修回日期:2014-07-11 出版日期:2015-09-25
- 通讯作者:
- 刘庆云
- 作者简介:
- 周舟男,1983年生,湖南长沙人,博士,助理研究员.主要研究方向为网络安全、高性能网络.E-mail:zhouzhou@iie.ac.cn;付文亮 男,1984年生,河北邯郸人,博士研究生.主要研究方向为网络安全、节能网络.E-mail:fuwenl@bit.edu.cn;嵩天男,1980年生,辽宁沈阳人,博士,副教授.主要研究方向为网络安全、计算机体系结构.E-mail:songtian@bit.edu.cn
- 基金资助:
- 国家高技术研究发展计划 ("863"计划)基金 (No.2011AA010703); 中国科学院战略性先导科技专项基金 (No.XDA06030200); 国家自然科学基金 (No.61402474)

Fast URL Lookup Using Parallel Bloom Filters

ZHOU Zhou¹, FU Wen-liang², SONG Tian², LIU Qing-yun¹

1. National Engineering Laboratory for Information Security Technologies Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China;
2. School of Computer Science, Beijing Institute Engineering, Chinese Acadenmy of Sciences, Beijing 100081, China

Received:2014-03-16 Revised:2014-07-11 Online:2015-09-25 Published:2015-09-25
- Supported by:
- Foundation of National High-tech R&D Program of China (863 Program) (No.2011AA010703); Chinese Academy of Sciences Strategic Pilot Project Fund (No.XDA06030200); National Natural Science Foundation of China (No.61402474)

摘要/Abstract

摘要：

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

关键词: URL查找, 布鲁姆过滤器, 最长前缀匹配, 现场可编程门阵列

Abstract:

URL lookup is fundamental to numerous networking systems,including URL filters,web caches,etc.With the explosive development of the Internet,the main challenge in implementing URL lookup operation is to achieve fast lookup speed and accommodate large URL sets while keeping memory and power consumption low.This paper presents a new URL lookup scheme based on parallel Bloom Filters.It can adapt to set cardinality and perform fast longest prefix matching(LPM)with large URL sets in a highly parallel fashion.The theoretical analysis and experiments on real-life data traces show that the proposed approach leads to reduced false positive probability for up to an order of magnitude(or reduced memory and hardware logic resources with the same false positive probability guaranteed)compared with the existing methods.Moreover,the architecture can be easily mapped to the state-of-the-art FPGAs with moderate resource consumption to provide over 150M lookups per second.

Key words: URL lookup, Bloom filter, longest prefix matching, FPGA

中图分类号:

TP393

周舟, 付文亮, 嵩天, 等. 一种基于并行Bloom Filter的高速URL查找算法[J]. 电子学报, 2015, 43(9): 1833-1840.

ZHOU Zhou, FU Wen-liang, SONG Tian, et al. Fast URL Lookup Using Parallel Bloom Filters[J]. Acta Electronica Sinica, 2015, 43(9): 1833-1840.

参考文献

[1] Broder A Z,et al.Efficient URL caching for world wide web crawling[A].Proc of WWW 2003[C].Budapest,Hungary:ACM,2003.679-689.
[2] Fan L,et al.Summary cache:a scalable wide-area web cache sharing protocol[J].IEEE/ACM Trans on Networking,2000,8(3):281-293.
[3] Huang N F,et al.A fast URL lookup engine for content-aware multi-gigabit switches[A].Proc of AINA 2005[C].Taipei,Taiwan:IEEE Computer Society,2005.641-646.
[4] Zhou Z,et al.A high-performance URL lookup engine for URL filtering systems[A].Proc of ICC 2010[C].Cape Town,South Africa:IEEE Computer Society,2010.1-5.
[5] Netcraft.September 2013 Web Server Survey[EB/OL].http://news.netcraft.com,2013-09-30.
[6] Michel B S,et al.URL forwarding and compression in adaptive web caching[A].Proc of INFOCOM 2000[C].Tel-Aviv,Israel:IEEE Computer Society,2000.670-678.
[7] Prodanoff Z G,et al.Managing routing tables for URL routers in content distribution networks[J].International Journal of Network Management,2004,14(3):177-192.
[8] Dharmapurikar S,et al.Longest prefix matching using bloom filters[J].IEEE/ACM Trans on Networking,2006,14(2):397-409.
[9] Yu H,et al.A memory-efficient hashing by multi-predicate bloom filters for packet classification[A].Proc of INFOCOM 2008[C].Phoenix,USA:IEEE Computer Society,2008.1795-1803.
[10] Chang F,et al.Bigtable:A distributed storage system for structured data[J].ACM Trans on Computer Systems,2008,26(2):1-26.
[11] Cai H,et al.Applications of bloom filters in peer-to-peer systems:issues and questions[A].Proc of NAS 2008[C].Chongqing,China:IEEE Computer Society,2008.97-103.
[12] Song H,et al.IPv6 lookups using distributed and load balanced bloom filters for 100Gbps core router line cards[A].Proc of INFOCOM 2009[C].Rio de Janeiro:IEEE Computer Society,2009.2518-2526.
[13] Lu Y,et al.Robust counting via counter braids:an error-resilient network measurement architecture[A].Proc of INFOCOM[C].Rio de Janeiro:IEEE Computer Society,2009.522-530.
[14] 王洪波,等.高速网络超连接主机检测中的流抽样算法研究[J].电子学报,2008,36(4):809-818. Wang Hong-bo,et al.On flow sampling for identifying super-connection hosts in high speed networks[J].Acta Electronica Sinica,2008,36(4):809-818.(in Chinese)
[15] 谢鲲,等.布鲁姆过滤器查询算法[J].软件学报,2009,20(1):96-108. Xie K,et al.Bloom filter query algorithm[J].Journal of Software,2009,20(1):96-108.(in Chinese)
[16] Guo D,et al.Theory and network applications of dynamic bloom filters[A].Proc of INFOCOM 2006[C].Barcelona,Spain:IEEE Computer Society,2006.1-12.
[17] Xiao B,et al.Using parallel bloom filters for multiattribute representation on network services[J].IEEE Trans on Parallel and Distributed Systems,2010,21(1):20-32.
[18] URLBlacklist.com.Thelatest blacklist download[EB/OL].http://urlblacklist.com,2013-09-20.
[19] Sogou.Sogou Labs User query log[EB/OL].http://www.sogou.com/labs/dl/q.html,2013-10-14.

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

Fast URL Lookup Using Parallel Bloom Filters

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	黄赟, 张帆, 郭威, 陈立, 羊光. 一种基于数据标准差的卷积神经网络量化方法[J]. 电子学报, 2023, 51(3): 639-647.
[2]	唐维伟, 钟胜, 卢金仪, 颜露新, 谭富中, 邹旭, 徐文辉. 基于FPGA的Skynet网络结构优化及高时效实现[J]. 电子学报, 2023, 51(2): 314-323.
[3]	田春生, 陈雷, 王源, 王硕, 周婧, 张瑶伟, 庞永江, 周冲, 马筱婧, 杜忠, 薛钰. 面向FPGA的布局与布线技术研究综述[J]. 电子学报, 2022, 50(5): 1243-1254.
[4]	罗阳锦, 张升伟, 陆浩. 高光谱微波辐射计宽带高速数字系统设计[J]. 电子学报, 2021, 49(2): 380-386.
[5]	曹保锋, 郑毅, 李鹏, 张雪芹, 李欣, 李小强, 胡淼. 微弱电磁脉冲信号低失真度实时检测的FPGA实现[J]. 电子学报, 2019, 47(8): 1797-1802.
[6]	闵富红, 金秋森. 双忆阻Shinriki振荡器的超级多稳态和反单调性分析[J]. 电子学报, 2019, 47(11): 2263-2270.
[7]	王今雨, 伍卫国, 秦朝楠, 赵东方, 聂世强. UPRFloor:一种动态可重构FPGA建模方法与布局策略[J]. 电子学报, 2018, 46(12): 2862-2869.
[8]	李冰, 周岑军, 陈帅, 吉建华. 用于SRAM PUFs的伪随机数发生器的FPGA实现[J]. 电子学报, 2017, 45(9): 2106-2112.
[9]	吴珊, 周学功, 王伶俐. 基于SRAM型FPGA单粒子效应的故障传播模型[J]. 电子学报, 2017, 45(8): 1976-1984.
[10]	史方显, 曾立, 陈昱, 王淼, 占丰. 改进型高速高精度CORDIC算法及其在DDFS中的应用[J]. 电子学报, 2017, 45(2): 446-451.
[11]	张朝柱, 韩吉南, 燕慧智. 高速高精度固定角度旋转CORDIC算法的设计与实现[J]. 电子学报, 2016, 44(2): 485-490.
[12]	李艳, 张东晓, 于芳. RTL综合中FPGA片上RAM工艺映射[J]. 电子学报, 2016, 44(11): 2660-2667.
[13]	刘书勇, 吴艳霞, 张博为, 张国印, 戴葵. 基于可重构计算系统的矩阵三角化分解硬件并行结构研究[J]. 电子学报, 2015, 43(8): 1642-1650.
[14]	李玮, 张大方, 黄昆, 谢鲲. 面向大数据处理的高精度多维计数布鲁姆过滤器[J]. 电子学报, 2015, 43(4): 652-657.
[15]	张震, 汪斌强, 陈庶樵, 郭通. 几何布鲁姆过滤器的设计与分析[J]. 电子学报, 2012, 40(9): 1852-1857.