一种基于TCAM的有效包分类方法

基于三态内容可寻址内存(TCAM)的包分类方法不能有效解决区间膨胀的问题。为此,提出一种有效包分类方法。对包分类规则集中各个域的不同区间进行分组,利用Shadow Encoding方法对同一分组中的所有区间进行重新编码,依据重新编码的区间结果改写原始规则集。实验结果表明,该方法可以平均压缩75.90%的TCAM存储空间。     

基于TCAM的二级路由查找

功率消耗大是三态内容寻址存储器(TCAM)的主要缺点之一。根据TCAM的可配置特性,提出了基于TCAM的二级路由查找,大大降低了TCAM的功耗。给出了基于比特选择的二级路由查找方案并对其进行了性能分析。最后介绍了二级路由查找下的路由更新算法。     

ISCP-TCAM :一种低功耗高速路由查找引擎结构

提出一种高速、低功耗路由查找引擎结构ISCP TCAM(ImprovedStage ControlPipeline TernaryContentAddressableMemory),这种结构不但具有传统内容可寻址寄存器(TCAM)管理简单、 更新容易、查找快速等优点,而且功耗要比同等容量的TCAM小得多。同时为进一步评估其性能利 用ALTERA公司的逻辑可编程门阵列(FPGA)实现了这一结构。该结构在低功耗高速路由查找引擎 的设计中是一个较好的选择。     

基于TCAM的高效浮动关键词匹配算法

针对传统浮动关键词匹配算法功耗高和速率低的问题,提出一种基于三态内容寻址寄存器(TCAM)的高效匹配算法。该算法应用关键词分类数据结构,将关键词存储在不同的TCAM模块中,并只将疑似关键词送入TCAM中查找匹配,从而减少每次访问TCAM查找的表项数目,提高一个查询周期内待匹配报文的移动速度。仿真结果表明,与传统算法相比,该算法功耗较低、匹配速度较快。     

基于决策树映射的低功耗TCAM包分类方案

为了实现网络流的线速转发,高性能交换机普遍采用三态内容寻址存储器(TCAM)来构建其包分类引擎。针对TCAM功耗高的问题,近年来出现了许多低功耗索引方案,实现了TCAM存储块的选择性激活以降低功耗,但这些索引方案普遍采用自底向上的局部优化算法来构建,无法有效实现流表规则的均匀划分,严重影响了TCAM的存储效率及功耗降低效果。提出并实现了一种基于决策树映射的TCAM低功耗索引方案,在极大降低功耗的同时提升了TCAM的存储效率。利用规则普遍存在的小域特征,将原始规则集划分为若干个规则子集,然后针对各个子集的特征域,采用自顶向下的方式分别构建平衡决策树,最后通过对各个决策树进行贪心遍历,从而得到TCAM索引列表。实验表明,针对规模为十万条的规则集,算法在仅使用额外1.3%存储空间开销的同时实现了98.2%的功耗降低。     

基于TCAM的并行路由查找方案综述

基于三态内容寻址存储器TCAM(Ternary Content-Addressable Memory)的路由查找方案是目前高性能路由器进行路由查找时普遍使用的方案,但这种方案仍存在查找速度、功耗和更新效率方面的挑战。因此,学者们提出了各种并行TCAM的解决方案以提高查找速度、降低功耗和增强更新效率。归类总结目前的并行TCAM路由查找方案,剖析它们的优缺点,指出目前这些方案仍存在的不足,并探索相应的解决方案。     

基于TCAM的二级转发表管理方案

目前高性能路由器的查找方案采用基于三重内容可寻址存储器(TCAM)的硬件查找。路由查找的最长前缀匹配要求使得TCAM的表项更新复杂。该文针对当前转发表管理方案在带突发情况下的不足,提出一种基于TCAM二级转发表管理方案,并对该方案进行了计算机仿真研究,仿真结果表明该方案在突发的情况下仍能保证转发系统稳定工作。     

基于TCAM报文分类的范围编码方案

针对现有范围编码方案三态内容寻址存储器(TCAM)利用率不高及更新性能差问题,提出一种混合范围编码方案(Hybrid-RES),根据扩展系数和出现频率,采用纵向或横向扩展编码策略对范围字段进行编码。纵向扩展编码策略利用格雷码的对称映射特征设计一种格雷范围编码算法,对纵向扩展出TCAM表项数目较多的范围字段采用横向扩展编码策略。理论分析和实验结果表明,Hybrid-RES可以较大地提高TCAM利用率,同时获得较好的更新性能。     

基于三态内容寻址存储器的多模式匹配算法

传统模式匹配算法在高速环境下无法实现数据包的实时处理。为此,提出一种基于三态内容寻址存储器(TCAM)的快速多模式匹配算法,通过模式移位将长模式截取为若干个子串,第1级TCAM存储子串,第2级TCAM存储子串的序列编号。搜索模式时,第1级TCAM向后端输出命中表项的编号,第2级TCAM实现序列编号的匹配,从而获得长模式的匹配信息,并通过编号空间划分方法压缩表项数目以提高资源利用率。实验结果表明,该算法可以实现网络数据的高速匹配处理,与基于hash标识的移位存储算法相比,具有空间消耗少的优势。     

低功耗与非型TCAM的原理介绍与时序研究

基于TCAM(三元内容寻址存储器)的硬件路由查找支持最长前缀匹配,可保存任意长度的关键字表项,实现快速路由查找和分组转发.如何降低功耗和协调各组分间大量的时序关系成为TCAM发展的瓶颈.介绍了"与非"型TCAM的工作原理和组成电路,并提出"哑单元行"的新思想模拟实际充放电时间,从而解决时序控制问题.     

