一种提高三重内容可寻址存储器报文分类查找速度的方法

摘要

本发明公开了一种提高三重内容可寻址存储器报文分类查找速度的方法，适用于在网络设备上实现基于TCAM的访问控制列表ACL的匹配，其特征在于，使用空间换取时间的方法来提高TCAM报文分类查找的速度，具体可以通过缓存关键字技术、并行查找技术和/或逻辑分表技术来实现。采用本发明所述方法可以大大提高TCAM实现ACL/QoS的查找速度，满足在高速网络下实现报文分类多次查找的线速要求。本发明的方法简单、可靠、灵活、易实施。

说明书

技术领域

本发明涉及计算机网络技术领域，尤其涉及使用TCAM(Ternary ContentAddressable Memory，三重内容可寻址存储器)实现ACL/QoS(Access ControlList/Quality of Service，访问控制列表/服务质量)方面的技术，主要应用在路由器，交换机，防火墙，入侵检测系统等网络设备。

背景技术

现今的网络设备中，大多都需要实现ACL/QoS，现以ACL举例，传统的ACL由五元组构成：源IP地址，目的IP地址，源端口号，目的端口号，协议。一般的实现中，IP地址使用前缀匹配，协议使用精确匹配，而端口则使用范围匹配。目前实现ACL主要有两种途径，一种是使用软件实现，最典型的就是RFC(Recursive Flow Classification，递归流分类)算法；另一种就是使用硬件实现，最典型的就是TCAM。当然硬件实现肯定比软件快很多，尤其是在一些高速网络中，一般都使用硬件进行加速。

TCAM是一种专用三重内容可寻址存储器，可以进行快速大量并行搜索。搜索的时候，存储器中所有的条目同时与搜索关键字比较，搜索结果就是匹配项的物理地址。在进行条目匹配时，条目的每个位可以是0、1、x三种状态，如果是x，那么该位不参与比较，默认是成功，否则关键字和条目的相应位进行比较，如果相同则成功否则失败。在比较过程中，如果某位不匹配，那么该条目匹配失败；如果所有位都匹配，那么该条目匹配成功。TCAM的三态特性，使得它很适合做ACL/QoS规则匹配。

现今的网络设备中，支持的业务也越来越多，典型的有Port ACL(端口ACL)、uRPF(Unicast Reverse Path Forwarding，单播反向路径转发)，RouteMap(策略路由))，NAT(Network Address Translation，网络地址转换)，QoS(Quality of Service，服务质量)等，这些业务中都涉及到了ACL，所以一个数据包往往需要进行多次ACL查找，这样就对查找速度提出了很高的要求，尤其是在高速网络中。现以10G网络举例，在10G流量下，64字节的小包速率大约是16MPPS，而目前的TCAM在576bit下单次查找的最快速度是33.25MSPS，但是因为硬件设计因素，查找突发性以及其它影响，实际的最快速度只能达到25MSPS，这样只能完成一次ACL的线速查找，如果需要进行多次ACL查找，那么肯定是达不到线速的。另外对于网络处理器，一般都是通过LA-1接口与TCAM相连，LA-1是一种与QDR SRAM兼容的接口，目前在250MHZ下的峰值带宽为2GBPS，但是SRAM的正常性能大约为峰值的70％左右，即为1.4GBPS。这样在16MPPS下，每个数据包在线速下允许输入的字节个数为87个，当进行576bit查找时，需要输入的关键字长度为76个字节，按照这个数值，那么也只能满足一次ACL的线速查找。

申请号为200510011511、公开号为1674557的中国专利申请“基于TCAM的解决范围匹配的并行IP包分类器及方法”中使用了多片TCAM进行分流查找的技术来加速TCAM的查找，该方法理论上虽然很好，但是实现起来复杂，同时控制平面的更新复杂度以及TCAM的内容管理也非常复杂，对于实现一个简单稳定可靠的网络设备来说还是不太适用的。

发明内容

本发明所要解决的技术问题在于提供一种适用于网络设备的提高TCAM实现ACL/QoS查找速度的简单、可靠、灵活、易实施的方法。

为实现本发明的上述目的，本发明提供了一种提高TCAM报文分类查找速度的方法，适用于在网络设备上实现基于TCAM的访问控制列表ACL的匹配，其中，使用空间换取时间的方法来提高TCAM报文分类查找的速度，具体可以通过缓存关键字技术、并行查找技术和/或逻辑分表技术来实现。

其中，通过缓存关键字技术来提高TCAM报文分类查找的速度，具体通过缓存查找时输入的关键字来实现。

所述的方法，其中，所述缓存查找时输入的关键字的步骤进一步通过输入一特殊的查找命令实现或通过在网络处理器与TCAM装置之间设置一TCAM转换器来实现，其中在所述TCAM转换器内设置有用于缓存关键字的关键字缓存部件。

所述的方法，其中，所述TCAM转换器使用ASIC/FPGA(ApplicationSpecific Integrated Circuit/Field Programmable Gate Array，专用集成电路/现场可编程门阵列)来实现，其内设置有：

