该文基于布鲁姆过滤器算法和三态内容寻址存储器(Ternary Content Addressable Memory, TCAM)技术提出一种高效范围匹配方法,解决了目前TCAM范围匹配方案存在的存储利用率低、功耗大的问题。设计基于最长共同前缀的分段匹配算法(Segmented Match on Longest Common Prefix, SMLCP)将范围匹配拆分为前缀匹配和特征区间比对两步,TCAM空间利用率达到100%。根据SMLCP算法设计了BF-TCAM模型,使用布鲁姆过滤器对关键字过滤,屏蔽无关项参与比较,大幅降低功耗。使用流水线缩短关键路径长度,使查找操作在一个时钟周期内完成。研究结果表明,所提方法实现了零范围扩张,工作功耗较传统TCAM降低50%以上。
An efficient range matching method based on Bloom Filter algorithm and Ternary Content Addressable Memory (BF-TCAM) technology is proposed to resolve the problem that there generally exit low memory using ratio and high power dissipation in current TCAM range matching methods. An algorithm of Segmented Match on Longest Common Prefix (SMLCP) splits range matching into two stepsprefix matching and feature range comparation, resulting in 100% TCAM space using ratio. BF-TCAM is designed according to SMLCP algorithm, which filters searching key words by Bloom filter to avoid that unrelated items participate in comparation, so as to reduce greatly power dissipation. Critical paths are streamlined so that searching operation can be completed during one clock cycle. Research results demonstrate that BF-TCAM achieves zero range expansion, meanwhile power dissipation falls more than 50%.
戴紫彬,刘航天. 基于布鲁姆过滤器算法和三态内容寻址存储器的高效范围匹配方法[J]. 电子与信息学报, 2016, 38(8): 1872-1879.
DAI Zibin, LIU Hangtian. Efficient Range Matching Method Based on Bloom Filter and Ternary Content Addressable Memory. JEIT, 2016, 38(8): 1872-1879.
DONG Yongji, GUO Yunfei, HUANG Wanwei, et al. A new high-speed packet parsing architecture[J]. Journal of Electronics & Information Technology, 2013, 35(5): 1083-1089.
LI Zhitao, XU Yajing, LIU Lihong, et al. An approach to available bandwidth measurement in IPv6 networks[J]. Journal of Electronics & Information Technology, 2008, 30(9): 2283-2286. [3] Grammatikakis M D, Papadimitriou K, Petrakis P, et al. Security effectiveness and a hardware firewall for MPSoCs[C]. IEEE High Performance Computing and Communications, Paris, 2014: 1032-1039.
[4]
Grammatikakis M, Papadimitriou K, Petrakis P, et al. Security in MPSoCs: a NoC firewall and an evaluation framework[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2015, 34(8): 1344-1357.
TIAN Le. Research on storage and power efficiency packet classification algorithm based on TCAM[D]. [Master dissertation], PLA Information Engineering University, 2013.
ZHU Guosheng and YU Shaohua. Range matching method based on TCAM: C-TCAM[J]. Journal on Communications, 2012, 33(1): 31-37.
[7]
BREMLERR-BARR A and HENDLER D. Space-efficient TCAM-based classification using gray coding[J]. IEEE Transactions on Computers, 2012, 61(1): 18-30.
[8]
RAY S S and BHATTACHARYA A. A fast range matching architecture with unit storage expansion ratio and high memory utilization using SBiCAM for packet classification[C]. IEEE India Conference, Pune, 2014: 1-6.
ZHANG Shigeng, LIU Guangliang, LIU Xuan, et al. An energy-efficient and fast missing tag detection algorithm in large scale RFID systems[J]. Chines Journal of Computers, 2014, 37(2): 434-444.
WANG Yizhuo, ZUO Qi, JI Weixing, et al. Memory-aware and user-aware mapping of applications to MPSoCS[J]. Acta Electronica Sinica, 2015, 43(4): 631-638.