Hardware-based high-performance string lookup with value retrieval using extended Bloom filter

doi:1005-8885 (2008) 02-0097-05

Acta Metallurgica Sinica(English letters) ›› 2008, Vol. 15 ›› Issue (2): 97-101.doi: 1005-8885 (2008) 02-0097-05

• Microelectronics • 上一篇下一篇

Hardware-based high-performance string lookup with value retrieval using extended Bloom filter

李奇越屈玉贵赵保华

Department of Computer, University of Science and Technology of China, Hefei 230027,China

收稿日期:2007-09-07 修回日期:1900-01-01 出版日期:2008-06-30
通讯作者: 李奇越

Hardware-based high-performance string lookup with value retrieval using extended Bloom filter

LI Qi-yue, QU Yu-gui, ZHAO Bao-hua

Department of Computer, University of Science and Technology of China, Hefei 230027,China

Received:2007-09-07 Revised:1900-01-01 Online:2008-06-30
Contact: LI Qi-yue

摘要/Abstract

摘要：

In network packet processing, high-performance string lookup systems are very important. In this article, an extended Bloom filter data structure is introduced to support value retrieval string lookup, and to improve its performance, a weighted extended Bloom filter (WEBF) structure is generalized. The optimal configuration of the WEBF is then derived, and it is shown that it outperforms the traditional Bloom filter. Finally, an application-specific integrated circuit (ASIC)-based technique using WEBF is outlined.

关键词:

Bloom;filter,;value;retrieval,;string;lookup,;Hash;function,;ASIC

Abstract:

Key words:

Bloom filter;value retrieval;string lookup;Hash function;ASIC

中图分类号:

TN393

LI Qi-yue, QU Yu-gui, ZHAO Bao-hua. Hardware-based high-performance string lookup with value retrieval using extended Bloom filter[J]. Acta Metallurgica Sinica(English letters), 2008, 15(2): 97-101.

参考文献

1. Young H C, William H M. A pattern matching co-processor for network security. Proceedings of IEEE 42nd Annual Conference on Design Automation, Nov 13-17, 2005, Anaheim, CA, USA: Piscataway, NJ, USA: IEEE, 2005: 234-239

2. Haoyu S, John W L. Efficient packet classification for network intrusion detecting using FPGA. Proceedings of the 2005 ACM/SIGDA 13th International Symposium on Field Program- mable Gate Arrays, Sep 12-16, 2005, Monterey, CA, USA. New York, NY, USA: ACM, 2005: 238-245

3. Waldvogel M, Varghese G. Scalable high speed IP routing lookups. Proceedings of the ACM SIGCOMM’97 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, Sep 14-18, 1997, France, ACM, 1997: 2-5

4. Sidhu R, Prasanna V K. Fast regular expression matching using FPGAs. Proceedings of the 9th Annual IEEE Symposium on Field Program-mable Custom Computing Machines, Apr 29-May 2, 2001, Rohnert Park, CA, USA. Los Alamitos, CA, USA: IEEE Computer Society, 2001: 227-238

5. Qu Yu-gui, Li Qi-yue. The research on high-speed hardware decoding based on ABNF. The Chinese Journal of Electronics, 2006, 9 (5): 253-256 (in Chinese)

6. Wang Shuo, Qu Yu-gui. Design of a processor for ABNF pattern matching. The Chinese Journal of Electronics, 2007, 35(5): 172-176 (in Chinese)

7. Burton H B. Space/time trade-offs in Hash coding with allowable errors. Communications of the ACM, 1970, 13(7): 422-426

8. Michael M. Compressed Bloom filters. IEEE/ACM Transactions on Networking, 2002, 10(5): 604-612

9. Sarang H S. Fast packet classification using Bloom filters. Proceedings of 2006 ACM/IEEE Symposium on Architecture for Networking and Communications Systems, Dec 3-5, 2006, San Jose CA, USA. New York, NY, USA: ACM, 2006: 61-70

