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

TaylorA

摘 要：该文基于布鲁姆过滤器算法和三态内容寻址存储器(Ternary Content Addressable Memory, TCAM)技术
提出一种高效范围匹配方法，解决了目前 TCAM 范围匹配方案存在的存储利用率低、功耗大的问题。设计基于最
长共同前缀的分段匹配算法(Segmented Match on Longest Common Prefix, SMLCP)将范围匹配拆分为前缀匹配
$ v1 {$ w8 Y3 C1 s5 A/ M  Y和特征区间比对两步，TCAM 空间利用率达到 100%。根据 SMLCP 算法设计了 BF-TCAM 模型，使用布鲁姆过
滤器对关键字过滤，屏蔽无关项参与比较，大幅降低功耗。使用流水线缩短关键路径长度，使查找操作在一个时钟
, t5 S2 H+ T+ R: d- X3 U周期内完成。研究结果表明，所提方法实现了零范围扩张，工作功耗较传统 TCAM 降低 50%以上。
关键词：范围匹配；布鲁姆过滤器；三态内容寻址存储器；零范围扩张；低功耗
4 `+ E( ]& v4 i, y1 引言
: \8 a1 @3 q- [5 E% d+ R3 M范围匹配广泛应用于网络 3 到 4 层的报文分类，
根据源端口和目的端口字段匹配端口范围，实现访
) ]- ]4 \  S2 [. a问控制、安全过滤、带宽控制等功能[1,2]。在存储保
8 u% M4 B* ~# s: W; C1 y护方面也有较多应用，比如审查进程发起的访存操
作地址是否匹配其权限内的存储空间实现安全访问
' t( I5 q( ~4 `* s# b控制[3,4]。这些实时应用对查找性能要求很高，高速
的范围匹配是实现实时应用的技术支撑。
目前业界普遍使用三态内容寻址存储器
) \, v' _0 m" M+ g6 i/ Q( y3 @* R(Ternary Content Addressable Memory, TCAM)实
- I+ N1 G9 m2 x' k5 Z1 l现高速查找表。TCAM 突出的问题在于它不适用于
范围匹配，只能实现精确匹配和前缀匹配。比如

) @+ r4 }4 F% C* Q  ^
5 H' y3 R6 P& s  R) n, B+ K

: m$ z4 X- B4 `附件下载：

游客，如果您要查看本帖隐藏内容请回复

; M: l9 z/ d6 _8 d' W* J8 M

vava

谢谢分享