一种用TCAM实现关键字快速查找并读表的方法

摘要

本发明揭示了一种用TCAM实现关键字快速查找的方法，在TCAM对关键字进行查找时，根据关键字的种类和比特，将关键字放在一个TCAM上或多个TCAM上，并在TCAM和SRAM间通过配置寄存器形成映射关系，使得从TCAM中查找得到的地址通过所述寄存器的逻辑控制分配到任意一个SRAM上，实现关键字在TCAM上的并行查找和SRAM中数据的并行读取。本发明充分利用了TCAM和SRAM资源，使得同一个TCAM上可以同时放置不同比特位宽不同类型的关键字，关键字和相对应的表项在TCAM和SRAM中能够灵活配置，提高了交换机芯片查表的效率，在保证通用查表性能的情况下降低了芯片的面积和功耗。

说明书

技术领域

本发明涉及计算机网络技术，尤其涉及在以太网交换机芯片中采用 TCAM实现对不同种类不同比特关键字(Key)进行快速查找的方法。

背景技术

在以太网交换机芯片中，会经常涉及到快速查找ACL(Access Control  List，访问控制列表)，路由表等功能，这时候查找效率将会影响到芯片的 性能。TCAM(Ternary Content Addressable Memory，三态内容寻址存储器) 具有快速并行查找，访问方式简单的特点，非常适合这种场合。然而TCAM 同时又具有成本高，功耗大的缺点，制约了其在芯片中的大量使用。查表 结束后，通常需要根据TCAM查回来的地址，读取此地址对应的SRAM中 的表项。交换机芯片中涉及到的表项越来越多，需要查TCAM的Key的位 宽变得越来越大，如何再用尽量少的TCAM和SRAM来做尽量多的查表， 直接决定了芯片的成本和性能。

在ACL查找时，关键字的长度会有80/160/320/640等多种位宽，同时， 同一个key可能查1次或多次。查1次得到1个地址，查多次将同时得到 多个地址。之后根据地址，会去读相应的SRAM表项，这时候要读1次或 多次SRAM表项。除了ACL，芯片还会做路由等查找。上述各种情况的混 合，增加了TCAM使用的复杂度。现有的做法是将ACL和其他查表根据 表的类型和关键字的大小放在不同位宽的TCAM中，然后根据查找回来的 地址，串行去访问SRAM。

这种方法需要的TCAM数量比较多，同时要求有不同位宽。如果某一 种或某一种大小关键字的查找表没有使用完当前的TCAM，将产生浪费。 而且会导致存放表象的SRAM的浪费。如果ACL查找多次，得到多个索 引(index)串行访问SRAM，这样对SRAM中数据的读取将成为瓶颈，影 响了芯片的整体性能。

发明内容

本发明目的在于通过灵活的TCAM映射方法，将不同比特和不同种类 的Key映射到同一块TCAM上，用有限的TCAM资源实现尽可能多的不 同类型的查找。查表回来的地址会去读数据存储器。通过灵活的SRAM映 射关系，能在一个时钟周期内，把多个地址的数据同时读出并发送出去。 这种方法能用最少的TCAM资源，实现以太网交换芯片中一个包尽可能多 的查找和读表次数；这里的TCAM和SRAM映射关系都可以通过配置寄存 器来灵活设置，支持尽可能多的应用场合。

为实现上述目的，本发明提出如下技术方案：一种用TCAM实现关键 字快速查找并读表的方法，在TCAM进行关键字的查找时，根据关键字的 种类和比特，将关键字放在一个TCAM上或多个TCAM上，并在TCAM 和SRAM间通过配置寄存器形成映射关系，使得从TCAM中查找得到的地 址通过所述寄存器的逻辑控制分配到任意一个SRAM上，实现关键字在 TCAM上的并行查找和SRAM中数据的并行读取。

更进一步地，所述关键字的种类为选自访问控制列表和路由表中的一 种或两种。

不同种类和不同比特的关键字放置到同一个TCAM上进行查找。

所述TCAM支持对关键字进行多次并行查找。

当关键字是访问控制列表且多次查找时，根据从TCAM中查到的相应 地址配置TCAM寄存器，并由TCAM寄存器将不同TCAM上得到的地址 映射到不同的访问控制列表的地址上。

从TCAM中查到的地址根据关键字对应的表项基址配置SRAM寄存器 并得到最终的地址，所述最终地址根据SRAM映射寄存器的映射到不同的 SRAM上。

所述映射关系是将TCAM中的关键字与该关键字在SRAM中对应的数 据间的对应关系。

