基于布鲁姆过滤器算法和三态内容寻址存储器的高效范围匹配方法
戴紫彬;刘航天
【摘 要】An efficient range matching method based on Bloom Filter algorithm and Ternary Content Addressable 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 range matching methods. An algorithm of Segmented Match on Longest Common Prefix (SMLCP) splits range matching into two stepsprefix matching and feature range comparation, resulting in 100% TCAM space using ratio. BF-TCAM is designed according to SMLCP algorithm, which filters searching key words by Bloom filter to avoid that unrelated items participate in comparation, so as to reduce greatly power dissipation. Critical paths are streamlined so that searching operation can be completed during one clock cycle. Research results demonstrate that BF-TCAM achieves zero range expansion, meanwhile power dissipation falls more than 50%.%该文基于布鲁姆过滤器算法和三态内容寻址存储器(Ternary Content Addressable Memory, TCAM)技术提出一种高效范围匹配方法，解决了目前TCAM范
围匹配方案存在的存储利用率低、功耗大的问题。设计基于最长共同前缀的分段匹配算法(Segmented Match on Longest Common Prefix, SMLCP)将范围匹配拆分为前缀匹配和特征区间比对两步，TCAM空间利用率达到100%。根据SMLCP算法设计了BF-TCAM模型，使用布鲁姆过滤器对关键字过滤，屏蔽无关项参与比较，大幅降低功耗。使用流水线缩短关键路径长度，使查操作在一个时钟周期内完成。研究结果表明，所提方法实现了零范围扩张，工作功耗较传统TCAM降低50%以上。
【期刊名称】《电子与信息学报》
【年(卷),期】2016(038)008
【总页数】8页(P1872-1879)
【关键词】范围匹配;布鲁姆过滤器;三态内容寻址存储器;零范围扩张;低功耗
【作 者】戴紫彬;刘航天
【作者单位】信息工程大学密码工程学院郑州 450004;信息工程大学密码工程学院郑州 450004
【正文语种】中 文
【中图分类】TP393.08
范围匹配广泛应用于网络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.1　问题描述
首先对范围匹配问题进行形式化描述，以准确无误地表达问题实质，为SMLCP算法提供理论基础。
S是一系列范围区间的集合，均为位于数轴上的整数。［si，ti］是一段连续整数的集合，，L是数值的上限，S内所有元素均为闭集且相互之间没有重叠。
范围匹配问题等价描述为：给定一整数x，在S中定位包含x的元素即］使如图1所示。同时S集支持元素的动态插入与删除。
下面给出算法涉及的几个名词解释：
（1）最长共同前缀（Longest Comm on Prefix，LCP）：范围是一系列连续整数，位于数
轴上的一段闭区间。最小的整数称为起点，最大的整数称为终点，构成范围的两个端点。起点与终点的二进制编码从第1个不同的比特位到最低位用*替代（*表示不关注），构成三态表示，这样的一个包含*的W位二进制编码称为范围的最长共同前缀（W为二进制编码位宽）。如8位范围［22:38］，起点22的二进制编码为0001_0110，终点38的二进制编码为0010_0110，则
（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可以唯一标识一段范围，即意P具有两个维度前缀值和前缀长度，前缀值相等且长度相同的两个范围必定完全重合。
定理1要从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不匹配的整数即可证明假设错误，从而得证。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。