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

TaylorA

摘 要：该文基于布鲁姆过滤器算法和三态内容寻址存储器(Ternary Content Addressable Memory, TCAM)技术
提出一种高效范围匹配方法，解决了目前 TCAM 范围匹配方案存在的存储利用率低、功耗大的问题。设计基于最
长共同前缀的分段匹配算法(Segmented Match on Longest Common Prefix, SMLCP)将范围匹配拆分为前缀匹配
" e5 \3 p8 r# J! m和特征区间比对两步，TCAM 空间利用率达到 100%。根据 SMLCP 算法设计了 BF-TCAM 模型，使用布鲁姆过
滤器对关键字过滤，屏蔽无关项参与比较，大幅降低功耗。使用流水线缩短关键路径长度，使查找操作在一个时钟
( E1 u) m$ a% Q! b3 S. {, [. g周期内完成。研究结果表明，所提方法实现了零范围扩张，工作功耗较传统 TCAM 降低 50%以上。
1 O' r( w0 G( @0 S关键词：范围匹配；布鲁姆过滤器；三态内容寻址存储器；零范围扩张；低功耗
1 引言
范围匹配广泛应用于网络 3 到 4 层的报文分类，
- z) [2 I& p( ~( X. Z, Q! N% t根据源端口和目的端口字段匹配端口范围，实现访
" Q5 F7 H0 p$ h问控制、安全过滤、带宽控制等功能[1,2]。在存储保
- `* X' S0 [# W1 e. s护方面也有较多应用，比如审查进程发起的访存操
作地址是否匹配其权限内的存储空间实现安全访问
控制[3,4]。这些实时应用对查找性能要求很高，高速
的范围匹配是实现实时应用的技术支撑。
目前业界普遍使用三态内容寻址存储器
# H* p, m" b! o) [(Ternary Content Addressable Memory, TCAM)实
现高速查找表。TCAM 突出的问题在于它不适用于
范围匹配，只能实现精确匹配和前缀匹配。比如
. @: |& v1 l2 T! B( l
! q+ z$ ]5 H3 |& s. ~' y
6 r6 ?7 @4 L  `( A& W* K  u6 k

' }+ g) j) J' a附件下载：

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

7 `/ |: @3 U+ V" |/ }
& o' b: ?; Q$ a7 R- r% S2 c

vava

谢谢分享