CN101986271A - 调度tcam查询和刷新消息的方法和装置 - Google Patents

Abstract

本发明公开了一种调度TCAM查询和刷新消息的方法和装置。其中，该方法包括：FPGA收到查询消息后，将该查询消息放入查询消息队列；FPGA收到刷新消息后，将刷新消息放入刷新消息队列；FPGA分别对查询消息队列中的查询消息和刷新消息队列中的刷新消息进行调度。根据本发明，解决了因刷新优先级高于查询优先级引起的查询响应较慢的问题，能够提供高速的查表转发和表项刷新，实现快速转发，提升了网络设备的吞吐能力，进而提高网络设备的性能。

Description

调度TCAM查询和刷新消息的方法和装置

技术领域

本发明涉及网络通信技术领域，尤其涉及一种调度TCAM(Ternary Content Addressable Memory，三态内容寻址存储器)查询和刷新消息的方法和装置。

背景技术

TCAM主要用于网络设备报文转发时快速查找ACL(AccessControl List，访问控制链表)、路由等表项。基于FPGA(FieldProgrammable Gate Array，现场可编程门阵列)的TCAM查找及刷新技术提供表项更新和查询调度，其中FPGA在处理器或者CPU和TCAM之间起到中转作用。在路由器和交换机等互连设备上，为了实现快速查表转发，TCAM的应用越来越普遍。

随着宽带网络的迅速发展，多核处理器的应用也越来越广泛，多个处理器内核集合起来可以提供很高的处理能力，为了充分利用每个单核处理器的资源，转发时将报文的处理分散到各个处理器单元，单个处理器单元都需要对报文进行ACL、路由等表项的查找，同时CPU需要对TCAM中的表项条目以及处理器外设中的表项内容进行刷新操作，多个处理器需要共同访问单一的TCAM外设，如何使多个处理器实现TCAM的快速查表转发和表项条目刷新，并且使得各处理器的性能均衡，这就是基于FPGA的TCAM查询及刷新装置需要解决的问题。

如图1示出了相关技术基于FPGA的TCAM查询及刷新系统的结构框图，其包括处理器、CPU接口、FPGA、TCAM单元和SSRAM(串行静态随机存储器)，SSRAM用于存放路由表。该技术的FPGA将TCAM查询和CPU对表项的刷新请求放在同一个队列中，基于查询和刷新的优先级对队列中的请求进行调度，其中，CPU对表项的刷新优先级高于处理器对TCAM查询的优先级。这种分优先级调度的方法，使得查询和刷新的藕合度比较紧密，当有大量表项更新时，查询的响应速度将非常低，易造成网络中报文的阻塞，影响网络设备的吞吐能力。

发明内容

本发明的主要目的在于提供一种调度TCAM查询和刷新消息的方法和装置(包括FPGA装置和网络设备)，以至少解决上述因刷新优先级高于查询优先级引起的查询响应较慢的问题。

根据本发明的一个方面，提供了一种调度TCAM查询和刷新消息的方法，包括：FPGA收到查询消息后，将该查询消息放入查询消息队列；FPGA收到刷新消息后，将该刷新消息放入刷新消息队列；FPGA分别对查询消息队列中的查询消息和刷新消息队列中的刷新消息进行调度。

根据本发明的另一方面，提供了一种FPGA装置，包括：查询消息入队模块，用于收到查询消息后，将该查询消息放入查询消息队列；刷新消息入队模块，用于收到刷新消息后，将该刷新消息放入刷新消息队列；查询调度模块，用于对查询消息队列中的查询消息进行调度；刷新调度模块，用于对刷新消息队列中的刷新消息进行调度。

根据本发明的又一方面，提供了一种网络设备，包括上述FPGA装置，该网络设备还包括：处理器，用于向FPGA装置发送查询消息，以及接收FPGA装置返回的查询结果，根据查询结果获取路由信息，根据路由信息进行报文转发；CPU，用于向FPGA装置发送刷新消息，该刷新消息携带有对调度三态内容寻址存储器TCAM进行刷新操作的指示信息。

