摘要
在三态内容寻址存储器(Ternary Content Addressable Memory,TCAM)表项宽度和存储容量约束下,该文提出一种基于匹配表项压缩的BF-TCAM算法,采用Bloom-Filter(BF)对匹配关键字进行单字节编码压缩关键字长度,解决了匹配吞吐率低和存储空间不足问题。针对BF在表项压缩过程带来的冲突率上升问题,引入向量存储空间策略,利用向量存储空间实现多个哈希函数映射,相对于比特向量策略,有利于降低匹配冲突率。测试实验表明,相对于传统的TCAM匹配算法,BF-TCAM算法不但提高了匹配吞吐率和存储空间利用率,同时可有效降低BF压缩产生的冲突率。
Within the confines of access width and storage capacity in Ternary Content Addressable Memory(TCAM) chip,pattern matching algorithm using TCAM has low throughput and limited memory.This paper proposes BF-TCAM algorithm based on access compression by single byte coding using Bloom-Filter(BF) algorithm,increases the throughput and improves the utilization efficiency of storage space.BF algorithm will bring collision,which can be reduced by using vector memory instead of bit vector in BF-TCAM algorithm.The experimentation shows that the BF-TCAM algorithm proposed in this paper can improve the matching throughput and storage space utilization,and at the same time,effectively reduce the conflict ratio resulting from BF compression.
出处
《电子与信息学报》
EI
CSCD
北大核心
2011年第9期2212-2218,共7页
Journal of Electronics & Information Technology
基金
国家863计划重大专项
高可信业务管控系统基金(2009AA01A346)资助课题