基于三态位分割的低功耗TCAM报文分类算法

tcam原理TCAM（Ternary Content-Addressable Memory）是一种高性能的存储器，具有快速的查找和匹配功能。

它可以在给定的时间内并行搜索多个存储单元，并返回匹配结果。

TCAM的原理可以通过以下几个方面来说明。

TCAM是一种内容寻址存储器，即根据数据内容来寻址存储单元。

与传统的RAM（Random Access Memory）不同，RAM是通过地址来寻址存储单元。

TCAM中的每个存储单元都有一个对应的比特串，称为标签。

当输入数据与某个存储单元的标签完全匹配时，该存储单元会被激活，输出相应的数据。

TCAM中的存储单元通常由三个状态表示：0、1和X（表示无关）。

这种三态逻辑使得TCAM可以进行三值逻辑的比较。

与传统的存储器不同，传统存储器只能进行二值比较，即0和1的比较。

而TCAM可以进行三值比较，即0、1和X的比较。

这使得TCAM在网络路由、防火墙等应用中具有更强大的匹配能力。

TCAM的查找过程是并行进行的，因此具有非常高的查找速度。

在传统的存储器中，查找操作需要逐个比较每个存储单元，直到找到匹配的数据为止。

而在TCAM中，所有存储单元都可以同时进行比较，只需要一个时钟周期即可完成查找操作。

这使得TCAM在高速网络设备中能够满足实时的数据处理需求。

TCAM还具有可编程的特性。

用户可以根据需要编程设置存储单元的标签和数据。

这使得TCAM能够适应不同的应用场景，提供灵活的匹配功能。

例如，在路由器中，可以根据IP地址、子网掩码等信息来编程设置TCAM的标签，从而实现高效的IP地址匹配。

然而，TCAM也存在一些局限性。

首先，由于TCAM的存储单元是并行比较的，因此其面积和功耗相对较大。

这使得TCAM在一些功耗敏感的应用中不太适用。

其次，由于TCAM的存储单元是固定的，因此其容量有限。

在一些大规模的应用中，可能需要多个TCAM进行级联扩展，增加系统的成本和复杂性。

TCAM是一种基于内容寻址的高性能存储器，具有快速的查找和匹配功能。

利用域转换的三态内容寻址存储器报文分类算法田乐;陈庶樵;黄慧群;马腾【摘要】针对基于三态内容寻址存储器(TCAM)的报文分类存在范围扩张导致空间利用率较低的问题,提出了一种利用域转换的报文分类算法(DTRM).首先将规则集独立的范围预编码算法中范围规则编码所需的比特数量由2k-1替换为任意值,从而能够利用TCAM中的所有冗余位进行编码,实现新范围域的构建,然后利用范围规则的分布特征,以规则集能够表示为较少的TCAM表项为原则,设计域转换函数,将规则集原始范围域转换为新构建的范围域.报文分类时,利用域转换函数将报文头部转换为新构建范围域中的某一数值或范围,并与TCAM表项进行并行比较,最终得到分类结果.仿真结果表明,与并行报文分类算法相比,DTRM算法的范围扩张因子由1.6减少至1.21,TCAM空间利用率由63％增加至82％,同时支持规则的增量更新.【期刊名称】《西安交通大学学报》【年(卷),期】2013(047)010【总页数】6页(P97-102)【关键词】报文分类;三态内容寻址存储器;范围扩张;冗余位;域转换【作者】田乐;陈庶樵;黄慧群;马腾【作者单位】国家数字交换系统工程技术研究中心,450002,郑州;国家数字交换系统工程技术研究中心,450002,郑州;国家数字交换系统工程技术研究中心,450002,郑州;国家数字交换系统工程技术研究中心,450002,郑州【正文语种】中文【中图分类】TN914.42网络服务的日益多样化和不断增加的网络安全需求，要求网络设备能够提供新的处理机制，如基于策略的路由、流量测量、资源预留、拥塞控制、负载均衡等，这些技术的实现都离不开对网络数据报文快速、准确地分类［1］。

