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

戴紫彬　刘航天

（信息工程大学密码工程学院郑州450004）



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

戴紫彬刘航天*

（信息工程大学密码工程学院郑州450004）

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

范围匹配；布鲁姆过滤器；三态内容寻址存储器；零范围扩张；低功耗

1　引言

范围匹配广泛应用于网络3到4层的报文分类，根据源端口和目的端口字段匹配端口范围，实现访问控制、安全过滤、带宽控制等功能［1，2］。在存储保护方面也有较多应用，比如审查进程发起的访存操作地址是否匹配其权限内的存储空间实现安全访问控制［3，4］。这些实时应用对查找性能要求很高，高速的范围匹配是实现实时应用的技术支撑。

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

文献［5］提出一种基于域转换的范围匹配算法DTRM（Domain Transformation for Range Match），充分利用TCAM表项中的冗余位压缩规则集，理想情况下可使范围扩张因子达到1.21以下，TCAM空间利用率提高到82%以上。文献［6］提出一种基于TCAM的范围匹配方法C-TCAM（Com pressed TCAM），通过二级压缩将2个扩展后的表项压缩成一个，最坏情况下范围扩张因子为W-1或W-2（W为关键字二进制编码位宽，如端口号位宽为16），同时减少查找过程中无效表项参与比较来降低功耗。文献［7］提出了基于格雷码的范围编码方法SRGE（Short Range Gray Encoding），利用格雷码相邻编码之间只有一位不同的特点对规则集进行压缩，但随着范围长度增加格雷编码效率大打折扣，只适用于较小范围，最坏情况下扩展因子达到了2W-2。文献［8］提出一种用于范围查找的新型存储器结构SBiCAM（Smart Binary Content Addressable Mem ory），无需规则扩展，直接实现关键字与表项并行比较大小，打破了传统的TCAM位比较结构，因而可实现高效的范围匹配。但SBiCAM是一种新型电路，投入实际应用尚需时日，从TCAM的发展历程可以判断SBiCAM即使投入生产也要经历一段漫长历程才能达到较理想的性能以满足应用需求。

本文为解决基于TCAM的范围匹配问题提供了高效解决方案，在实现零范围扩张的同时大幅降低TCAM功耗。提出基于最长共同前缀的分段匹配算法（Segmented Match on Longest Common Prefix，SMLCP），将范围匹配转化为前缀匹配和特征区间比对两个步骤，实现了零范围扩张，使TCAM空间利用率达到100%。根据SM LCP算法设计了BFTCAM模型，结合B loom filter的前缀分类处理优势和TCAM的高速查找特性，在保持高性能的同时大幅降低了TCAM功耗。

2　 SM LCP算法

2.1问题描述

首先对范围匹配问题进行形式化描述，以准确无误地表达问题实质，为SMLCP算法提供理论基础。

范围匹配问题等价描述为：给定一整数x，在S中定位包含x的元素即］使如图1所示。同时S集支持元素的动态插入与删除。

下面给出算法涉及的几个名词解释：

（1）最长共同前缀（Longest Comm on Prefix，LCP）：范围是一系列连续整数，位于数轴上的一段闭区间。最小的整数称为起点，最大的整数称为终点，构成范围的两个端点。起点与终点的二进制编码从第1个不同的比特位到最低位用*替代（*表示不关注），构成三态表示，这样的一个包含*的W位二进制编码称为范围的最长共同前缀（W为二进制编码位宽）。如8位范围［22:38］，起点22的二进制编码为0001_0110，终点38的二进制编码为0010_0110，则

图1　范围匹配的形式化描述

（2）特征区间（feature range）：范围起点与终点去除最长共同前缀后组成的新区间，它不改变范围的规模，标识了范围内所有整数的上限与下限，位宽为W-length（LCP）。如范围［22，38］的特征区间为［01_0110:10_0110］，位宽由8减为6。

（3）偏移量（offset）：范围内的一个整数，其二进制编码去除最长共同前缀后的数值，标明了它在特征区间内的偏移量，位宽与特征区间一致。如范围［22:38］内的整数31，偏移量为O ffset（31）=01_ 1111。

2.2算法设计与证明

范围［s，t］内任意一整数点x，其二进制编码分为LCP和O ffset两段，SMLCP算法利用这种特性，将匹配过程分段进行：首先查找与关键字x任意长度前缀相匹配的范围，至多有W个范围的LCP与x相匹配，然后再根据x的O ffset精确筛选出匹配的范围。算法的关键在于第1步将搜索范围减少至W个以下，大幅缩小了匹配范围。