查找的关键字在TCAM中的分配方式为：与TCAM位宽相同的关键 字将发送到每一个TCAM进行并行查找，而大于TCAM位宽的关键字会 将高位的发送到偶数的TCAM(TCAM#2N)中，低位的发送到与所述偶 数紧接着下来的奇数TCAM(TCAM#2N+1)。

与现有技术相比，本发明能充分利用TCAM和SRAM资源，使得同一 个TCAM上能够同时放置不同比特位宽不同类型的关键字，关键字和相对 应的表项在TCAM和SRAM灵活配置。同时能支持一个关键字并行查找多 个地址，而且能并行读取SRAM数据。提高了交换机芯片查表的效率，在 保证通用查表性能的情况下降低了芯片的面积和功耗。

附图说明

图1为本发明TCAM和SCAM映射举例示意图；

图2为本发明TCAM和SCAM 80位宽映射关系示意图；

图3为本发明TCAM和SCAM 160位宽映射关系示意图；

图4为本发明TCAM和SRAM映射实现结构示意图。

具体实施方式

下面将结合本发明的附图，对本发明优选实施例中的技术方案进行清 楚、完整的描述。

本发明用TCAM实现关键字快速查找并读表的方法，通过TCAM配 置寄存器的配置，采用对不同种类和不同比特位宽的关键字(Key)在TCAM 上灵活动态地分配，能将不同的(或相同的)关键字放在不同TCAM上， 同时也能将不同的关键字放在同一个TCAM上。

图1所示为本发明使用配置寄存器进行映射的实施例，图中TCAM中 放的是关键字0～8，SRAM中为相应编号关键字对应的数据0～8。其中关键 字3是160bits，放在两个TCAM中，即TCAM#0及TCAM#1中。

根据图1，放在同一个TCAM中的关键字1和2，其数据可以被映射 到两个SRAM3和4中。而放在不同TCAM中的关键字4和6，其数据也 可以映射到同一个SRAM1中。如果要进行1个ACL关键字5的3次并行 查找，可以将关键字5放在3个不同的TCAM上，其对应的3个数据也放 在3个SRAM上，这样并能实现并行查找，并行读表。相应的将3个数据 放在同一个SRAM上，就是并行查找，串行读表。

图2所示为本发明实施例中的TCAM和SRAM关键字80位宽的映射 关系示意图，箭头表示一对一的映射关系。其中图中的TCAM位宽都是 80bits，因此，位宽为80的关键字将占有一个TCAM，1个关键字可以放 在任意一个TCAM中。这个关键字对应的数据也可以放在任意一个SRAM 中。

如图3所示为TCAM和SRAM关键字160位宽的映射关系示意图， 实线箭头为160:80(高位)映射关系，虚线箭头为79:0(低位)映射关系。 因此，位宽为160的关键字将占有两个相邻的TCAM。同理，位宽为320 的关键字将同时占用相邻的四个TCAM(或者当四个TCAM中剩余的位宽 不够时，将占用更多的TCAM)。

而通过TCAM查找得到的地址，可以根据配置寄存器，分配到任意一 个SRAM上。这样当一个关键字实现多次ACL查找的时候，得到的多个 地址可以并行读取SRAM数据。这样可以灵活地实现各种表象在TCAM和 SRAM中的配置。

如图4所示为本发明实施例中一种较佳的关键字在TCAM中的放置方 式，待查找的关键字通过key发送控制器后，将对关键字的种类和比特进 行识别，并将识别判断后的这些关键字发送至同一个或不同的TCAM中， 具体的分配方式为：当TCAM收到一个关键字时(其中以TCAM位宽都 是80bits为例)，根据关键字的比特位宽，80的关键字会发送到每一个 TCAM进行并行查找，而160的关键字会将159:80(高位的)发送TCAM#2N (偶数的TCAM中)，79:0(低位的)发送到TCAM#2N+1(奇数的TCAM 中)以简化查找逻辑，并同时并行查找。320和640的关键字以此类推。

TCAM查找结束后会返回地址，这时根据每个TCAM的位宽配置寄存 器来决定当前查找是否成功。如果配的是80bits，那么将从每一个TCAM 查找得到的地址中，根据网络中查表的最小前缀匹配原则，挑选出最小的。

如果是160bits，需要同时匹配关键字的159:80(高位的)和79:0(低 位的)。根前面两节中所述的160关键字发送原则，那么只有TCAM#2N和 TCAM#2N+1同时都有查找到才代表查找成功，这时候查找的地址是 TCAM#2N的地址。以此类推320bits的地址为TCAM#4N的地址，而640bits 的地址为TCAM#8N的地址。

如果这个关键字是ACL，当只查一次ACL的时候，得到地址方法同 上。如果要查多次ACL，将得到多个地址。这时候根据各个TCAM及ACL 配置寄存器，将不同TCAM上得到的地址映射到不同的ACL地址上。

得到TCAM查找地址后，然后根据不同关键字类型对应的表项基址配 置寄存器，得到最终的地址。再根据SRAM映射寄存器的逻辑控制，将最 终地址映射到不同的SRAM上。这样就可以从这块SRAM上读到想要的数 据后发送出去，从而实现TCAM的对不同种类不同比特的关键字的并行查 找，以及对查找到的SRAM中的数据的并行读取。

本发明的技术内容及技术特征已揭示如上，然而熟悉本领域的技术人 员仍可能基于本发明的教示及揭示而作种种不背离本发明精神的替换及修 饰，因此，本发明保护范围应不限于实施例所揭示的内容，而应包括各种 不背离本发明的替换及修饰，并为本专利申请权利要求所涵盖。