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

TaylorA

摘 要：该文基于布鲁姆过滤器算法和三态内容寻址存储器(Ternary Content Addressable Memory, TCAM)技术
# T) [; w1 f/ v2 T7 {: m  y提出一种高效范围匹配方法，解决了目前 TCAM 范围匹配方案存在的存储利用率低、功耗大的问题。设计基于最
6 s# R9 X6 i% P8 ?- w4 w8 j: B  o; S0 d长共同前缀的分段匹配算法(Segmented Match on Longest Common Prefix, SMLCP)将范围匹配拆分为前缀匹配
和特征区间比对两步，TCAM 空间利用率达到 100%。根据 SMLCP 算法设计了 BF-TCAM 模型，使用布鲁姆过
" Y. S8 h+ A$ Y  o2 Z滤器对关键字过滤，屏蔽无关项参与比较，大幅降低功耗。使用流水线缩短关键路径长度，使查找操作在一个时钟
9 I* Y" o. R4 z周期内完成。研究结果表明，所提方法实现了零范围扩张，工作功耗较传统 TCAM 降低 50%以上。
关键词：范围匹配；布鲁姆过滤器；三态内容寻址存储器；零范围扩张；低功耗
1 引言
范围匹配广泛应用于网络 3 到 4 层的报文分类，
根据源端口和目的端口字段匹配端口范围，实现访
/ F  p  `, b0 m3 h/ p问控制、安全过滤、带宽控制等功能[1,2]。在存储保
护方面也有较多应用，比如审查进程发起的访存操
作地址是否匹配其权限内的存储空间实现安全访问
控制[3,4]。这些实时应用对查找性能要求很高，高速
2 ?8 G* I; F* @; B6 X/ l的范围匹配是实现实时应用的技术支撑。
目前业界普遍使用三态内容寻址存储器
: Z8 h( n2 C0 B2 C9 G(Ternary Content Addressable Memory, TCAM)实
! b( _5 E, z( U/ s' l7 p8 \+ W现高速查找表。TCAM 突出的问题在于它不适用于
; i; A1 {6 f+ G7 Q2 Y, P范围匹配，只能实现精确匹配和前缀匹配。比如
) ^; q  L2 X1 S6 G1 g3 G
  c( R) Z$ Y* O6 T
& C: t2 S# e* K6 L& N

附件下载：

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

# F+ Q  h8 T' }8 s8 i$ M
$ ^1 r: y( A" u2 `6 h& E/ H1 w

vava

谢谢分享