三态内容寻址存储器（ternary content－addressable memory，TCAM）是一种基于内容查找的存储器［2－3］，具有查询速度快、匹配时间固定等优点，目前广泛应用于报文分类领域。

CAM是Content Addressable Memory的缩写，即“内容寻址存储器”的意思，它是在传统的存储技术的基础上实现的联想记忆存储器，关于CAM的基本操作有三种：1).写操作：输入地址和数据，将数据写到指定的地址上，写入速度与RAM相同；2).读操作：输入地址，返回该地址上的数据，读取速度与RAM相同；3).查找操作：输入待查数据，返回该数据被存储的地址。

这也是CAM的最主要用途，它能够从巨大的数据库中进行快速查找，并且返回最佳的匹配地址，最快查找速度能达到每秒一亿次以上。

TCAM是Ternary Content Addressable Memory的缩写，即“三态内容寻址存储器”的意思，它是从CAM的基础上发展而来的。

一般的CAM存储器中每个bit位的状态只有两个，“0”或“1”，而TCAM中每个bit位有三种状态，除掉“0”和“1”外，还有一个“don’t care”状态，所以称为“三态”，它是通过掩码来实现的，正是TCAM的这个第三种状态特征使其既能进行精确匹配查找，又能进行模糊匹配查找，而CAM没有第三种状态，所以只能进行精确匹配查找。

TCAM器件的生产厂商主要有Cypress、IDT和Netlogic三家。

这三家分别将TCAM器件称作Network Search Engine(NSE)、Network Search Accelerator(NSA)和Knowledge-based Processor(KBP)。

TCAM器件在通信领域种有非常广泛的应用，主要有：1).ATM Switching设备中的VCI/VPI转发和ATM-to-MPLS or ATM-to-TCP-Flow地址映射表项的存储和查找；2).Ethernet Switching设备中的二层MAC地址、ARP/RARP解析和三层IP路由表项的存储和查找；3).Emerging Protocols and functions方面的MPLS label表项的存储和查找；4).Packet Classification业务中的Enforce security、Enforce departmental policies和QOS检测表项的存储和查找；5).安全防护设备中的FIB/LBT、MFIB及ACL表项存储和查找。

CAM是Content Addressable Memory的缩写，即“内容寻址存储器”的意思，它是在传统的存储技术的基础上实现的联想记忆存储器，关于CAM的基本操作有三种：1).写操作：输入地址和数据，将数据写到指定的地址上，写入速度与RAM 相同；2).读操作：输入地址，返回该地址上的数据，读取速度与RAM相同；3).查找操作：输入待查数据，返回该数据被存储的地址。

这也是CAM的最主要用途，它能够从巨大的数据库中进行快速查找，并且返回最佳的匹配地址，最快查找速度能达到每秒一亿次以上。

TCAM是Ternary Content Addressable Memory的缩写，即“三态内容寻址存储器”的意思，它是从CAM的基础上发展而来的。

一般的CAM存储器中每个bit位的状态只有两个，“0”或“1”，而TCAM中每个bit位有三种状态，除掉“0”和“1”外，还有一个“don’t care”状态，所以称为“三态”，它是通过掩码来实现的，正是TCAM的这个第三种状态特征使其既能进行精确匹配查找，又能进行模糊匹配查找，而CAM没有第三种状态，所以只能进行精确匹配查找。

TCAM器件的生产厂商主要有Cypress、IDT和Netlogic三家。

这三家分别将TCAM器件称作Network Search Engine(NSE)、Network Search Accelerator(NSA)和Knowledge-based Processor(KBP)。

TCAM器件在通信领域种有非常广泛的应用，主要有：1).ATM Switching设备中的VCI/VPI转发和ATM-to-MPLS orATM-to-TCP-Flow地址映射表项的存储和查找；2).Ethernet Switching设备中的二层MAC地址、ARP/RARP解析和三层IP 路由表项的存储和查找；3).Emerging Protocols and functions方面的MPLS label表项的存储和查找；4).Packet Classification业务中的Enforce security、Enforce departmental policies和QOS检测表项的存储和查找；5).安全防护设备中的FIB/LBT、MFIB及ACL表项存储和查找。

