基于BF_TCAM实现零范围扩张的高效范围匹配方法

摘要

本发明提出了一种基于BF_TCAM实现零范围扩张的高效范围匹配方法，解决了目前基于TCAM实现范围匹配方法存在的存储利用率低、功耗大的问题，主要应用包括报文分类中端口范围匹配，存储保护中访存地址的审查等。本发明高效性体现在：高效存储、高速查找及低功耗。其特点在于，SMLCP算法将范围匹配过程分解为前缀匹配和特征区间比对两个步骤，从而便于使用TCAM技术，使TCAM存储利用率达到100％。根据SMLCP算法设计了BF_TCAM模型，按前缀长度对范围进行分类处理，使用Bloom？filter对关键字过滤，屏蔽无关项参与比较，从而大幅降低功耗。使用流水线技术减小电路关键路径长度，使查找操作在一个时钟周期内完成。

说明书

技术领域

本发明涉及一种基于Bloomfilter算法和TCAM(TernaryContentAddressableMemory,三态内容寻址存储器)实现零范围扩张的高效范围匹配方法，主要用于解决报文分类中端口范围匹配，存储保护中访存地址的审查等，实现访问控制、安全过滤、带宽控制等功能，广泛应用于防火墙、路由器、交换机、分布式存储网络、可信计算安全平台等设备中。这些应用对查找性能要求很高，高速的范围匹配是其实现的技术支撑。

背景技术

目前业界普遍使用TCAM实现高速查找表。和普通内存通过地址寻找内容不同，TCAM通过内容定位地址，它将查找输入的关键字和所有表项进行并行比较来定位关键字匹配的存储地址，根据得到的地址在RAM中索引规则内容。TCAM可以在固定的时钟周期完成查找操作，目前其时钟周期可以达到2ns，实现500MSPS的查找速率。TCAM三态特性需要使用多达16个晶体管来实现一个比特的存储，导致芯片面积较大且价格不菲，而其并行比较特性使得功耗很高，一个18Mbit的TCAM功耗高达15W。

TCAM突出的问题在于其不适于实现范围匹配，它的三态性便于实现精确匹配和前缀匹配。比如TCAM可以方便地表达报文分类中的协议字段和IP地址字段，但端口范围无法直接实现。目前已有方案是将范围匹配转换成前缀匹配和精确匹配，一个范围字段往往映射出多条匹配表项，称为范围扩张(rangeexpansion)。范围扩张降低了TCAM空间使用效率，造成了较大的配置负载，提高了更新代价，同时使TCAM的功耗问题雪上加霜。

文献“面向存储和功耗优化的TCAM报文分类算法研究(2013年解放军信息工程大学硕士论文)”提出一种基于域转换的范围匹配算法DTRM(DomainTransformationforRangeMatch)，充分利用TCAM表项中的冗余位压缩规则集，理想情况下可使范围扩张因子达到1.21以下，TCAM空间利用率提高到82％以上。文献“基于TCAM的范围匹配方法——C-TCAM(通信学报,2012,33(1):31-37)”提出一种基于TCAM的范围匹配方法C-TCAM(CompressedTCAM)，通过二级压缩将2个扩展后的表项压缩成一个，最坏情况下范围扩张因子为W-1或W-2(W为关键字位宽，如端口号位宽为16)，同时减少查找过程中无效表项参与比较来降低功耗。文献“Space-EfficientTCAM-BasedClassificationUsingGrayCoding(IEEETRANSACTIONSONCOMPUTERS,2012,61(1):18-30)”提出了基于格雷码的范围编码方法SRGE(ShortRangeGrayEncoding)，利用格雷码相邻编码之间只有一位不同的特点对规则集进行压缩，但随着范围长度增加格雷编码效率大打折扣，只适用于较小范围，最坏情况下扩展因子达到了2W-2。报文分类中要同时匹配源端口和目的端口两个字段，上述文献为代表的范围匹配方案扩张因子是单字段下的平方，大幅增加了规则表项，造成大量存储冗余，同时提高了更新操作的复杂性和TCAM功耗，如最差情况下DTRM造成49倍扩张，C-TCAM造成225倍扩张，SRGE造成784倍扩张，同时DTRM和C-TCAM每条表项需要额外使用32个比特。文献“AFastRangeMatchingArchitecturewithUnitStorageExpansionRatioandHighMemoryUtilizationusingSBiCAMforPacketClassification(2014AnnualIEEEIndiaConference)”提出一种用于范围查找的新型存储器结构SBiCAM(SmartBinaryContentAddressableMemory)，无需规则扩展，直接实现关键字与表项并行比较大小，而传统的TCAM只能判断是否相等，因而可实现高效的范围匹配。但其缺陷显而易见，SBiCAM是一种新型电路，投入实际应用尚需时日，从TCAM的发展历程可以判断SBiCAM即使投入生产也要经历一段漫长历程才能达到较理想的性能以满足应用需求。近年来出现TCAM分块存储策略，按照前缀长度进行分类存储，实现了前缀子集内表项的随机存放，提高了更新性能，而且查找操作只涉及TCAM部分区域，大幅降低了TCAM工作功耗，其中引入Bloomfilter对前缀分类处理是最近几年的一个创新。文献“LongestPrefixMatchingUsingBloomFilters(IEEE/ACMTRANSACTIONSONNETWORKING,2006,14(2):397-409)”利用Bloom_filter算法先对关键字的前缀长度进行预判断，再利用哈希查找表搜索前缀值，最差情况下需要使用N/2(N为前缀子集表项的最大数目)次哈希查找实现匹配，查找性能较TCAM差许多；文献“基于并行BP神经网络的路由查找算法(通信学报,2012,33(2):61-68)”提出BF_BP模型，第一步与文献“LongestPrefixMatchingUsingBloomFilters”相似，使用Bloomfilter匹配前缀长度，第二步利用BP反射神经网络实现前缀值匹配，然而其不足之处在于神经网络相比TCAM配置与更新要花费较长时间，需要多次训练实现神经单元学习。