10. Sarang D, Praveen K, David E T. Longest prefix matching using Bloom filters. Proceedings of the 2003 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, Aug 25-29, 2003, Karlsruhe, Germany. New York, USA. ACM, 2003: 201-212

11. Bruck, Jie Gao, Jiang An-xiao. Weighted Bloom filter. The 2006 IEEE International Symposium on Information Theory, Jul 9-14, 2006, Seattle, WA, USA. Piscataway, NJ, USA: IEEE, 2006: 2304-2308

12. Ramakrishna M V, Fu E, Bahcekapili E. A performance study of hashing functions for hardware applications. Journal of Computing and Information, 1994, 1(1): 1621-1636

[1]	季一木, 李可, 刘尚东, 刘强, 尧海昌, 李奎. Collaborative filtering recommendation algorithm based on interactive data classification[J]. 中国邮电高校学报(英文版), 2020, 27(5): 1-12.
[2]	吴青高小凤范九伦张恒昌. Application of smoothing technique on twin support vector hypersphere[J]. 中国邮电高校学报(英文版), 2020, 27(3): 31-41.
[3]	Yang Tao1, Yan Yonghong1, Zhang Yue1, Guo Huijuan1, Zhu Yongyuan2, Huang Wei1,3. Single-Cavity triangular substrate integrated waveguide bandpass filter with complementary triangular split ring resonator[J]. 中国邮电高校学报(英文版), 2019, 26(5): 94-98.
[4]	Wu Xiaochu1, Tang Guijin1,Liu Xiaohua1, Cui Ziguan1, Luo Suhuai2. Low-light color image enhancement based on NSST[J]. 中国邮电高校学报(英文版), 2019, 26(5): 41-48.
[5]	Zhai Qi, Jiang Mingyan. Supervised learning of enhancing convolutional Hash for image retrieval[J]. 中国邮电高校学报(英文版), 2019, 26(4): 51-61.
[6]	晁浩董亮刘永利. Improved vocal effort modeling by exploiting echo state network and radial basis function network[J]. 中国邮电高校学报(英文版), 2019, 26(3): 98-104.
[7]	李鑫谢刚高锦春. TMAHS: a truthful multi-unit double auction framework for heterogeneous spectrum in secondary market[J]. 中国邮电高校学报(英文版), 2019, 26(1): 82-94.
[8]	Yuan Fang, Tian Bin. Modified min-sum SCAN decoding algorithm for polar codes[J]. 中国邮电高校学报(英文版), 2018, 25(6): 90-96.
[9]	Wang En. Rotated hyperbola model for smooth support vector machine for classification[J]. 中国邮电高校学报(英文版), 2018, 25(4): 48-55.
[10]	Zhou Shuisheng, Wang Baojun, Chen Li. High precision approximate analytical solutions to ODE using LS-SVM[J]. 中国邮电高校学报(英文版), 2018, 25(4): 94-102.
[11]	郑喆田磊张建华. Elevation spatial characteristic investigation based on 3D massive MIMO channel measurements at 6 GHz[J]. 中国邮电高校学报(英文版), 2018, 25(3): 1-7.
[12]	Ma Xin,Jing Xiaojun. Palm vein recognition method based on fusion of local Gabor histograms[J]. 中国邮电高校学报(英文版), 2017, 24(6): 55-66.
[13]	武昆李桂菊韩广良杨航刘培勋. Color image detail enhancement based on quaternion guided filter[J]. 中国邮电高校学报(英文版), 2017, 24(4): 40-50.
[14]	姚引娣曾志斌. Design of a wideband common-mode filter using approximate closed- loop pattern of compact C-shaped defected ground structure[J]. 中国邮电高校学报(英文版), 2017, 24(3): 70-74.
[15]	王珺易琼王悦贾莹莹. Distributed data storage solution under sink failures in wireless sensor networks[J]. 中国邮电高校学报(英文版), 2017, 24(2): 72-82.

Hardware-based high-performance string lookup with value retrieval using extended Bloom filter

Hardware-based high-performance string lookup with value retrieval using extended Bloom filter

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价