Computer Science ›› 2015, Vol. 42 ›› Issue (Z6): 429-434.

Previous Articles     Next Articles

Design and Implement of Exact Matching Algorithm Based on Bloom Filter

WANG Peng-chao, DU Hui-min, CAO Guang-jie, DU Qin-qin and DING Jia-long   

  • Online:2018-11-14 Published:2018-11-14

Abstract: Because the technology of Bloom filter makes the element which does not belong to a set misjudge the element belonging to the set and element removal is difficult,this paper introduced CAM(Content Addressable Memory) for two exact matches.We proposed that the k hash values of the Bloom filter store in CAM,in order to determine whether an element belongs to this collection,and it is easy to remove elements.The results of the algorithm based on Snort2.9 rule database show that,compared with single-stage CAM seeking,in false positive rate of 0.01,the BF-CAM system reduces by more than 5-fold reduction in resource consumption,10 times in power consumption,and it can reduce the load of system,improve system performance,and adapt to detect strings in the high-speed networks.

Key words: Bloom filter,CAM,String matching,Hash function,Network security

[1] Ruijie Network.DPI Technical Papers.http://wenku.baidu.com/ iew/aa73eac66137ee06ef f91879.html.2010.3
[2] Tuck N,Sherwood T,Calder B,et al.Deterministic memory- efficient string matching algorithms for intrusion detection[C]∥ Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies(INFOCOM 2004).IEEE,2004,4:2628-2639
[3] Introduction to Snort.http://www.snort.org/docs/
[4] Song H,Dharmapurikar S,Turner J,et al.Fast hash table lookup using extended bloom filter:an aid to network processing[J].ACM SIGCOMM Computer Communication Review,ACM,2005,35(4):181-192
[5] Mitzenmacher.Compressed bloom filters[J].IEEE/ACM Trans-actions on Networking(TON),2002,10(5):604-612
[6] Peir J K,Lai S C,Lu S L,et al.Bloom filtering cache misses for accurate data speculation and prefetching[C]∥Proceedings of the 16th International Conference on Supercomputing.ACM,2002:189-198
[7] Bloom B H.Space/time trade-offs in hash coding with allowable errors[J].Communications of the ACM,1970,13(7):422-426
[8] Mitzenmacher M.Compressed bloom filters[J].IEEE/ACMTransactions on Networking,2002,10(5):604-612
[9] 谢鲲.布鲁姆过滤器查询算法及其应用研究 [D].长沙:湖南大学,2007
[10] Tan J S,Kuang Z,Yang G.Bloom filter based frequent patterns mining over data streams [C]∥2012 International Conference on Graphic and Image Processing.International Society for Optics and Photonics,2013:87685V-87685V-7
[11] 徐欣,李宗华,卢启中,等.基于FPGA的内容可寻址存储器研究设计与应用[J].国防科技大学学报,2001,23(5):69-73
[12] Guo R,Delgado-Frias J G.IP Routing table compaction andsampling schemes to enhance TCAM cache performance[J].Journal of Systems Architecture,2009,55(1):61-69
[13] Kim Y D,Ahn H S,Kim S,et al.A high-speed range- matching TCAM for storage-efficient packet classification[J].IEEE Transactions on Circuits and Systems I:Regular Papers,2009,56(6):1221-1230
[14] Chen Y,Oguntoyinbo O.Power efficient packet classification using cascaded bloom filter and off-the-shelf ternary CAM for WDM networks[J].Computer Communications,2009,32(2):349-356
[15] Kanizo Y,Hay D,Keslassy I.Access-efficient balanced Bloom filters[J].Computer Communications,2013,36(4):373-385
[16] AbuHmed T,Mohaisen A,Nyang D H.A survey on deep packet inspection for intrusion detection systems[J].Magazine of korea Telecommunication Society,2007,24(11):25-36
[17] McLaughlin K,O’Connor N,Sezer S.Exploring CAM design for network processing using FPGA technology [C]∥International Conference on Internet and Web Applications and Services/ Advanced International Conference on Telecommunications,2006(AICT-ICIW’06).IEEE,2006:84-84
[18] 田耘,徐文波.Xilinx FPGA 开发实用教程[M].北京:清华大学出版社,2008

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!