发明内容

本发明所要解决的技术问题是提供一种基于Bloomfilter算法和TCAM实现零范围扩张的高效范围匹配算法，以解决基于TCAM实现范围匹配方法存在的存储利用率低、功耗大的问题，本算法高效性体现在：高效存储、高速查找及低功耗。

为达到上述目的，本发明具体方案如下。

一种基于BF_TCAM实现零范围扩张的高效范围匹配方法，适用于网络设备中端口范围匹配、存储保护中访存地址审查，设计了基于最长共同前缀的分段匹配(SegmentedMatchonLongestCommonPrefix,SMLCP)算法，将范围匹配转化为前缀匹配和特征区间比对两个步骤，实现了零范围扩张，使TCAM存储空间利用率达到100％；根据SMLCP算法设计了BF_TCAM模型，结合Bloomfilter的前缀分类处理优势和TCAM的高速查找特性，在保持高性能的同时大幅降低TCAM功耗；范围区间[s,t]内任意一整数点x，其二进制编码可以分为最长共同前缀和偏移量两段，其中LCP是区间内所有整数点的最长共同前缀，如LCP([37,57])＝001*_****是范围[37,57]的LCP，40的二进制编码分为001*_****和01000两部分，*表示不关心；SMLCP算法利用范围区间的这种特性，将匹配过程分段进行，其具体步骤如下：

步骤一，查找与关键字x任意长度前缀相匹配的范围区间，至多有W个范围的LCP与x相匹配，W为x二进制编码位宽；

步骤二，根据x的偏移量精确挑选出匹配的范围。

算法的关键在于第一步将搜索范围缩小至W个以下，从而大幅减小了查找范围。

使用分类处理思想，根据前缀长度划分范围子集，各子集独立并行处理，能够随机插入或删除表项，支持增量更新，从而提高了更新性能；利用Bloomfilter对关键字各长度前缀进行预判断，过滤无关范围子集参与比较，从而大大降低功耗；针对Bloomfilter无法删除元素的缺陷设计Bloomfilter计数器，将位数组的每一位扩展为计数器，每增加或删除一个元素时执行加1或减1操作；设计BF_TCAM模型，分为前缀预处理(BloomfilterPreprocessing,BFPP)单元，TCAM_RAM单元(附优化的区间比较器)，更新单元和状态单元；BFPP单元对关键字进行判断，筛选出关键字所在的前缀子集；TCAM_RAM单元存储所有范围的LCP、特征区间及附属信息(Acs_Infor)，每个前缀子集对应一组TCAM_RAM，由片选信号进行选择；更新单元维护Bloomfilter计数器，实时更新BFPP单元的Bloomfilter和TCAM_RAM，有效减少了电路资源开销；状态单元记录工作状态，指示关键字是否有效；利用SMLCP特征区间比对特点优化了比较器设计，降低电路资源开销。

配置过程分为4个步骤：

步骤1、获取范围区间；

步骤2、计算范围区间的lcp，根据LCP前缀长度划分子集；

步骤3、首先训练各子集的Bloomfilter计数器,对每个范围的LCP进行K组哈希计算，记录训练结果，当学习完所有范围后更新BFPP单元Bloomfilter的位数组，对应Bloomfilter计数器不为0的位被置1；

步骤4、配置TCAM和RAM，根据前缀长度找到相应TCAM块存入lcp值，范围的特征区间和附属信息存入RAM相应位置，该步骤与步骤3在时间上同步，没有序要求，完成配置。

查找过程分为3个步骤：