文章编号:16711742(2011)01006105基于March 算法的三态内容寻址存储器的故障诊断及实现王莉1,黄洪1,刘海青2(1.西南交通大学信息科学与技术学院,四川成都610031;2.成都迈普通信有限公司路由产品开发部,四川成都610029)摘要:介绍了三态内容寻址存储器的硬件组成,分析了三态内容寻址存储器的工作原理,结合Mar ch 算法的理论设计了三态内容寻址存储器故障诊断的方法,并介绍了故障检测的流程,在VxWorks 的操作系统下以Tornado为开发平台实现了三态内容寻址存储器的故障诊断功能,最后给出了实验结果。

实际应用表明结果可靠性能高能满足用户的需求。

关键词:计算机应用技术;故障诊断;三态内容寻址存储器;内建自测中图分类号:TP399文献标识码:A 收稿日期1引言近年,随着信息网络知识与技术的不断发展和提高,越来越多的公司(例如:中国移动、中国电信、银行等)都使用网络办公,于是因特网和以太网等网络的使用量显著增加,因此很多运营商对于高速和高可靠性的数据处理性能的需求也日益增加。

三态内容寻址存储器(T ernary Content Addressable Memory,TCAM)作为数据传输过程中关键器件,能够实现数据目标等的快速查找,能很好地解决多业务中各种表项的高速查找问题。

为支持大量的路由信息,网络设备制造商往往会在路由器,三层交换机中扩展多个TCAM 器件,满足业务的需求。

由于TCAM 处于高频率被使用状态,避免不了会出现诸如读、写、查找功能出错的故障问题,导致网络阻塞,丢包现象,其故障排查与检测也就成了维修部门首先要考虑的问题。

传统情况下,维修部门对TCAM 故障检测是通过TCAM 厂家提供的专用检测仪并经人工观赏检测仪的指示灯判读T CAM 的故障状态,检测方式不仅提高了TCAM 的检测成本,而且也加大了维修人员的数量及工作量。

基于这种背景下,结合March 算法的理论和T CAM 的工作原理,设计了一种快速排查与检测TCAM 读、写、查找功能的一种方法,并给出了实验结果。

基于FPGA+TCAM架构的网络分流系统的设计与实现鲁佳琪;黄芝平;刘纯武;刘德胜;陈实【摘要】网络流量分类技术为网络服务提供有力保障,在网络行为分析和网络监管方面发挥重要作用.设计并实现了一种基于FPGA+TCAM架构的网络分流系统,接入高速网络信号,恢复数据流信息,并对其进行分流管理.解决了传统网络分流系统接入速率不高,分流效果差的问题.最后对系统平台进行了测试,测试结果表明,该系统具备在高速网络环境下数据流实时分流处理的能力.【期刊名称】《微型机与应用》【年(卷),期】2016(035)015【总页数】5页(P65-68,71)【关键词】网络流量;分流;三态内容可寻址寄存器;现场可编程门阵列【作者】鲁佳琪;黄芝平;刘纯武;刘德胜;陈实【作者单位】国防科学技术大学机电工程与自动化学院,湖南长沙410073;国防科学技术大学机电工程与自动化学院,湖南长沙410073;国防科学技术大学机电工程与自动化学院,湖南长沙410073;国防科学技术大学机电工程与自动化学院,湖南长沙410073;国防科学技术大学机电工程与自动化学院,湖南长沙410073【正文语种】中文【中图分类】TP393;TP302网络流量分类技术是指将混合有各种应用的流量，按其相关特性进行分类的技术。

网络流量分类一直是学术界和产业界关注的重点之一。

对学术界来说，网络流量分类是高性能网络协议和应用设计的基础；对运营商来说，网络流量分类是网络运营管理、网络发展规划、网络流量调度和高效能业务前瞻的依据[1] 。

因此，进行网络流量分类相关领域的研究具有重要的理论和现实意义。