定理1范围［s，t］两端点s，t的LCP是范围内所有整数点的最长共同前缀且这种对应关系是唯一的。

定理1要从LCP前缀值和前缀长度两个维度予以证明，包括：

（2）所有范围的LCP构成的集合称为标识集，P=LCP（s，t）是［s，t］内所有整数点共同前缀中最长的，即在标识集中不存在比P更长的LCP与范围内所有整数点相匹配。

范围为一个整数点时其前缀长度最长，容易处理，为方便证明，首先设定范围［s，t］至少包含两个整数点。定理1证明如下：

首先证明（1），分为两种情况：

（a）当h=g=x即范围［h，g］为一整数点时，

LCP为其自身，即LCP（h，g）=x。

∵P=LCP（s，t）的前缀长度小于x，

∴P≠x，得证。

（b）当h≠g时，使用反证法，

假设LCP（h，g）=LCP（s，t）=P，

令［h，g］在数轴上位于［s，t］的左边，即g＜s。

则h，g，s，t可以表示为

h=P 0*，g=P 1*，s=P 0*，t=P 1*。

∵g＜s，

∴有P1*＜P0*，

假设产生矛盾，得证。

下面证明（2），P=LCP（s，t），LCP（S）为标识集。使用反证法，假设∃PQ∈LCP（S），对于∀x∈［s，t］，LCP（x）=PQ，其中PQ表示覆盖P的前缀，只需在［s，t］中找出与PQ不匹配的整数即可证明假设错误，从而得证。

为方便证明，设定Q=0。分两种情况：

（a）当［s，t］包含3个及3个以上的整数点，则有u=P10..0∈［s，t］（0..0表示1个或若干个0），

但LCP（u）≠P0。

假设产生矛盾，得证。

（b）当［s，t］仅包含两个整数点，

则s=P0，t=P1，

显然LCP（t）≠P0，即得证。

综上所述，定理1得证。

LCP适于TCAM存储，无需范围扩张就可以唯一表示范围，实现了TCAM的高效存储，使存储利用率达到100%。对于关键字x，其任意长度的前缀可能与标识集中多个LCP相匹配，但其中至多只有一个LCP对应的范围包含x。例如R1为［37，57］，R2为［32，36］，P1=LCP（R1）=001*_****，P2=LCP（R2）= 0010_0***，关键字x=0010_0101（37）同时与P1，P2相匹配，但只有R1命中x。要实现精确查找，还要对与关键字前缀相匹配的所有范围进行筛选。需要指出，并非一定是与关键字前缀相匹配的最长LCP包含x，上例中虽然P2覆盖了P1，但其对应范围R2并不真正包含x。易得知，如果存在多个范围的LCP与关键字前缀匹配，则这些LCP之间存在覆盖关系，且数量不会超过关键字的位宽。

定理2对关键字进行分段匹配：当关键字某一长度前缀与范围LCP相匹配且偏移量位于特征区间内，则与该范围匹配，否则不匹配。定理2易于证明，不再予以详细论证。

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

3　 BF-TCAM模型

3.1模型设计

布鲁姆过滤器（B loom filter）是一种空间效率很高的随机数据结构，利用位数组简洁地表示一个集合，能判断一个元素是否属于该集合。B loom filter包含一个m位的位数组，初始状态每一位都置为0。为了表达含有n个元素的集合B loom filter使用k个相互独立的哈希函数Hash_i分别将集合中每个元素映射到｛1，2，，｝m…的范围中［911］-。

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

BF-TCAM模型由4类单元构成：基于B loom filter的前缀预处理BFPP（Prefix Prep rocessing unit on Bloom Filter）单元，TCAM_RAM单元，更新单元（Updata Unit）和状态单元（State Unit），如图2所示。

BFPP单元对关键字进行判断，筛选出关键字可能所在的前缀子集。为每个长度的前缀子集设置B loom filter，分别为判断关键字是否属于长度为i的前缀子集。所有B loom filter对关键字相应长度的前缀并行运算，判断结果组成匹配向量，表明关键字命中的前缀子集。匹配向量作为TCAM的块区域片选信号，被选中的块区域参与关键字的前缀匹配运算。如果关键字没有命中任何B loom filter，则可判断关键字无效，通知状态单元。

图2　 BF-TCAM模型电路结构解析