步骤1、前缀预处理，Bloomfilter对关键字各个长度前缀进行运算，将命中的前缀子集标记在匹配向量match_vector中，过滤掉其它子集，选中match_vector标记的TCAM块和RAM块，这个阶段如果发现没有匹配前缀即match_vector为0可判断关键字无效；

步骤2、在选中子集的TCAM块中查找关键字，若存在匹配表项，以其位置作为地址索引RAM，输出相关范围的特征区间至比较器；

步骤3、比较器判断关键字偏移量是否位于特征区间，若存在匹配区间，将对应的附属信息输出，完成范围匹配，否则判定关键字无效。

更新过程分为3个步骤：

步骤1、计算插入/删除范围的LCP，根据LCP前缀长度定位所属子集；

步骤2、训练子集对应的Bloomfilter计数器，对LCP进行K组哈希计算，记录计算结果，插入过程中如计数器发生0到1的正跳变,置BFPP单元Bloomfilter的位数组相应位为1，删除过程中如果Bloomfilter计数器发生1到0负跳变，置BFPP单元Bloomfilter的位数组相应位为0；

步骤3、在子集相应的TCAM块中存储/删除LCP，RAM块中存储/删除特征区间，完成更新。

增加流水线从而减少电路关键路径长度，使查找操作在一个时钟周期内完成，特殊情况下流水线停顿只延长一个时钟周期，以目前TCAM技术可使查找操作最多在4ns内完成。

BF_TCAM模型能够自动校正Bloomfilter产生的正误差，过滤掉因误判通过Bloomfilter筛选的关键字。

SMLCP算法具体实现时，由TCAM和RAM分别存储各范围的LCP标识和特征区间，使用TCAM完成第一步前缀与LCP的匹配，缩小查找范围，然后以TCAM匹配表项的位置作为地址搜索RAM，比对关键字偏移量是否位于特征区间，完成第二步精确匹配。SMLCP算法将范围匹配问题转化为前缀匹配和偏移比对两个步骤，在没有扩展规则集的情况下实现了精确查找，因而其扩张因子仅为1.0。因为SMLCP算法存在离散范围的前提条件，所以在规则制定中需要注意各个范围不能重叠，相互之间不能够存在交集。

按前缀长度将范围空间划分为不同的集合，比如IP报文端口号有16位，将端口范围按LCP长度划分为16个不同子集，每个子集单独存储于TCAM中的一块区域。为降低TCAM的功耗，生产厂家在设计时将TCAM进行了分块，在接口中增加片选信号，只有选中的块参与运算。在查找时首先通过Bloomfilter筛选出关键字所在的集合，然后驱动相应的TCAM块完成查找，这样仅被选中的TCAM块参与查找，功耗大幅降低。为进一步优化存储空间，根据前缀长度的分布规律为不同子集分配相应规模的存储空间。

该发明的有益效果在于：本发明提出了一种基于BF_TCAM实现零范围扩张的高效范围匹配方法，解决了目前基于TCAM实现范围匹配方法存在的存储利用率低、功耗大的问题，主要应用包括报文分类中端口范围匹配，存储保护中访存地址的审查等。本发明高效性体现在：高效存储、高速查找及低功耗。其特点在于，SMLCP算法将范围匹配过程分解为前缀匹配和特征区间比对两个步骤，从而便于使用TCAM技术，使TCAM存储利用率达到100％。根据SMLCP算法设计了BF_TCAM模型，按前缀长度对范围进行分类处理，使用Bloomfilter对关键字过滤，屏蔽无关项参与比较，从而大幅降低功耗。使用流水线技术减小电路关键路径长度，使查找操作在一个时钟周期内完成。本发明具有以下优点：(1)高效存储，范围匹配转化过程不增加任何冗余信息，扩张因子达到1.0，使TCAM空间利用率达到100％；(2)高速匹配性能，查找操作在一个时钟周期内即可完成；(3)大幅提高更新性能，支持表项的随机插入与删除；(4)大幅降低工作功耗，使用Bloomfilter进行预处理，可快速判断关键字可能存在的前缀子集，过滤无关子集参与运算。

附图说明

图1是本发明实施例中的Bloom_filter算法配置示意图。

图2是本发明实施例中的Bloom_filter查找示意图。

图3是本发明实施例中的BF_TCAM模型结构图。

具体实施方式

下面结合附图对本发明的具体实施方式进行描述，以便更好的理解本发明。

实施例

Bloomfilter算法介绍：BloomFilter是一种空间效率很高的随机数据结构，利用位数组简洁地表示一个集合，能判断一个元素是否属于该集合。BloomFilter包含一个m位的位数组，初始状态时每一位都置为0。为了表达含有n个元素的集合S＝{s1,s2,…,sn}，BloomFilter使用k个相互独立的哈希函数hash_i(i＝1,2…,k)，分别将集合中每个元素映射到{1,…,m}的范围中。对任意一个元素x，第i个哈希函数映射的位置hash_i(x)就会被置为1(1≤i≤k)，如图1所示。

