一种基于Bloom_filter表项压缩的TCAM业务识别算法.docxVIP

一种基于Bloom-filter表项压缩的TCAM业务识别算法陈正虎*兰巨龙黄万伟李玉峰(国家数字交换系统工程技术研究中心郑州450002)摘要：在三态内容寻址存储器(TernaryContentAddressableMemory,TCAM)表项宽度和存储容量约束下，该文提出一种基于匹配表项压缩的BF-TCAM算法，采用Bloom-Filter(BF)对匹配关键字进行单字节编码压缩关键字长度，解决了匹配吞吐率低和存储空间不足问题。针对BF在表项压缩过程带来的冲突率上升问题，引入向量存储空间策略，利用向量存储空间实现多个哈希函数映射，相对于比特向量策略，有利于降低匹配冲突率。测试实验表明，相对于传统的TCAM匹配算法，BF-TCAM算法不但提高了匹配吞吐率和存储空间利用率，同时可有效降低BF压缩产生的冲突率。关键词：三态内容寻址存储器(TCAM)；Bloom滤波器(BF)；模式匹配中图分类号：TP393DOI:10.3724/SP.J.1146.2011.00058文献标识码：A文章编号：1009-5896(2011)09-2212-07ATCAMServiceIdentificationAlgorithmBasedonAccessCompressionUsingBloom-filterChenZheng-huLanJu-longHuangWan-weiLiYu-feng(NationalDigitalSwitchingSystemEngineeringTechnologicalRDCenter,Zhengzhou450002,China)Abstract:WithintheconfinesofaccesswidthandstoragecapacityinTernaryContentAddressableMemory(TCAM)chip,patternmatchingalgorithmusingTCAMhaslowthroughputandlimitedmemory.ThispaperproposesBF-TCAMalgorithmbasedonaccesscompressionbysinglebytecodingusingBloom-Filter(BF)algorithm,increasesthethroughputandimprovestheutilizationefficiencyofstoragespace.BFalgorithmwillbringcollision,whichcanbereducedbyusingvectormemoryinsteadofbitvectorinBF-TCAMalgorithm.TheexperimentationshowsthattheBF-TCAMalgorithmproposedinthispapercanimprovethematchingthroughputandstoragespaceutilization,andatthesametime,effectivelyreducetheconflictratioresultingfromBFcompression.Keywords:TernaryContentAddressableMemory(TCAM);Bloom-Filter(BF);Patternmatching1引言互联网上新型的业务层出不穷，P2P和流媒体类业务泛滥成灾，DDOS等异常流量攻击日益繁多，以及不健康的虚假、恶意信息发布日益猖獗，对互联网的公共和个人安全造成了威胁。为净化网络环境，需要对互联网上承载的不同业务进行准确地识别并有区分地处理。当前骨干网络的链路带宽已达到了40Gbps，而现有的业务识别系统的吞吐率在10Gbps左右，远远不能满足需要。因此迫切的需要一种高速的业务识别机制，对数据包的五元组以及负载作深度的报文检测[1]，满足链路的需求。对于模式匹配算法，按照实现途径有基于软件和基于硬件两种实现方式。传统的基于软件的算法有Knuth-Morris-Pratt(KMP)算法[2]，Boyer-Moore(BM)算法[3]，Aho-Corasick(AC)[4]算法以及Commentz-Walter(CW)算法[5]，改进型的Aho-Corasick-Boyer-Moore(ACBM)算法[6]和setwiseBoyer-Moore-Horspool(BMH)算法[7]在空间和时间损耗上要优于传统的算法，但基于软件的算法由于依靠处理器来完成，是一种时分复用的串行结构，随着模式集的增加，此类算法的空间复杂度也随之增加。目前基于软件实现的算法吞吐率一般小于1Gbps[8]，难以满足40Gbps网络线速的需求。目前高速的模式匹配算法主要分为基于硬件实现的Bloo