基于布鲁姆过滤器算法和三态内容寻址存储器的高效范围匹配方法

戴紫彬; 刘航天

doi:10.11999/JEIT151264

基于布鲁姆过滤器算法和三态内容寻址存储器的高效范围匹配方法

doi: 10.11999/JEIT151264

戴紫彬¹,
刘航天¹

计量
- 文章访问数: 1359
- HTML全文浏览量: 106
- PDF下载量: 447
- 被引次数: 0
出版历程
- 收稿日期: 2015-11-10
- 修回日期: 2016-03-21
- 刊出日期: 2016-08-19

Efficient Range Matching Method Based on Bloom Filter and Ternary Content Addressable Memory

DAI Zibin¹,
LIU Hangtian¹

摘要

摘要: 该文基于布鲁姆过滤器算法和三态内容寻址存储器(Ternary Content Addressable Memory, TCAM)技术提出一种高效范围匹配方法，解决了目前TCAM范围匹配方案存在的存储利用率低、功耗大的问题。设计基于最长共同前缀的分段匹配算法(Segmented Match on Longest Common Prefix, SMLCP)将范围匹配拆分为前缀匹配和特征区间比对两步，TCAM空间利用率达到100%。根据SMLCP算法设计了BF-TCAM模型，使用布鲁姆过滤器对关键字过滤，屏蔽无关项参与比较，大幅降低功耗。使用流水线缩短关键路径长度，使查找操作在一个时钟周期内完成。研究结果表明，所提方法实现了零范围扩张，工作功耗较传统TCAM降低50%以上。
- 范围匹配 /
- 布鲁姆过滤器 /
- 三态内容寻址存储器 /
- 零范围扩张 /
- 低功耗
Abstract: 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%.
- Range matching /
- Bloom Filter (BF) /
- Ternary Content Addressable Memory (TCAM) /
- Zero range expansion /
- Low power dissipation

HTML全文

参考文献(21)

董永吉, 郭云飞, 黄万伟, 等. 一种新的高速报文解析结构研究[J]. 电子与信息学报, 2013, 35(5): 1083-1089.

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.

李智涛, 徐雅静, 刘利宏, 等. 一种新的IPv6网络带宽测量方法[J]. 电子与信息学报, 2008, 30(9): 2283-2286.

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.

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.

田乐. 面向存储和功耗优化的TCAM报文分类算法研究[D]. [硕士论文], 解放军信息工程大学, 2013.

TIAN Le. Research on storage and power efficiency packet classification algorithm based on TCAM[D]. [Master dissertation], PLA Information Engineering University, 2013.

朱国胜, 余少华. 基于TCAM的范围匹配方法C-TCAM [J]. 通信学报, 2012, 33(1): 31-37.

ZHU Guosheng and YU Shaohua. Range matching method based on TCAM: C-TCAM[J]. Journal on Communications, 2012, 33(1): 31-37.

BREMLERR-BARR A and HENDLER D. Space-efficient TCAM-based classification using gray coding[J]. IEEE Transactions on Computers, 2012, 61(1): 18-30.

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.

侯颖, 郭云飞, 黄海, 等. 基于同源组合布鲁姆过滤器的早期流量抽样算法[J]. 通信学报, 2014, 35(10): 117-126.

HOU Ying, GUO Yunfei, HUANG Hai, et al. Early traffic sampling algorithm based on SSCBF[J]. Journal on Communications, 2014, 35(10): 117-126.

侯颖, 黄海, 兰巨龙, 等. 基于自适应超时计数布鲁姆过滤器的流量测量算法[J]. 电子与信息学报, 2015, 37(4): 887-894. doi: 10.11999/JEIT140820.

HOU Ying, HUANG Hai, LAN Julong, et al. An adaptive

timeout counter bloom filter algorithm for traffic

measurement[J]. Journal of Electronics Information Technology, 2015, 37(4): 887-894. doi: 10.11999/JEIT140820.

张士庚, 刘光亮, 刘璇, 等. 大规模RFID系统中一种能量有效的丢失标签快速检测算法[J]. 计算机学报, 2014, 37(2): 434-444.

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.

王一拙, 左琦, 计卫星, 等. 访存与用户行为敏感的MPSoC应用映射[J]. 电子学报, 2015, 43(4): 631-638.

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.

施引文献

资源附件(0)

访问统计