在判断s是否属于集合时，对s应用k次哈希函数，如果所有hash_i(s)的位置都是1(1≤i≤k)，则s以一很大概率命中此集合，否则可判定s不属于此集合。如图2所示可以判定y1不是集合中的元素，而y2属于此集合是一个大概率事件。

BF_TCAM模型结构：BF_TCAM模型由四类单元构成：基于Bloomfilter的前缀预处理单元BFPP(BloomFilterPreprocessingUnit)，TCAM_RAM单元，更新单元(UpdataUnit)和状态单元(StateUnit)，如图3所示。

BFPP单元对关键字进行判断，筛选出关键字所在的前缀子集。如果关键字没有命中任何Bloomfilter，则可判断关键字无效，通知状态单元。

TCAM_RAM单元存储了所有范围的LCP、特征区间及附属信息(Acs_Infor)，每个前缀子集对应一组TCAM_RAM，由片选信号进行选择。仅被选中前缀集的比较器参与运算，当所有参与运算的比较器判断关键字不在特征区间内时，即判断关键字无效，通过零匹配(No_Match)信号通知状态单元。

使用Bloomfilter进行预处理，可快速判断关键字可能存在的前缀子集，过滤无关子集参与运算，但同时增加了电路关键路径长度，为了不降低时钟频率引入流水线，使查找操作在一个时钟周期内即可完成。特殊情况下流水线停顿造成查找操作增加一个时钟周期，但目前TCAM时钟频率已达到500MHz以上，意味着查找操作可在4ns内完成，能够满足性能需求。

本发明实施例中的具体工作流程如下：

如表1所示为一个8位范围集，R1-R10为初始范围集，R11为工作过程中添加的表项，表中标明了每个范围区间的LCP、特征区间及所属子集。

表1：范围集

编号 范围区间 LCP(二进制) 特征区间(二进制) 所属子集 R1 [10:28] 0000_1*** [010:100] C5 R2 [32:37] 0010_0*** [000:101] C5 R3 [38:57] 001*_**** [0_0110:1_1001] C3 R4 [66-81] 010*_**** [0_0010:1_0001] C3 R5 [99-118] 011*_**** [0_0011:1_0110] C3 R6 [137-165] 10**_**** [00_1001:10_0101] C2 R7 [172-198] 1***_**** [010_1100:100_0110] C1 R8 [200-208] 110*_**** [0_1000:1_0000] C3 R9 [212-236] 11**_**** [01_0100:10_1100] C2 R10 [244:245] 1111_010* [0:1] C7 R11 [85:93] 0101_**** [0101:1101] C4

配置过程如下：

步骤1：获取R1-R10共10个范围区间；

步骤2：计算范围区间LCP，根据LCP前缀长度划分子集，R1、R2属于C5，R3-R5、R8属于C3，R6、R9属于C2，R7属于C1，R10属于C7；

步骤3：首先训练1,2,3,5,7号Bloomfilter计数器,对范围的LCP进行K组哈希计算，记录训练结果，当学习完所有范围后更新BFPP单元1,2,3,5,7号Bloomfilter的位数组；

步骤4：TCAM和RAM按子集分别存储LCP和特征区间，该步骤与步骤3在时间上同步，没有序要求，完成配置。

以关键字Search_Key＝70(0100_0110)为例，查找过程如下：

步骤1：前缀预处理，Bloomfilter对Search_Key各个长度前缀进行运算，只有C3子集匹配，过滤掉其它子集，选中3号TCAM块和3号RAM块(T3和RAM3)；

步骤2：在T3中查找前缀010*_****，存在相关表项，索引RAM3输出特征区间到3号比较器(Comp3)；

步骤3：Comp3比较Search_Key[4:0]与特征区间，Search_Key[4]为0，因而选取特征区间起始端s’＝0010与Search_Key[3:0]＝0110比较，s’<Search_Key[3:0]，判断关键字匹配该范围区间，完成查找。

以动态插入R11为例，更新过程如下：

步骤1：计算P＝LCP(R11)＝0101_****，P前缀长度为4，R11所属子集为C4；

步骤2：训练4号Bloomfilter计数器，对P进行K组哈希计算，记录计算结果，如计数器发生0到1的正跳变,置BFPP单元4号Bloomfilter的位数组相应位为1；

步骤3：T4存储P，RAM4存储特征区间[0101:1101]，完成更新。

删除过程与插入过程相似，不同的地方为：步骤2如果Bloomfilter计数器发生1到0负跳变，置BFPP单元Bloomfilter的位数组相应位为0；步骤3删除TCAM和RAM中的表项。

以上所述是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也视为本发明的保护范围。