通过本发明，采用FPGA上设置两个分支，即查询处理分支和刷新处理分支，对两个分支采用单独进行处理，互不干扰，解决了因刷新优先级高于查询优先级引起的查询响应较慢的问题，能够提供高速的查表转发和表项刷新，实现快速转发，提升了网络设备的吞吐能力，进而提高网络设备的性能。

附图说明

此处所说明的附图用来提供对本发明的进一步理解，构成本申请的一部分，本发明的示意性实施例及其说明用于解释本发明，并不构成对本发明的不当限定。在附图中：

图1是根据相关技术的基于FPGA的TCAM查询及刷新系统的结构框图；

图2是根据本发明实施例1的调度TCAM查询和刷新消息的方法流程图；

图3是根据本发明实施例1的提供的缓存队列结构图；

图4是根据本发明实施例2的网络设备的结构框图；

图5是根据本发明实施例2的查询消息入队和出队调度的方法流程图；

图6是根据本发明实施例2的查询消息入队和出队调度的示意图；

图7是根据本发明实施例2的TCAM查询表项的方法流程图；

图8是根据本发明实施例2的CPU对表项刷新的方法流程图；

图9是根据本发明实施例3的FPGA装置的结构框图；

图10是根据本发明实施例4的网络设备的结构框图。

具体实施方式

下文中将参考附图并结合实施例来详细说明本发明。需要说明的是，在不冲突的情况下，本申请中的实施例及实施例中的特征可以相互组合。

实施例1

图2示出了根据本发明实施例的一种调度TCAM查询和刷新消息的方法流程图，该方法包括以下步骤：

步骤S102，现场可编程门阵列FPGA收到查询消息后，将查询消息放入查询消息队列；

步骤S104，FPGA收到刷新消息后，将该刷新消息放入刷新消息队列；

步骤S106，FPGA分别对查询消息队列中的查询消息和刷新消息队列中的刷新消息进行调度。

上述FPGA对TCAM的查询和刷新消息采用分路进行存放，能够实现并行调度查询和刷新。

为了实现对于多核处理器时，各处理器TCAM查询的均衡处理，优选地，上述FPGA上设置有多个查询消息队列，且查询消息队列与处理器一一对应；相应地，步骤S102包括：FPGA将查询消息放入查询消息携带的处理器编号对应的查询消息队列中；步骤S106中的FPGA对查询消息队列中的查询消息进行调度包括：FPGA采用轮询方式调度多个查询消息队列，对被调度的查询消息队列中的查询消息进行出队列处理。

所谓轮询调度指对每个查询消息队列按照一定的顺序依次调度，在一段时间内，每个查询消息队列被调度的次数基本相同。

优选地，FPGA对被调度的查询消息队列中的查询消息进行出队列处理包括：FPGA采用先进先出(FIFO，First In First Out)的方式对被调度的查询消息队列中的查询消息进行出队列处理。

FPGA对刷新消息队列中的刷新消息进行调度包括：FPGA采用先进先出FIFO的方式对刷新消息队列中的刷新消息进行调度。

上述FPGA对查询消息队列中的查询消息进行调度之后，方法还包括：FPGA接收查询消息的查询结果，将查询结果返回给查询消息对应的处理器；处理器根据查询结果获取路由信息，根据路由信息转发报文。

在实际应用中，一般当用户配置改变或者网络中链路状态发生变化时，TCAM表项条目才会进行刷新，而这些改变的频率较低，这就使得分优先级调度有点多余，所以本实施例没有为刷新调度和查询调度设置优先级，而是将二者分别存放在不同的队列中，对存放的队列分别进行调度。

参见图3，为本发明实施例提供的缓存队列结构图，缓存队列包括多个查询消息队列和一个刷新消息队列，其中，s1-s5表示查询消息，u1-u5表示刷新消息，具体介绍如下：

查询消息队列为多个，对应每个处理器设置，一个查询消息队列用于缓存来自同一个处理器发出的查询消息，本发明实施例的查询消息可以包括：处理器编号、所查询表项类型、查询内容的大小以及查询内容。其中，处理器编号用于确定查询消息所入的队列号，以及查询结果返回的处理器；表项类型标识是何种表项的查询，是ACL或者路由，还是其他表项；查询内容的大小表示是多少位的查询，比如144/256；查询内容是输入查找的条件，比如查路由输入的内容是目的IP，ACL查找输入的内容是报文的IP五元组，该IP五元组包括源IP址，目的IP地址，源端口号，目的端口号，以及协议类型。在将查询消息放入对应的查询消息队列时，可以为该查询消息设置消息编号，以标识该查询消息队列中查询消息进入的先后顺序。

