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

TaylorA

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


, _8 g' K: u% N! C  V

附件下载：

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

vava

谢谢分享