但是，传统分流设备由于不能适应高速网络环境，导致处理效率和准确率不高。

传统设备的缺点一直制约着网络流量分类技术研究的发展。

因此，设计并实现高接入速率、高处理效率的分流系统迫在眉睫。

网络流量分类技术分为软件和硬件两种主要实现方式。

已有的软件算法包括：(1)键树结构的分类算法：包括分层树和扩展树两种结构。

CAM是Content Addressable Memory的缩写，即“内容寻址存储器”的意思，它是在传统的存储技术的基础上实现的联想记忆存储器，关于CAM的基本操作有三种：1).写操作：输入地址和数据，将数据写到指定的地址上，写入速度与RAM相同；2).读操作：输入地址，返回该地址上的数据，读取速度与RAM相同；3).查找操作：输入待查数据，返回该数据被存储的地址。

这也是CAM的最主要用途，它能够从巨大的数据库中进行快速查找，并且返回最佳的匹配地址，最快查找速度能达到每秒一亿次以上。

TCAM是Ternary Content Addressable Memory的缩写，即“三态内容寻址存储器”的意思，它是从CAM的基础上发展而来的。

一般的CAM存储器中每个bit位的状态只有两个，“0”或“1”，而TCAM中每个bit位有三种状态，除掉“0”和“1”外，还有一个“don’t care”状态，所以称为“三态”，它是通过掩码来实现的，正是TCAM的这个第三种状态特征使其既能进行精确匹配查找，又能进行模糊匹配查找，而CAM没有第三种状态，所以只能进行精确匹配查找。

TCAM器件的生产厂商主要有Cypress、IDT和Netlogic三家。

这三家分别将TCAM器件称作Network Search Engine(NSE)、Network Search Accelerator(NSA)和Knowledge-based Processor(KBP)。

TCAM器件在通信领域种有非常广泛的应用，主要有：1).ATM Switching设备中的VCI/VPI转发和ATM-to-MPLS or ATM-to-TCP-Flow地址映射表项的存储和查找；2).Ethernet Switching设备中的二层MAC地址、ARP/RARP解析和三层IP路由表项的存储和查找；3).Emerging Protocols and functions方面的MPLS label表项的存储和查找；4).Packet Classification业务中的Enforce security、Enforce departmental policies和QOS检测表项的存储和查找；5).安全防护设备中的FIB/LBT、MFIB及ACL表项存储和查找。

TCAM(Ternary content addressable memories): 三态内容寻址存储器，结构如下图。

图中，整个TCAM 由1010（TCAM building block）阵列组成；1010可细分为1020数据存储区域， 1025掩码区域（mask），1080有效位（Valid Bit），1015数据内容（内容可以为‘0’、‘1’、‘X’），1040比较逻辑（Comparison Logic）和1045 匹配线（Match line）.b6tcamlp_128x96x1_pbr : SILICON DESIGN SOLUTIONS 提供的TCAM IP，字数128，字长96位（包含160位数据位和160位的掩码位），包含5个冗余列（Redundancy column）。

B6TCAMLP的编码方式如下表Test Mode ：B6TCAMLP 内建BIST接口，IP有两种工作方式：由TMODE 脚区分，一般模式（TMODE = ‘0’）和BIST 测试模式（TMODE = ‘1’）.不同的工作方式IP内部逻辑不变。

只区分输入端Test sequence: 测试向量由BIST controller通过BIST接口送到TCAM，对每个TCAM单元（1010）进行测试。

读写数据内容、读写掩码、内容比较、。

//Silicon Design 将会提供BIST模块及SPEC， TCAM module更新为128×96, Due data 4/19/2010SD BITS controller notes:BIST 控制器流程图1.Storage Test存储测试采用March RAW 算法。

相对于March LR和March C，March RAW算法采用back to back read/write方式不仅可以检测到固定错，还能检测动态错误。

为了增强测试的健壮性，还对算法进行改进：同个地址，数据和掩码区写入相反的数据；相邻地址写入相反数据。