刷新消息队列，多个处理器共用一个FIFO缓存队列，只设一个缓存队列是由于在实际应用中CPU对TCAM条目的刷新操作频率较低，一般是在用户配置更改的情况下才刷新表项。刷新消息的数据结构包括刷新消息编号、刷新条目的类型、刷新内容。

缓存队列的长度取2的整数次方，可以直接用查询消息编号或者刷新消息编号的低位找到消息在在缓存队列中的位置，比如缓存队列长度为32，为2的5次方，则取消息编号的二进制数低5位作为其在缓存队列中的位置，例如，消息编号为57，其二进制数为111001，低5位为11001，十进制为25，则该消息入缓存队列25的位置。

上述方法可以应用于多核处理器或者多个处理器用FPGA中转进行TCAM查询及刷新处理中，由于其FPGA上设置两个分支，即查询处理分支和刷新处理分支，对两个分支采用单独进行处理，互不干扰，解决了因刷新优先级高于查询优先级引起的查询响应较慢的问题，能够提供高速的查表转发和表项刷新，实现快速转发，提升了网络设备的吞吐能力，进而提高网络设备的性能。

实施例2

本实施例提供了一种调度TCAM查询和刷新消息的方法，该方法以在图4所示的网络设备上实现为例进行说明，图4所示的网络设备包括如下功能单元：

1)处理器单元，处理器单元通过查询通道与FPGA相连，其内部包括多个处理器，分别用处理器1、处理器2、......、处理器n表示，多个单核处理器或者多个处理器可以同时发出对不同表项的TCAM查询请求。查询通道负责传递从各个处理器发出的查询请求以及从FPGA返回的查询结果，处理器根据该查询的结果，访问存储在处理器外设中的表项，获取报文转发所需的信息，以实现报文的转发。

2)CPU，CPU通过刷新通道与FPGA相连，CPU通过FPGA对TCAM中表项条目进行增加、删除、更新操作，同时对处理器外设中表项进行相应修改。

3)处理器外设，包括SRAM(Static Random Access Memory，静态随机存储器)、DRAM(Dynamic Random Access Memory，动态随机存储器)以及DDR(Double Data Rate，双倍数据传输速率存储器)等外设，上述处理器查询TCAM得到的结果是一个指向存储在外设中的具体表项地址的指针或者索引，根据该指针或索引处理器从外设中读取相应表项信息。CPU对TCAM表项条目进行更新操作的同时，对存储在外设中相应表项进行相应的修改。

4)FPGA，FPGA包括查询处理单元和刷新处理单元，其分别响应处理器和CPU发出的查询和刷新请求，查询处理和刷新处理独立运作，在CPU刷新TCAM表项条目的同时，处理器仍然可以进行TCAM查询。

其中，查询处理单元根据单核处理器的个数设置有多个FIFO查询缓存队列(对应于实施例1中的查询消息队列)，每个处理器对应一个FIFO队列，队列之间采用轮询调度的原则。查询处理单元根据处理器编号将查询消息分发到对应的查询队列中。刷新处理单元的功能在于快速响应CPU的更新命令，对TCAM中表项进行更新。

5)TCAM单元，用于响应CPU通过FPGA发来的刷新消息，更新表项条目；以及用于响应处理器通过FPGA发来的查询消息，并返回查询结果。

基于图4所示的网络设备，本实施例提供了一种查询消息入队和出队调度的方法，本实施例的FPGA的查询处理单元维护一个队列状态向量，队列状态向量是一个二进制的数值，相应位置1表示该队列有消息，例如：队列总数为8，队列状态向量00001001表示队列1和队列4中有消息需要出队，而其他6个队列中没有消息需要出队，参见图5，该方法包括以下步骤：