TCAM_RAM单元存储了所有范围的LCP、特征区间及附属信息，每个前缀子集对应一组TCAM_RAM，由片选信号进行选择。其中TCAM中存储范围的LCP，在BFPP单元选中的块区域中搜索与关键字匹配的表项，以匹配表项的地址索引RAM。RAM中存储了范围的特征区间及附属信息，如端口范围和控制信息。每个子集（除长为w的子集）设置比较器判断关键字偏移量是否位于特征区间内，w长子集为精确匹配，不存在特征区间，无需进行比较。特征区间端点最高位为固定值（起点为0，终点为1），利用此特点优化比较器减小电路资源开销：使用1个比较电路实现区间判断（通常设置2个，一个判断大于起点，另一个判断小于终点）。对于长度为j（1 j w≤<）的比较器，仅关键字的低w j-比特参与比较，比较电路输入位宽为1w j--。若所有参与运算的比较器判断关键字不在特征区间内，可判断关键字无效，通过零匹配信号通知状态单元。匹配特征区间的比较器输出相关附属信息。

Bloom filter位数组中每一位可能被多个元素共享，因而某元素的删除操作可能影响到其它元素，造成BFPP单元无法执行删除操作。为解决该问题，将B loom filter位数组的每一位扩展为BF计数器，每执行一次插入/删除操作相应位加/减1。进一步分析发现，更新操作较查找操作发生频率很低，为降低开销设置更新单元维护BF计数器，BFPP单元中的B loom filter依然保持位数组结构。当BF计数器跳变为0或由0变为正数时更新BFPP单元的B loom filter。TCAM_RAM单元同步更新。

Bloom filter的高效是以较低的错误率换取的，存在正误差，即Bloom filter判断通过的关键字以较小概率是无效的。这种误差并非随机的，对于特定关键字出现误判则该关键字永远出错。具体在模型中由BFPP和比较器的判断结果表现：当BFPP匹配向量不为0而比较器出现零匹配时，表明关键字通过Bloom filter判断却没有匹配的范围表项，误差出现。然而这种误差不影响匹配结果，最终将被比较器过滤掉，但较高的错误率会使更多TCAM块区域参与比较，从而增加了工作功耗。状态单元记录查找状态，通过无效信号指示关键字是否有效。

使用B loom filter进行预处理，可快速判断关键字可能存在的前缀子集，过滤无关子集参与运算，但同时增加了电路关键路径长度，为了不降低时钟频率引入二级流水线，将前缀预处理和TCAM_ RAM查找分为两级进行。

3.2算法流程

配置算法（BF-TCAM Configuration A lgorithm）流程如表1所示。

首先获取范围集，计算每一个范围的LCP，然后对LCP进行K次哈希计算，由BF计数器记录计算结果，根据计数值配置BFPP单元中的B loom filter，同时将LCP存入TCAM相应位置，特征区间和附属信息存入RAM相应位置。整个配置算法分为4个阶段：（1）获取范围集，如1～5行所示，共有N个范围（range），saddr表示起始地址，eaddr表示结束地址，acs_infor表示附属信息；（2）计算范围LCP，如6～7行所示，plen表示LCP的前缀长度；（3）训练B loom filter，如8～18行所示，其中8～11行是更新单元中BF计数器的学习过程，根据前缀长度plen找到对应的BF计数器，对LCP进行K次哈希计算，Hash_j表示BF计数器的第j个哈希函数，将哈希映射的位置加1；12～18行是BFPP单元B loom filter的配置过程，对应BF计数器不为0的位被置1，m为Bloom filter数组的位宽；（4）配置TCAM和RAM，如19～20行所示，根据前缀长度（p len）找到相应TCAM块存入LCP值，范围的特征区间saddr［w-plen-2:0］，eaddr［w-plen-2:0］和附属信息（acs_infor）存入RAM相应位置。3，4阶段可并行运行。

表1　配置算法流程

查找算法（BF-TCAM Lookup A lgorithm）流程如表2所示。

首先通过B loom filter过滤关键字任意长度前缀，如果没有前缀匹配，判定关键字无效。若通过过滤，然后在匹配的TCAM块区域中查找相应长度前缀，将匹配表项的位置作为地址索引RAM，最后由比较器判断关键字是否位于特征区间，如果匹配成功，输出附属信息，否则判定关键字无效。整个查找算法分为两个阶段：（1）前缀预处理，如1～19行所示，其中1～15行完成B loom filter运算，分别对关键字各个长度的前缀进行哈希计算和判断，将命中的前缀子集标记在匹配向量（match_vector）中，这个阶段如果没有发现匹配前缀即匹配向量为0可判断关键字无效，如16～19行所示；（2）在命中的TCAM_RAM中查找关键字，如20～34行所示，TCAM若存在匹配表项，以其位置作为地址（ram_ addr）索引RAM，比较器判断关键字偏移量是否位于特征区间，若存在匹配的特征区间，将对应的附属信息输出，完成范围匹配，否则判定关键字无效。