LA-1(Look Aside，旁视)接口，用于连接网络处理器；

context(线程)管理器，用于将来自网络处理器的命令和数据放入相应context的命令队列和数据队列中；

调度器，用于调度context中的命令队列及结果队列；

命令解析器，用于识别当前执行的命令并根据不同的命令进行相应的操作；

命令执行部件，用于将当前需要执行的命令转换城TCAM器件的命令格式；

ASIC/FPGA接口，用于与TCAM相连接，以把命令发送给TCAM执行；

结果获取部件，用于获取TCAM的执行结果并将其交给调度器。

所述的方法，其中，所述通过TCAM转换器实现关键字的缓存进一步包括：

步骤401，网络处理器发送的命令和数据到达context管理器；

步骤402，所述context管理器将命令和数据放入相应的命令队列和数据队列；

步骤403，调度器调度所述命令队列，并在执行命令时将命令信息传给命令解析器；

步骤404，命令解析器识别当前执行的命令，判断当命令信息为再搜索命令时，从关键字缓存器件中取出相应缓存的关键字，并根据所述缓存的关键字修改ACL号字段，再交由搜索命令部件执行；

步骤405，命令执行部件将要执行的命令转换成TCAM器件的命令格式，并通过ASIC/FPGA接口把命令发送给TCAM执行；

步骤406，TCAM执行完命令后，如返回执行结果，则结果获取部件获取所述执行结果并交由调度器处理；

步骤407，调度器将所述执行结果送入context的结果队列中供网络处理器获取。

所述的方法，其中，所述步骤404进一步包括判断当当前执行的命令不是再搜索命令时，进一步判断当前执行的命令是否为搜索命令；如是，则向命令执行部件发送命令执行请求，并更新关键字缓存器件中相应context的关键字的值；如否，则直接交由命令执行部件执行。

本发明进一步提供了并行查找技术来提高TCAM报文分类查找的速度，其中，具体通过使用多片TCAM并行查找来实现。

所述的方法，其中，所述并行查找的多片TCAM，每片存储的内容完全一样。

本发明进一步提供了逻辑分表技术来提高TCAM报文分类查找的速度，其中，具体通过将ACL表在逻辑上分成多个表，每个条目使用多个ACL号字段分别供多个ACL子表使用，查找时在关键字中设置多个不同的ACL号字段来实现一次查得多个结果。

所述的方法，其中，所述逻辑上分成的多个表存储的内容可以完全相同或完全不同。

上述三种技术都是采用空间换取时间的方法，它们可以单独使用，也可以任意组合使用，可以非常灵活的运用。

采用本发明的方法可以大大提高TCAM实现ACL/QoS的查找速度，满足在高速网络下实现报文分类多次查找的线速要求。本发明的方法实用性非常强，可供选择的方式也很多，灵活性也非常好。

附图说明

图1是减少多次查找关键字输入个数的示意图；

图2是一次查找多个ACL结果的TCAM条目格式；

图3是TCAM转换器参考实现原理图；

图4是多片TCAM分流原理图；

图5是一次查找多个ACL结果的原理图。

具体实施方式

下面结合附图对技术方案的实施作进一步的详细描述。

本发明的一实施例使用Key Capture(关键字捕捉)减少多次查找的关键字输入长度。图1是减少多次查找关键字输入个数的示意图。如图1，当一个数据包需要进行多次ACL查找时，除了ACL号外，其它字段都是一样的，所以可以采用一种Key Capture机制使得后面的查找只需要输入ACL号即可，而不需要每次查找都把全部的关键字都输入一遍。这是一种Cache(缓冲)技术。有些TCAM设备支持特殊的查找命令，命令的特点如下：把前一次查找命令使用的key进行部分替换然后进行查找，注意该命令的使用前提是前一次必须是查找命令，我们把这种功能称为Key Capture，它是一种cache技术。如果TCAM设备支持这种类似命令，那么就可以使用该命令实现该功能，如果不支持，那么可以使用一个TCAM转换器来实现，参见图3。

图3是TCAM转换器参考实现原理图。如图3所示，该器件可以使用ASIC/FPGA(Application Specific Integrated Circuit/Field Programmable GateArray，专用集成电路/现场可编程门阵列)来实现，其一端使用LA-1(LookAside，旁视)接口2连接网络处理器1，另一端使用与TCAM一样的专用ASIC/FPGA接口8来连接TCAM设备10。TCAM转换器11内部最主要有一个Key Cache部件(关键字缓存部件)9，该部件缓存每个context(线程)最后一次查找使用的关键字。因为网络处理器1使用的LA-1接口2带宽是很低的并且处理器都是支持多线程编程的，所以该器件内部有一个context管理器3，每个context表示一个访问者(也即线程)。当网络处理器1向TCAM转换器11发出查找命令时，命令和数据首先到达context管理器3，然后由其放入相应context的命令队列(CMD FIFO)12和数据队列(DAT FIFO)13里。这时调度器(Scheduler)4会对所有context中的命令队列进行调度，每调度执行一个命令就会把命令信息传给命令解析器(CMD Parser)5，该命令解析器会识别当前执行的是什么命令：如果是ReSearch(再搜索)命令14，那么就到Key Cache 9相应context中取出缓存的key(关键字)，然后修改高16/8位值(ACL号字段)再交由Search命令部件执行；如果是Search(搜索)命令15，那么该命令首先向命令执行部件(Execute CMD)7发送命令执行请求，然后立刻更新Key Cache中相应context的key值；如果是其它命令，那么直接交由命令执行部件7执行。命令执行部件7会把当前需要执行的命令转换成具体TCAM器件的命令格式，然后通过专门的ASIC/FPGA接口8把命令发送给TCAM 10执行。当TCAM 10执行完命令后，如果命令有返回结果，那么结果获取部件(Execute Result)6会获取到执行结果，然后交由调度器4处理，调度器会把结果送到context的结果队列(RES FIFO)16中，这时网络处理器1就可以从TCAM转换器11中的相应context中获取查询结果。