步骤S502，查询消息入队，具体为：查询处理单元接收到查询消息后，根据查询消息的处理器编号分别入队，对查询消息编号，根据入队的队列号将队列状态向量的相应位置1，表示该队列有消息需要出队；

步骤S504，查询处理单元对各队列采用轮询的方式循环调度，每轮调度一个队列中的一个查询消息；具体如下：

步骤1，初始化调度队列号为n＝1，从第一个队列开始调度；

步骤2，如果n大于队列总数，则设置n＝1，即最后一个队列执行了调度后，再从第一个队列开始循环调度；否则，本轮调度队列为n；

步骤3，判断队列状态向量的相应位是否置1，若置1，表示该队列有查询消息需要出队，则执行步骤4；否则，表示该队列没有查询消息需要调度，执行下一个队列的调度，即执行步骤5；

步骤4，队列内部的调度，根据查询消息编号顺序出队，如果该队列所有查询消息都被调度出去，将该队列对应的队列向量中的位清0。

步骤5，n＝n+1，执行下一个队列的调度，跳到步骤3。

参见图6所示的查询消息入队和出队调度的示意图，FPGA根据查询消息的处理器编号将查询消息放入对应的队列，采用轮询方式对各队列的查询消息进行出队处理。

基于图4所示的网络设备，图7示出了根据本实施例的一种TCAM表项查询方法的流程图，该方法包括以下步骤：

步骤S702，处理器1、处理器2，......，处理器n根据需要发出查询消息，查询消息中包括处理器编号、所查询表项的类型、查询内容的大小、查询内容，查询消息通过查询通道传送给FPGA；

步骤S704，FPGA识别出查询消息，将查询消息按处理器编号入队；

FPGA的查询处理单元维护多个查询消息队列，每个处理器对应一个队列，根据处理器编号将查询消息入队，按照轮询的方式对多个查询消息队列进行调度，每个队列内部按FIFO的原则调度，进行TCAM查询，并将查询结果返回给请求的处理器。

步骤S706，查询处理单元将查询消息出队，进入TCAM查询，并将查询的结果按处理器编号返回给相应的处理器；

步骤S708，处理器根据TCAM查询的结果，即表项信息在处理器外设中的地址，读取表项的具体内容；

步骤S710，处理器根据查询到表项的内容进行报文转发。

基于图4所示的网络设备，图8示出了根据本实施例的一种CPU对表项刷新的方法流程图，该方法包括以下步骤：

步骤S802，CPU发出表项刷新消息，刷新消息中包括表项的类型以及刷新的内容，刷新消息通过刷新通道传送给FPGA；

步骤S804，FPGA识别出刷新消息，将刷新消息入队；

步骤S806，按照先进先出的原则将刷新消息调度出队；

步骤S808，TCAM收到刷新消息则将表项条目进行更新，包括增添、删除、修改操作；

步骤S810，CPU对处理器外设表项中的条目进行更新，包括增添、删除、修改操作。

上述方法中的处理器用FPGA中转进行TCAM的查询访问，FPGA返回指向外设中表项地址的指针或者索引，处理器根据返回的结果，读取处理器外设中的表项；另外，CPU用FPGA中转进行TCAM的刷新操作(即TCAM表项条目的更新操作)，同时更新处理器外设中的相应表项信息。

本实施例提供的调度方法支持查询和刷新操作的并行处理，在查询的同时可以进行表项条目的更新，表项条目更新的同时也可以进行查询。同时，上述方法采用在FPGA上设置与处理器个数对应的查询消息队列，能够解决相关技术只支持单个处理器的查询，对多个处理器或者多线程的并行查询以及多种表项的查询处理能力不足的问题，如果有多个单核处理器并行查询多种表项，查找的效率将比较高；且因采用轮询调度的方式，各个单核处理器的性能也比较均衡。

实施例3

图9示出了根据本发明实施例的一种FPGA装置的结构框图，该装置包括：

查询消息入队模块92，用于收到查询消息后，将查询消息放入查询消息队列；

刷新消息入队模块94，用于收到刷新消息后，将刷新消息放入刷新消息队列；

查询调度模块96，与查询消息入队模块92相连，用于对查询消息队列中的查询消息进行调度；

