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

TaylorA

摘 要：该文基于布鲁姆过滤器算法和三态内容寻址存储器(Ternary Content Addressable Memory, TCAM)技术
' Z! x$ V# }3 \  |& d) U, v提出一种高效范围匹配方法，解决了目前 TCAM 范围匹配方案存在的存储利用率低、功耗大的问题。设计基于最
长共同前缀的分段匹配算法(Segmented Match on Longest Common Prefix, SMLCP)将范围匹配拆分为前缀匹配
和特征区间比对两步，TCAM 空间利用率达到 100%。根据 SMLCP 算法设计了 BF-TCAM 模型，使用布鲁姆过
" D6 d; E" A: y- b4 W/ r滤器对关键字过滤，屏蔽无关项参与比较，大幅降低功耗。使用流水线缩短关键路径长度，使查找操作在一个时钟
/ F2 T$ K; m( }% f7 w$ ^周期内完成。研究结果表明，所提方法实现了零范围扩张，工作功耗较传统 TCAM 降低 50%以上。
8 k/ A9 ~" t0 S; @( L  O关键词：范围匹配；布鲁姆过滤器；三态内容寻址存储器；零范围扩张；低功耗
( }5 S- Y) [% Z4 x) l: c* y) ?2 z1 引言
1 K4 T5 Y6 Y3 Y范围匹配广泛应用于网络 3 到 4 层的报文分类，
根据源端口和目的端口字段匹配端口范围，实现访
% _& f2 s/ D, ]! u1 g5 h" [问控制、安全过滤、带宽控制等功能[1,2]。在存储保
/ E. P( W" X2 d9 U+ M- P$ f/ c6 {( b护方面也有较多应用，比如审查进程发起的访存操
1 ~. L3 X% q& Y) P6 d- p2 T作地址是否匹配其权限内的存储空间实现安全访问
, s1 V9 N7 u* g2 i" U控制[3,4]。这些实时应用对查找性能要求很高，高速
的范围匹配是实现实时应用的技术支撑。
' s* @* h# F: g目前业界普遍使用三态内容寻址存储器
- \6 u4 Z* ~1 I5 ^% a(Ternary Content Addressable Memory, TCAM)实
, G3 r5 q5 z4 r% R( B0 a; t( P现高速查找表。TCAM 突出的问题在于它不适用于
范围匹配，只能实现精确匹配和前缀匹配。比如



% O- ]- h% [( |+ x
附件下载：

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

! b8 h) P% f3 r$ ?# j2 [+ z+ i% d

vava

谢谢分享