BF-TCAM支持增量更新，包括插入和删除操作。插入算法与配置算法的2，3，4阶段相同，完成BF训练和TCAM_RAM表项的插入。删除与插入算法相似，BF训练阶段对BF计数器进行减1操作，如果某位归零，则相应更新BFPP中的B loom filter，同时删除TCAM_RAM中的表项。各个长度的前缀子集分区存放，支持随机插入与删除，无需移动无关表项，因而BF-TCAM模型能够高效完成更新操作。

4　性能分析

表3为不同算法的关键性能指标对比，其中F为范围匹配包含的字段个数，对于报文分类来说为2，包括源端口和目的端口，W为范围字段位宽，DTRM算法将W位宽的范围字段划分为M个较短的比特串编码，N为表项数目。DTRM，SRGE和C-TCAM最坏情况下都会造成严重范围扩张，以报文分类中的端口查询为例，DTRM造成2（2 4 1）×-倍扩张，倍扩张。DTRM和C-TCAM平均扩张因子优化到了较理想的水平，但每条表项需要额外使用2W个比特。范围扩张直接引发了高昂的更新代价，增加或删除一个范围需要对多条表项进行操作，同时加重了TCAM功耗。BF-TCAM通过SMLCP算法实现了高效的范围匹配转化，不增加任何冗余信息，扩张因子达到1.0，使TCAM空间利用率达到100%。SMLCP算法将范围匹配拆分为两个步骤，较其它算法增加了一个比较过程，为不降低查找速度，使用流水线缩小关键路径长度，但不可避免地增加了电路资源消耗，由此可见SMLCP的高效存储是以牺牲一定电路资源为代价的。TCAM功耗与参与并行比较的表项数目成正相关，BF-TCAM引入分类存储思想，仅通过B loom filter过滤的子集参与比较，能够大大降低TCAM功耗，极端恶劣情况下所有子集同时参与比较，此时功耗达到峰值。BF-TCAM支持增量更新，实现了表项的随机插入与删除，较其它算法大幅提高了更新性能。查找操作一个时钟周期即可完成，特殊情况下流水线停顿造成一个时钟周期延时，但目前TCAM时钟频率已达500 MHz以上，意味着查找操作可在4 ns内完成，能够满足性能需求。

表2　查找算法流程

以多处理器片上系统［12］（Mu lti-Processor System-on-Chips，MPSoC）的存储保护为背景评估BF_TCAM的实际功耗：MPSoC上可并行运行多个任务，每个任务分配有独享的内存区域，对共享数据存储区有特定的访问权限，引入BF-TCAM监控任务的访存地址可以实现对存储资源的访问控制，进而保护系统不受非法入侵。实验中并行执行4个应用，共有551条规则表项，通过监测TCAM_ RAM的片选信号即匹配向量可以计算实时参与比较的表项数目，进而评估实时功耗。如图3所示，每个应用采集2000次访存操作，统计每次访存参与比较的表项数目，图中横轴表示访存次序，纵轴表示实时参与比较的表项数目，可以发现应用1平均每次访存有181.4条表项参与比较，占总规则数目的32.9%；应用2为232.9条，占42.3%；应用3为213.9条，占38.8%；应用4为253.5条，占46.0%。BF-TCAM使用Bloom filter过滤无关项参与比较，将实际参与比较的规则数目大幅减少，实验表明，BF-TCAM较传统TCAM实际功耗降低50%以上。

表3　不同算法的关键性能指标对比

图3　不同应用下BF_TCAM的实际功耗水平

5　总结

目前基于TCAM的范围匹配方案通过扩展规则集方式表达范围，存储空间利用率低，尤其对于报文分类中的端口匹配，范围扩张因子达数百倍，同时大幅提高了工作功耗和更新代价。针对这个问题，本文提出了基于BF-TCAM的高效范围匹配方法，利用范围区间两端点二进制编码最长共同前缀的唯一性设计了SMLCP算法，将范围匹配过程分解为前缀匹配和特征区间比对两个步骤，从而便于应用TCAM技术，使TCAM空间利用率达到100%。进而设计BF-TCAM模型，按前缀长度对范围进行分类处理，支持增量更新，提高了更新性能。使用B loom filter对关键字过滤，屏蔽无关项参与比较，从而大幅降低功耗。使用流水线技术缩短电路关键路径长度，使查找操作在一个时钟周期内完成。BF-TCAM模型在保持高速查找性能的同时，使用B loom filter过滤无关项，大幅减少参与比较的规则数目，实际功耗较传统TCAM降低50%以上。