该TCAM转换器的主要功能其实就是对现有TCAM器件的功能进行扩展从而可以支持更多的用户自定义功能。该TCAM转换器是一个很通用的框架，它并不仅限于上面所述的功能，用户可以根据自己的需要增加其它的功能。

本发明另一实施例使用多片TCAM进行并行查找。当一片TCAM的查找速度无法满足要求时，可以使用多片TCAM方案，这时每片TCAM都可以并行进行不同的ACL查找，从而提高查找速度，这是一种增加并行度的技术。参见图4，这里使用两片TCAM(TCAM1和TCAM2)进行分流，每片TCAM存储的内容完全一样，设计思想是增加并行度。因为每片TCAM存储的内容完全一样，所以查找的结果不需要进行转换，可以直接进行使用，另外任意一个ACL号可以在任意一个TCAM中进行查找。当一个数据包到达时，假设需要进行4次ACL查找，那么可以将这4次查找平均分配到每个TCAM中，这样每个TCAM只需要进行2次查找。利用多片TCAM分流的优点在于性能提高一倍，可以进行灵活查找，实现起来比较简单。但却浪费TCAM空间。

本发明的又一实施例使用MultiSearch(多次查找)一次查找多个ACL结果，可以提高单次查找速度。很多TCAM产品都支持MultiSearch功能，它可以使用同一个key在两个不同的表中一次查得两个结果。该实施例中的逻辑分表技术利用TCAM的MultiSearch功能来实现，可以提高单次查找的速度。本发明使用一种逻辑分表技术可以使得使用ACL号不同的两个key在同一个ACL表中查得两个结果。实现的方法是在TCAM条目格式中使用两个ACL号字段，ACL表在逻辑上分成左边和右边两个表，左边表的规则中第二个ACL号为“*”即第二个ACL号不参与匹配，右边表的规则中第一个ACL号为“*”即第一个ACL号不参与匹配。查找时在key中写入两个不同的ACL号，第一个ACL号就会在左边的ACL表中查，第二个ACL号就会在右边的ACL表中查，这样就可以一次查得两个ACL结果，分别是第一结果(1st Result)和第二结果(2nd Result)。图2是一次查找多个ACL结果的TCAM条目格式。

图5是一次查找多个ACL结果的原理图。如图5，两个逻辑分表中可以存储完全相同的内容，这样做的优点在于：任意一个ACL号可以在任意一个表内查找，即可以进行任意组合查找，性能很高。注意第二个查找结果需要减去N/2；缺点在于：只能使用一半的表空间。两个逻辑分表中也可根据业务存储不同的内容，比如表0存储基本的Port/uRPF ACL，表1存储NAT，QoS ACL等。这种做法的优点在于：整个表空间都可以利用；缺点：只能进行受限的组合查找，性能不是很高。类似的，逻辑分表可以是分成多于两个的多个表，每个条目使用多个ACL号字段分别供多个ACL子表使用，查找时在关键字中设置多个不同的ACL号字段来实现一次查得多个结果。

本发明的三个实施例从三个不同的方面来提高TCAM实现报文分类的查找速度，它们可以单独使用，也可以任意组合使用。三个实施例的本质技术特征都是使用空间换取时间：第一实施例使用cache技术，它把key缓存起来(空间)，从而可以减少输入时间，提高查找速度(时间)；第二实施例采用增加并行度的方法，它使用多片TCAM(空间)同时查找，从而提高查找速度(时间)；第三实施例使用逻辑分表技术，它在key中设置2个ACL号字段(空间)，一次查得2个结果，从而提高查找速度(时间)。

本发明的有益效果在于采用本发明所述方法可以大大提高TCAM实现ACL/QoS的查找速度，满足在高速网络下实现报文分类多次查找的线速要求。本发明的方法实用性非常强，可供选择的方式也很多，灵活性也非常好。

当然，本发明还可有其它多种实施例，在不背离本发明精神及其实质的情况下，熟悉本领域的技术人员当可根据本发明作出各种相应的改变和变形，但这些相应的改变和变形都应属于本发明所附的权利要求的保护范围。