刷新调度模块98，与刷新消息入队模块94相连，用于对刷新消息队列中的刷新消息进行调度。

查询消息入队模块92包括：队列确定单元，用于接收到查询消息后，根据查询消息携带的处理器编号确定对应的查询消息队列；其中，FPGA装置上设置有多个查询消息队列，且查询消息队列与处理器一一对应；入队单元，用于将查询消息放入队列确定单元确定的查询消息队列中；

查询调度模块96包括：轮询调度单元，用于采用轮询方式调度多个查询消息队列；出队单元，用于对轮询调度单元调度的查询消息队列中的查询消息进行出队列处理。

优选地，出队单元包括：出队子单元，用于采用先进先出FIFO的方式对上述轮询调度单元调度的查询消息队列中的查询消息进行出队列处理。

刷新调度模块98包括：刷新调度单元，用于采用先进先出FIFO的方式对刷新消息队列中的刷新消息进行调度。

其中，上述查询消息包括：处理器编号、所查询表项类型、查询内容的大小以及查询内容。处理器编号用于确定查询消息所入的队列号，以及查询结果返回的处理器；表项类型标识是何种表项的查询，是ACL或者路由，还是其他表项；查询内容的大小表示是多少位的查询，比如144/256；查询内容是输入查找的条件，比如查路由输入的内容是目的IP，ACL查找输入的内容是报文的IP五元组，该IP五元组包括源IP址，目的IP地址，源端口号，目的端口号，以及协议类型。在将查询消息放入对应的查询消息队列时，可以为该查询消息设置消息编号，以标识该查询消息队列中查询消息进入的先后顺序。

刷新消息队列，本实施例的多个处理器共用一个FIFO缓存队列，本实施例只设一个刷新消息队列是由于在实际应用中CPU对TCAM条目的刷新操作频率较低，一般是在用户配置更改的情况下才刷新表项。刷新消息的数据结构包括刷新消息编号、刷新条目的类型、刷新内容。

上述FPGA装置可以应用于多核处理器或者多个处理器用FPGA中转进行TCAM查询及刷新处理中，由于FPGA装置上设置两个分支，即查询处理分支和刷新处理分支，对两个分支采用单独进行处理，互不干扰，解决了因刷新优先级高于查询优先级引起的查询响应较慢的问题，能够提供高速的查表转发和表项刷新，实现快速转发，提升了网络设备的吞吐能力，进而提高网络设备的性能。

实施例4

图10示出了根据本发明实施例的一种网络设备的结构框图，该网络设备包括FPGA装置102、处理器104和CPU 106，FPGA装置102分别与处理器104和CPU 106相连，其中，FPGA装置102可以按照实施例3中的方式实现，这里不再详述。

处理器104，用于向FPGA装置102发送查询消息，以及接收所述FPGA装置返回的查询结果，根据该查询结果获取路由信息，根据该路由信息进行报文转发；

CPU 106，用于向FPGA装置102发送刷新消息，其中，该刷新消息携带有对调度TCAM进行刷新操作的指示信息。

本实施例的网络设备还可以按照实施例2中图4所示的网络设备实现，具体功能与其相同，这里不再赘述。

本实施例的网络设备通过在FPGA装置上设置两个分支，即查询处理分支和刷新处理分支，对两个分支采用单独进行处理，互不干扰，解决了因刷新优先级高于查询优先级引起的查询响应较慢的问题，能够提供高速的查表转发和表项刷新，实现快速转发，提升了网络设备的吞吐能力，进而提高网络设备的性能。

与现有技术相比较，以上实施例提供的技术，通过对查询和刷新的分开处理，使得查询和刷新的处理互不干扰，提高了查询与刷新的效率；将不同处理器的查询消息分开入队，实现了并行查询，各个单核处理器的查询队列轮询调度，使得每个单核处理器的性能均衡。并能够快速响应处理器对TCAM的查询以及表项的刷新，实现快速转发，提高了网络设备吞吐能力，进而提升了网络设备的性能。