［1］董永吉，郭云飞，黄万伟，等.一种新的高速报文解析结构研究［J］.电子与信息学报，2013，35（5）:1083-1089.

DONG Yongji，GUO Yunfei，HUANG W anwei，et al.A new high-speed packet parsing architecture［J］.Journal of Electronics&Information Technology，2013，35（5）: 1083-1089.

［2］李智涛，徐雅静，刘利宏，等.一种新的IPv6网络带宽测量方法［J］.电子与信息学报，2008，30（9）:2283-2286.

LI Zh itao，XU Yajing，LIU Lihong，et al.An approach to available bandw idth m easurem ent in IPv6 networks［J］. JournalofElectronics&Information Technology，2008，30（9）: 2283-2286.

［3］Grammatikakis M D，Papadim itriou K，Petrakis P，et al. Security effectiveness and a hardware firewall for MPSoCs［C］. IEEE High Perform ance Com puting and Comm un ications，Paris，2014:1032-1039.

［4］Grammatikakis M，Papadim itriou K，Petrakis P，et al. Security in MPSoCs:a NoC firewall and an evaluation framework［J］.IEEE Transactions on Computer-Aided Design of In tegrated Circuits and System s，2015，34（8）:1344-1357.

［5］田乐.面向存储和功耗优化的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.

［6］朱国胜，余少华.基于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 Comm unications，2012，33（1）:31-37.

［7］BREMLERR-BARR A and HENDLER D.Space-efficient TCAM-based classification using gray coding［J］.IEEE Transactions on Computers，2012，61（1）:18-30.

［8］RAY S S and BHATTACHARYA A.A fast rangematching architecture w ith un it storage expansion ratio and h igh m em ory utilization using SBiCAM for packet classification［C］. IEEE India Conference，Pune，2014:1-6.

［9］侯颖，郭云飞，黄海，等.基于同源组合布鲁姆过滤器的早期流量抽样算法［J］.通信学报，2014，35（10）:117-126.

HOU Ying，GUO Yunfei，HUANG Hai，et al.Early traffic sam p ling algorithm based on SSCBF［J］.Journal on Communications，2014，35（10）:117-126.

［10］侯颖，黄海，兰巨龙，等.基于自适应超时计数布鲁姆过滤器的流量测量算法［J］.电子与信息学报，2015，37（4）:887-894. doi:10.11999/JEIT 140820.

HOU Ying，HUANG Hai，LAN Ju long，et al.An adap tive tim eou t counter b loom filter a lgorithm for tra ffic measurement［J］.Journal of Electronics&Information Technology，2015，37（4）:887-894.doi:10.11999/JEIT 140820.

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

ZHANG Sh igeng，LIU Guangliang，LIU Xuan，et al.An energy-efficient and fast m issing tag detection algorithm in large scale RFID system s［J］.Chines Journal of Computers，2014，37（2）:434-444.

［12］王一拙，左琦，计卫星，等.访存与用户行为敏感的MPSoC应用映射［J］.电子学报，2015，43（4）:631-638.

WANG Yizhuo，ZUO Qi，JIWeixing，et al.Memory-aware and user-awaremapping of applications to MPSoCS［J］.Acta Electronica Sinica，2015，43（4）:631-638.

戴紫彬：男，1966年生，博士，教授，研究方向为安全专用芯片设计.

刘航天：男，1991年生，硕士生，研究方向为安全SoC设计与验证.

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

DAIZibin LIU Hangtian
（Cryptography Engeering College，Information Engeering University，Zhengzhou 450004，China）

An efficient rangematchingmethod based on Bloom Filter algorithm and Ternary Content Add ressab le 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 rangematchingmethods.An algorithm of Segmented Match on Longest Common Prefix（SM LCP）sp lits range m atching into two steps prefix m atching and featu re range comparation，resulting in 100%TCAM space using ratio.BF-TCAM is designed according to SM LCP algorithm，which filters searching key wordsby Bloom filter to avoid that unrelated item s participate in comparation，so as to reduce greatly power dissipation.Critical paths are stream lined so that searching operation can be comp leted during one clock cycle.Research resu lts demonstrate that BF-TCAM achieves zero range expansion，meanwhile power dissipation fallsmore than 50%.

Range m atching；B loom Filter（BF）；Ternary Content Addressab le M em ory（TCAM）；Zero range expansion；Low power dissipation

TP393.08

A

1009-5896（2016）08-1872-08

10.11999/JEIT 151264

2015-11-10；改回日期：2016-03-21；网络出版：2016-05-09

刘航天13703928360@163.com