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

• 作者: 刘航天 戴紫彬
• 来源期刊: 电子与信息学报
• 学科: 工学
• 关键词: 范围匹配 布鲁姆过滤器 三态内容寻址存储器 零范围扩张 低功耗
• 年，卷（期）: 2016,（8）
• 所属期刊栏目: 论文
• 页码范围: 1872-1879
• 页数: 8页
• 分类号: TP393.08
• 字数: 6712字
• 语种: 中文
• DOI: 10.11999/JEIT151264

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	戴紫彬	信息工程大学密码工程学院	39	133	6.0	10.0
2	刘航天	信息工程大学密码工程学院	3	4	1.0	1.0