显然，本领域的技术人员应该明白，上述的本发明的各模块或各步骤可以用通用的计算装置来实现，它们可以集中在单个的计算装置上，或者分布在多个计算装置所组成的网络上，可选地，它们可以用计算装置可执行的程序代码来实现，从而，可以将它们存储在存储装置中由计算装置来执行，并且在某些情况下，可以以不同于此处的顺序执行所示出或描述的步骤，或者将它们分别制作成各个集成电路模块，或者将它们中的多个模块或步骤制作成单个集成电路模块来实现。这样，本发明不限制于任何特定的硬件和软件结合。

以上所述仅为本发明的优选实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

Claims (10)

1.一种调度三态内容寻址存储器TCAM查询和刷新消息的方法，其特征在于，包括：

现场可编程门阵列FPGA收到查询消息后，将所述查询消息放入查询消息队列；

所述FPGA收到刷新消息后，将所述刷新消息放入刷新消息队列；

所述FPGA分别对所述查询消息队列中的查询消息和所述刷新消息队列中的刷新消息进行调度。

2.根据权利要求1所述的方法，其特征在于，所述FPGA上设置有多个查询消息队列，且所述查询消息队列与处理器一一对应；

所述FPGA将所述查询消息放入查询消息队列包括：所述FPGA将所述查询消息放入所述查询消息携带的处理器编号对应的查询消息队列中；

所述FPGA对所述查询消息队列中的查询消息进行调度包括：所述FPGA采用轮询方式调度所述多个查询消息队列，对被调度的查询消息队列中的查询消息进行出队列处理。

3.根据权利要求2所述的方法，其特征在于，所述FPGA对被调度的查询消息队列中的查询消息进行出队列处理包括：

所述FPGA采用先进先出FIFO的方式对所述被调度的查询消息队列中的查询消息进行出队列处理。

4.根据权利要求1所述的方法，其特征在于，所述FPGA对所述刷新消息队列中的刷新消息进行调度包括：

所述FPGA采用先进先出FIFO的方式对所述刷新消息队列中的刷新消息进行调度。

5.根据权利要求1-4任一项所述的方法，其特征在于，所述FPGA对所述查询消息队列中的查询消息进行调度之后，所述方法还包括：

所述FPGA接收所述查询消息的查询结果，将所述查询结果返回给所述查询消息对应的处理器；

所述处理器根据所述查询结果获取路由信息，根据所述路由信息转发报文。

6.一种现场可编程门阵列FPGA装置，其特征在于，包括：

查询消息入队模块，用于收到查询消息后，将所述查询消息放入查询消息队列；

刷新消息入队模块，用于收到刷新消息后，将所述刷新消息放入刷新消息队列；

查询调度模块，用于对所述查询消息队列中的查询消息进行调度；

刷新调度模块，用于对所述刷新消息队列中的刷新消息进行调度。

7.根据权利要求6所述的装置，其特征在于，

所述查询消息入队模块包括：队列确定单元，用于接收到所述查询消息后，根据所述查询消息携带的处理器编号确定对应的查询消息队列；其中，所述FPGA装置上设置有多个查询消息队列，且所述查询消息队列与处理器一一对应；入队单元，用于将所述查询消息放入所述队列确定单元确定的所述查询消息队列中；

所述查询调度模块包括：轮询调度单元，用于采用轮询方式调度所述多个查询消息队列；出队单元，用于对所述轮询调度单元调度的所述查询消息队列中的查询消息进行出队列处理。

8.根据权利要求7所述的装置，其特征在于，所述出队单元包括：

出队子单元，用于采用先进先出FIFO的方式对所述轮询调度单元调度的所述查询消息队列中的查询消息进行出队列处理。

9.根据权利要求6所述的装置，其特征在于，所述刷新调度模块包括：

刷新调度单元，用于采用先进先出FIFO的方式对所述刷新消息队列中的刷新消息进行调度。

10.一种网络设备，其特征在于，包括权利要求6-9任一项所述的现场可编程门阵列FPGA装置，所述网络设备还包括：

处理器，用于向所述FPGA装置发送查询消息，以及接收所述FPGA装置返回的查询结果，根据所述查询结果获取路由信息，根据所述路由信息进行报文转发；

CPU，用于向所述FPGA装置发送刷新消息，所述刷新消息携带有对调度三态内容寻址存储器TCAM进行刷新操作的指示信息。

Images