TCAMChecker: A Software Approach to the Error Detection and Correction of TCAM-Based Networking Systems

Ternary content addressable memories (TCAMs) are widely used in network devices carrying out the core operation of single-operation lookups. TCAMs are the core component of many networking devices such as routers, switches, firewalls and intrusion detection/prevention systems. Unfortunately, they are susceptible to errors caused by environmental factors such as radiation. TCAM errors may have significant impact on search results. In fact, only one error in a TCAM can cause 100 % of search keys to have wrong lookup results. Therefore, TCAM error detection and correction schemes are needed to enhance the reliability of TCAM-based systems. All prior solutions require hardware changes to TCAM circuitry and therefore are difficult to deploy. In this paper, we propose TCAMChecker, the first software-based solution for TCAM error detection and correction. Given a search key, TCAMChecker probabilistically decides to verify the lookup result. If TCAMChecker decides to verify the lookup result then it performs two parallel lookups for the given search key. If the lookup results do not match then at least one error is detected and is corrected by using a backup error-free memory. Note that the probability of lookup verification can be tuned for tradeoff between performance and reliability. A higher probability of lookup verification provides a more reliable TCAM system at the cost of performance. Our proposed TCAMChecker can be easily deployed on existing TCAM-based networking devices to improve the system reliability.     

一种基于分段式存储的组播路由查找方案

在高端路由器基于硬件的路由查找设计方案中,TCAM（Ternary Content Addressable Memory）因其性能优良而被普遍采用。但通常的TCAM路由查找方式因组播报文路由查找的特殊性,会导致更多的TCAM存储空间被占用以及查找功效的降低。又因其无法流水线操作,限制了组播报文路由查找速度,从而使得该方法将不再适用。提出一种基于分段式存储的解决方案,该方案支持流水线操作,能够实现线速查找组播报文,而且节约了存储空间从而提高了功效。该方案在863重大课题“大规模接入汇聚路由器（Access Convergence Router,ACR）”中得以验证。     

一种面向FPGA异构计算的高效能KV加速器

网络功能虚拟化等新兴应用的蓬勃发展对Key-Value查询的能效提出了更高要求。传统的解决方法要么采用基于软件Hash表,要么采用专用的三态内容可寻址存储器(TCAM)芯片进行加速。其中,软件方法实现成本低,但是在数据冲突较高时会导致查表性能急速下降;硬件TCAM方法具有优良的时间特性,但其价格昂贵、耗能巨大。目前,随着基于现场可编程门阵列FPGA的异构计算技术的高速发展,利用系统已经提供的FPGA资源对基于软件实现的Hash表结构进行加速成为一种性价比更佳的解决方案。探讨如何利用FPGA上的RAM资源来实现一种具有高扩展性和高能效比的TCAM逻辑。与传统的TCAM结构不同,提出的架构支持查表范围的动态缩放,从而可以有效减少查表功耗。为了验证方案的有效性,利用Virtex-7系列FPGA对本文方案进行实现和评估,并与软件查表的性能进行详细比较。实验表明,本文方案吞吐量可达到234 Mpps,查表延迟为25.56ns。相比软件的方法,吞吐量提高780倍,延迟降低240倍。     

一种保持OpenFlow功能完整性的TCAM流表压缩模型

随着OpenFlow协议版本的不断更新,其在数据平面上细粒度的控制能力得到了很大提升。然而,由于表项匹配域支持的任意通配符依赖TCAM进行匹配处理,随着OpenFlow匹配域支持字段的增加,设备中的TCAM存储空间面临很大压力。为此,提出一种减小TCAM中流表存储空间的数学模型FICO(A Function-Integral TCAM-saving Compression model for flow table of OpenFlow)。FICO首先根据匹配域不同字段间的关系,将字段之间的冗余分为三种。然后基于冗余提出三种预压缩算法,分别为域间字段合并、字段映射、域内字段压缩,最终组合为更小位宽的表项被送往TCAM中进行流匹配。通过仿真表明在保持OpenFlow功能完整性的前提下,较未压缩流表,FICO可以节省60%TCAM存储空间。并且随着流表规模的增大,压缩性能保持稳定。     

Power efficient packet classification using cascaded bloom filter and off-the-shelf ternary CAM for WDM networks

In wavelength division multiplexing (WDM) networks, tens or hundreds of wavelengths can be transmitted over a single fiber. As transmission line speed goes to 10 Gb/s and beyond, ternary CAM (TCAM) is usually employed for wire speed packet classification. To the best of authors’ knowledge, this is the first paper that addresses the impact of WDM transmission on the power consumption of packet classification. We show that as the number of wavelengths increases in the WDM networks, the power consumption of TCAMs can become the limiting factor for WDM network expansion. For example, the power consumption of IPv4 and IPv6 packet classification with merely 32 channels at 40 Gb/s can be as high as 700 and 1400 W, respectively, while technology wise it is feasible to transmit over 500 channels over a single fiber. Existing power efficient TCAM designs require special modification to TCAM cell structures, which makes the adoption of the technology difficult. This paper proposes a novel approach which cascades bloom filter with off-the-shelf TCAM to greatly reduce the power consumption of packet classification. In particular, the proposed solution takes advantage of the fact that bloom filters may give false positive alarms but never give false negative alarms. By eliminating majority of non-matching packets before passing the packets to the TCAM, the TCAM is only activated to exam packets with a high potential of matching in the filter set. The proposed scheme greatly reduces the activation frequency of the TCAM, thus achieving great power savings.