CN105704037A - 一种表项保存方法和控制器 - Google Patents

Abstract

一种表项保存方法和控制器，通过在转发设备片内内存带宽和空间足够的情况下，让生成的表项优先占用高速的片内内存；在转发设备片内内存带宽或空间不足的情况下，优先将片内内存中优先级较低的表项切换到片外内存；在转发设备片内内存中有表项删除时，优先将片外内存中优先级较高的表项切回至片内内存，从而实现了片内内存的带宽和空间的最大利用，以及提高了转发设备整体的处理速度。

Description

一种表项保存方法和控制器

技术领域

本发明涉及通信技术领域，尤其涉及一种表项保存方法和控制器。

背景技术

转发设备处理报文是基于一系列的表项完成的。表项在转发设备上占用的内存可以分为转发芯片内部的内存和转发芯片外部的内存，为了便于说明，下文将这两种内存分别称为片内内存和片外内存。通常片内内存的空间小但带宽高，片外内存的空间大但带宽较小。

转发设备在出厂时，其支持的业务和每个类型的表项的规格都是确定的。每种业务的完成需要一系列的表项来支持，转发设备支持的业务确定了意味着转发设备支持的表项的类型也是确定的。表项的规格表示表项可以同时配置的最大数量，例如，某一类型的表项的规格为10000，表示同一时间存储在该转发设备上的这一类型的表项的数量不能超过10000。

目前各类型的表项在转发设备上的存储位置在转发设备出厂时便是规划好的。例如，转发设备可以预先规定将带宽要求高占用内存小的表项部署在片内内存，如下表1中的表(Table)A和TableB；将带宽要求低的表项部署在片外内存，如下表1中的TableC和TableD；对带宽要求高占用内存也大的表项采用分段部署，即将这类表项的一部分部署在片内内存，另一部分部署在片外内存，如下表1中的TableE。

表1

由于表项的部署位置是固定的，表项不论是否配置都会占用转发设备的空间和带宽，而转发设备实际使用的规格往往远小于转发设备支持的规格，从而实际使用的内存可能只是片内内存和片外内存的一小部分，导致片内内存的带宽和空间利用率低。

发明内容

本申请提供一种表项保存方法和控制器，用以解决转发设备采用固定方式部署表项导致片内内存的带宽和空间利用率低的问题。

第一方面，提供了一种表项保存方法，方法包括：

控制器将转发设备的第一内存和第二内存包括的每个物理块均划分为多个小颗粒存储单元，每个小颗粒存储单元用于存储同种类型的表项；所述第一内存的带宽大于所述第二内存的带宽；

所述控制器生成第一表项，并在保存所述第一表项之前，首先判断所述第一内存和所述第二内存中是否已经存储有与所述第一表项属于同一类型的表项；

若所述第一内存和所述第二内存中未存储有与所述第一表项属于同一类型的表项，则所述控制器在确定所述第一内存包括的第一物理块的剩余带宽和剩余空间不小于所述第一表项需要的带宽和空间时，可以在所述第一物理块中确定出未被任何表项占用的第一小颗粒存储单元，所述第一物理块为所述第一内存包括的各个物理块中的一个，所述第一小颗粒存储单元为对所述第一物理块划分得到的多个小颗粒存储单元中的任意一个；

所述控制器将所述第一表项发送给所述转发设备，并指示所述转发设备将所述第一表项保存到所述第一小颗粒存储单元中。

通过上述方式，通过将内存划分成小颗粒存储单元，并在转发设备片内内存带宽和空间足够的情况下，让表项优先占用高速的片内内存，更充分地利用了片内内存的带宽和空间。

在一个可能的设计中，控制器将转发设备的第一内存和第二内存包括的每个物理块划分为多个小颗粒存储单元时，可以通过如下方式实现：

控制器将转发设备的第一内存和第二内存包括的每个物理块划分为大小为N的多个小颗粒存储单元；

相应的，所述方法还包括：

所述控制器确定在生成所述第一表项之前已生成的与所述第一表项属于同一类型的其它表项的数量m；

若m＝0，则所述控制器确定所述第一内存或所述第二内存中未存储有与所述第一表项属于同一类型的表项；

若m≠0，则所述控制器确定所述第一内存或所述第二内存中存储有与所述第一表项属于同一类型的表项；

当m＝0时，或是当m≠0，且m为的整数倍时，L为所述第一表项的位宽，所述控制器可以在确定所述第一物理块的剩余带宽和剩余空间不小于所述第一表项需要的带宽和空间时，在所述第一物理块中确定所述第一小颗粒存储单元；其中，当m≠0，且m为的整数倍时，表明虽然所述第一内存和第二内存中存储有与所述第一类型属于同一类型的表项，但分配给这些表项的小颗粒存储单元已存满。

所述控制器将所述第一表项发送给所述转发设备，并指示所述转发设备将所述第一表项保存到所述第一小颗粒存储单元中。

在一个可能的设计中，所述方法还包括：

若m不为的整数倍，表明所述第一内存和第二内存中存储有与所述第一类型属于同一类型的表项，并且分配给这类表项的小颗粒存储单元还足够存下所述第一表项，则所述控制器确定存储有第二表项的第二小颗粒存储单元；所述第二表项为在所述第一表项前一个生成的、与所述第一表项属于同一类型的表项；

所述控制器将所述第一表项发送给所述转发设备，并指示所述转发设备将所述第一表项保存到所述第二小颗粒存储单元中。

在一个可能的设计中，所述方法还包括：

若m为的整数倍，所述第一内存包括的每个物理块的剩余带宽小于所述第一表项需要的带宽；m可以等于0，也可以不等于0；

则所述控制器确定在所述第一内存包括的第二物理块上保存的第一类型的表项，以及确定所述第二物理块上用于保存所述第一类型的表项的所有小颗粒存储单元；所述第一类型的表项的优先级低于所述第一表项的优先级，所述第二物理块为所述第一内存包括的各个物理块中的任意一个；

所述控制器将所述第一表项发送给所述转发设备，并指示所述转发设备将所述所有小颗粒存储单元中保存的表项移动到所述第二内存中，以及指示所述转发设备将所述第一表项保存到所述所有小颗粒存储单元中的其中一个小颗粒存储单元中。

在一个可能的设计中，所述方法还包括：

若m为的整数倍，所述第一内存包括的每个物理块的剩余空间小于所述第一表项需要的空间；m可以等于0，也可以不等于0；

则所述控制器确定在所述第一内存包括的第三物理块上保存的第二类型的表项，以及确定所述第三物理块上用于保存所述第二类型的表项的一个小颗粒存储单元；所述第二类型的表项的优先级低于所述第一表项的优先级，所述第三物理块为所述第一内存包括的各个物理块中的任意一个；

所述控制器将所述第一表项发送给所述转发设备，并指示所述转发设备将所述一个小颗粒存储单元中保存的表项移动到所述第二内存中，以及指示所述转发设备将所述第一表项保存到所述一个小颗粒存储单元中。

通过上述两种方式，在转发设备片内内存带宽或空间不足的情况下，优先将片内内存中优先级较低的表项切换到片外内存，从而充分利用了皮纳内内存的带宽和空间。

在一个可能的设计中，所述方法还包括：

所述控制器删除第三小颗粒存储单元上的第三表项，所述第三小颗粒存储单元位于所述第一内存包括的第四物理块上，所述第四物理块为所述第一内存包括的各个物理块中的任意一个，所述第三小颗粒存储单元为对所述第四物理块划分得到的多个小颗粒存储单元中的任意一个；

若删除所述第三表项后的第三小颗粒存储单元未被任何表项占用、且删除所述第三表项后的所述第四物理块上还保存有与所述第三表项属于同一类型的其它表项、并保存有第三类型的表项，则所述控制器指示所述转发设备将所述第二内存中保存的所述第三类型的表项从所述第二内存的一个小颗粒存储单元移动到所述第三小颗粒存储单元，所述第三类型与所述第三表项所属的类型为不同类型；或

若删除所述第三表项后的所述第四物理块上未保存有与所述第三表项属于同一类型的其它表项，则所述控制器指示所述转发设备将所述第二内存中保存的优先级最高的表项从所述第二内存的一个小颗粒存储单元移动到所述第三小颗粒存储单元。

通过上述方式，在转发设备片内内存中有表项删除时，优先将片外内存中优先级较高的表项切回至片内内存，从而实现了片内内存的带宽和空间的最大利用。

第二方面，提供了一种控制器，所述控制器具有实现上述方法的功能。所述功能可以通过硬件实现，也可以通过硬件执行相应的软件实现。所述硬件或软件包括一个或多个与上述功能相对应的模块。

在一个可能的设计中，所述控制器包括：

划分单元，用于将转发设备的第一内存和第二内存包括的每个物理块划分为多个小颗粒存储单元，每个小颗粒存储单元用于存储同种类型的表项；所述第一内存的带宽大于所述第二内存的带宽；

生成单元，用于生成第一表项；

确定单元，若所述第一内存和所述第二内存中未存储有与所述第一表项属于同一类型的表项，则用于在确定所述第一内存包括的第一物理块的剩余带宽和剩余空间不小于所述第一表项需要的带宽和空间时，在所述第一物理块中确定未被任何表项占用的第一小颗粒存储单元，所述第一物理块为所述第一内存包括的各个物理块中的一个，所述第一小颗粒存储单元为对所述第一物理块划分得到的多个小颗粒存储单元中的任意一个；

发送单元，用于将所述第一表项发送给所述转发设备，并指示所述转发设备将所述第一表项保存到所述第一小颗粒存储单元中。

在另一个可能的设计中，所述移动终端包括存储器、处理器和通信接口，所述存储器、所述处理器和所述通信接口之间通过总线相互连接；其中

所述处理器，用于将转发设备的第一内存和第二内存包括的每个物理块划分为多个小颗粒存储单元，每个小颗粒存储单元用于存储同种类型的表项；生成第一表项；若所述第一内存和所述第二内存中未存储有与所述第一表项属于同一类型的表项，则用于在确定所述第一内存包括的第一物理块的剩余带宽和剩余空间不小于所述第一表项需要的带宽和空间时，在所述第一物理块中确定未被任何表项占用的第一小颗粒存储单元，所述第一物理块为所述第一内存包括的各个物理块中的一个，所述第一小颗粒存储单元为对所述第一物理块划分得到的多个小颗粒存储单元中的任意一个；

所述通信接口，用于将所述第一表项发送给所述转发设备，并指示所述转发设备将所述第一表项保存到所述第一小颗粒存储单元中；

所述存储器中存放程序，所述处理器通过执行该程序，实现上述方法。

利用本申请提供的方案，通过将带宽高的片内内存作为各类型表项共用的动态内存，在转发设备片内内存带宽和空间足够的情况下，让生成的表项优先占用高速的片内内存，从而实现了片内内存的带宽和空间的最大利用。

附图说明

图1为本申请提供的一种表项保存方法的流程图；

图2为本申请提供的一种控制器的结构示意图。

具体实施方式

本申请提供了一种表项保存方法和控制器，通过将带宽高的片内内存作为各类型表项共用的动态内存，在转发设备片内内存带宽和空间足够的情况下，让生成的表项优先占用高速的片内内存，从而实现了片内内存的带宽和空间的最大利用。

本申请提供的技术方案可以应用于具备转发芯片的转发设备上，如路由器、交换机等；此外，其它同样具备有配套的片内内存和片外内存、同时内存上采用固定方式部署表项的设备也可以采用本申请提供的技术方案。

需要说明的是，本申请中所说的控制器，可以是独立于转发设备的第三方设备，如软件定义网络(英文：SoftwareDefinedNetwork，简称：SDN)中位于网络侧的控制器；也可以位于转发设备内部。

下面结合说明书附图和各实施例对本发明技术方案进行说明。

图1所示为本申请提供的表项保存方法的流程图，所述方法包括如下步骤：

步骤101：控制器将转发设备的第一内存和第二内存包括的每个物理块划分为多个小颗粒存储单元，每个小颗粒存储单元用于存储同种类型的表项；所述第一内存的带宽大于所述第二内存的带宽。

以转发芯片为例，这里的第一内存即是指转发芯片内部的内存；第二内存即是指转发芯片外部的内存。

控制器可以按照合适的大小，将每个物理块划分为若干相等或不等的小颗粒存储单元。例如，假设某芯片的片内内存为32兆比特(单位：Mbit)，若将片内内存划分为大小固定的小颗粒存储单元，每个小颗粒存储单元的大小为128bit*128，则一共可以得到32Mbit/(128bit*128)＝2048个小颗粒存储单元；若将一个这样的小颗粒存储单元用于存储位宽为128bit的表项，则一共可以存储128张同种类型的表项。

步骤102：所述控制器生成第一表项。

步骤103：若所述第一内存和所述第二内存中未存储有与所述第一表项属于同一类型的表项，则所述控制器在确定所述第一内存包括的第一物理块的剩余带宽和剩余空间不小于所述第一表项需要的带宽和空间时，在所述第一物理块中确定出未被任何表项占用的第一小颗粒存储单元，所述第一物理块为所述第一内存包括的各个物理块中的一个，所述第一小颗粒存储单元为对所述第一物理块划分得到的多个小颗粒存储单元中的任意一个。

步骤104：所述控制器将所述第一表项发送给所述转发设备，并指示所述转发设备将所述第一表项保存到所述第一小颗粒存储单元中。

本申请中表项的部署位置是不固定的，在片内内存的剩余带宽和剩余空间充足的情况下，所有新生成的表项均可以占用高速的片内内存，从而可以实现对片内内存的最大利用。

此外，若所述第一内存和所述第二内存中存储有与所述第一表项属于同一类型的表项，则所述控制器需要进一步判断最近一次申请的、用于存储与所述第一表项属于同一类型的其它表项的小颗粒存储单元是否已经存满，若是，则在确定所述第一内存包括的第一物理块的剩余带宽和剩余空间不小于所述第一表项需要的带宽和空间时，在所述第一物理块中确定出未被任何表项占用的第一小颗粒存储单元，后续指示转发设备将所述第一表项保存至所述第一小颗粒存储单元。否则，控制器指示转发设备将所述第一表项保存至上述最近一次申请的、用于存储与所述第一表项属于同一类型的其它表项的小颗粒存储单元中。

可选的，控制器在生成第一表项后，可以确定在生成所述第一表项之前已生成的与所述第一表项属于同一类型的其它表项的数量m，并根据m来确定所述第一内存和所述第二内存中是否存储有与所述第一表项属于同一类型的表项。

具体的，若m＝0，则表明所述第一内存和所述第二内存中未存储有与所述第一表项属于同一类型的表项；若m≠0，则表明所述第一内存或所述第二内存中存储有与所述第一表项属于同一类型的表项。

假设控制器将转发设备的第一内存和第二内存包括的每个物理块划分成了大小均为N的多个小颗粒存储单元，在m≠0的情况下，如果m为的整数倍，L为所述第一表项的位宽，则表明虽然所述第一内存和第二内存中存储有与所述第一类型属于同一类型的表项，但分配给这些表项的小颗粒存储单元已存满，无法再存下所述第一表项。例如，假设每个小颗粒存储单元的大小为128bit*128，A类型的表项的位宽为90bit，可以得到即每个小颗粒存储单元最多能够存储182张A类型的表项，当控制器已存储的A类型的表项的数量为182的整数倍时，用于存储A类型表项的每个小颗粒存储单元恰好都是存满的。在这种情况下，控制器可以在确定所述第一内存包括的第一物理块的剩余带宽和剩余空间不小于所述第一表项需要的带宽和空间时，优先在所述第一物理块中确定未被任何表项占用的第一小颗粒存储单元。其中，所述第一物理块为所述第一内存包括的各个物理块中的一个，所述第一小颗粒存储单元为对所述第一物理块划分得到的多个小颗粒存储单元中的任意一个。后续，控制器可以将所述第一表项发送给所述转发设备，并指示所述转发设备将所述第一表项保存到所述第一小颗粒存储单元中。

需要注意的是，所述第一表项的位宽L可以是所述第一表项的实际表位宽，也可以是基于所述第一表项的实际表位宽和硬件位宽为所述第一表项选取的一个理论表位宽，例如，A表的实际表位宽为92bit，硬件位宽有32bit、64bit和128bit等多个值，则可以设定A表的理论表位宽为比A表的实际表位宽高的硬件位宽，即128bit。

如果m不为的整数倍，则表明所述第一内存和第二内存中存储有与所述第一类型属于同一类型的表项，并且分配给这类表项的小颗粒存储单元还足够存下所述第一表项。在这种情况下，控制器可以确定出存储有第二表项的第二小颗粒存储单元；所述第二表项为在所述第一表项前一个生成的、与所述第一表项属于同一类型的表项，后续控制器将所述第一表项发送给所述转发设备，并指示所述转发设备将所述第一表项保存到所述第二小颗粒存储单元中。例如，假设每个小颗粒存储单元的大小为128bit*128，B类型表项的位宽为128bit，可以得到即每个小颗粒存储单元最多能够存储128张B类型的表项，当控制器已存储的B类型的表项的数量为129时，控制器分配出去的用于存储B类型表项的两个小颗粒存储单元中一个小颗粒存储单元已经存满，另一个小颗粒存储单元只存了1个表项，控制器可以将新生成的B类型的表项继续存入这个还未存满的小颗粒存储单元中。

本申请中，当所述第一内存和所述第二内存中未存储有与所述第一表型属于同一类型的表项，或是虽然所述第一内存和第二内存中存储有与所述第一类型属于同一类型的表项、但分配给这类表项的小颗粒存储单元已存满时，控制器优先在带宽较高的所述第一内存中申请新的小颗粒存储单元，但有以下两种原因会导致申请新的小颗粒存储单元失败：

第一种原因，所述第一内存包括的每个物理块的剩余空间都小于所述第一表项需要的空间。

第二种原因，所述第一内存包括的每个物理块的剩余带宽都小于所述第一表项需要的带宽。

在第一种原因下，如果所述第一内存包括的每个物理块的剩余空间均不足，控制器可以指示转发设备优先将性能要求较低的类型的表项从所述第一内存的一个小颗粒存储单元切换到所述第二内存的一个小颗粒存储单元。具体实现过程如下：所述控制器确定在所述第一内存包括的第三物理块上保存的第二类型的表项，以及确定所述第三物理块上用于保存所述第二类型的表项的一个小颗粒存储单元；其中，所述第二类型的表项的优先级低于所述第一表项的优先级，所述第三物理块为所述第一内存包括的各个物理块中的任意一个。然后，所述控制器将所述第一表项发送给所述转发设备，并指示所述转发设备将所述一个小颗粒存储单元中保存的表项移动到所述第二内存中，以及指示所述转发设备将所述第一表项保存到所述一个小颗粒存储单元中。例如，某片内内存的剩余空间不足以存储新生成的A类型的表项，转发设备在控制器的指示下，可以找到片内内存中优先级最低的B类型的表项，若B类型的表项的优先级低于A类型的表项，则启动存储单元搬移流程，不论片内内存中B类型的表项占据了多少个小颗粒存储单元，只将其中一个小颗粒存储单元内存储的B类型的表项拷贝至申请的片外内存，然后清空这个小颗粒存储单元内的表项数据，再将新生成的A类型的表项存至这个清空的小颗粒存储单元中。

在第二种原因下，如果所述第一内存包括的每个物理块的剩余带宽均不足，控制器可以指示所述转发设备优先将性能要求较低的类型的表项从所述第一内存的一个物理块切换到所述第二内存的一个物理块。具体实现过程如下：所述控制器确定在所述第一内存包括的第二物理块上保存的第一类型的表项，以及确定所述第二物理块上用于保存所述第一类型的表项的所有小颗粒存储单元；所述第一类型的表项的优先级低于所述第一表项的优先级，所述第二物理块为所述第一内存包括的各个物理块中的任意一个。然后，所述控制器将所述第一表项发送给所述转发设备，并指示所述转发设备将所述所有小颗粒存储单元中保存的表项移动到所述第二内存中，以及指示所述转发设备将所述第一表项保存到所述所有小颗粒存储单元中的其中一个小颗粒存储单元中。例如，某片内内存的剩余带宽不足以存储新生成的A类型的表项，转发设备在控制器的指示下，可以找到片内内存中优先级最低的B类型的表项，若B类型的表项的优先级低于A类型的表项、B类型的表项占用的带宽不低于A类型的表项占用的带宽，则可以启动存储单元组搬移流程，如果片内内存的某一个物理块上共有3个小颗粒存储单元用于存储B类型表项，则可以将这3个小颗粒存储单元内的表项数据拷贝至在片外内存申请的3个小颗粒存储单元中，然后清空片内内存中的这3个小颗粒存储单元内的表项数据，再将新生成的A类型的表项存至这3个清空的小颗粒存储单元的其中一个。

此外，当控制器清空了所述第一内存中的某一个小颗粒存储单元内的表项后，控制器可以启动回切流程，指示转发设备将部署于所述第二内存中的一个小颗粒存储单元的表项搬回至第一内存中的该清空的小颗粒存储单元。具体实现过程如下：

所述控制器删除第三小颗粒存储单元上的第三表项，所述第三小颗粒存储单元位于所述第一内存包括的第四物理块上，所述第四物理块为所述第一内存包括的各个物理块中的任意一个，所述第三小颗粒存储单元为对所述第四物理块划分得到的多个小颗粒存储单元中的任意一个。

在第一种情况下，删除了所述第三表项后的第三小颗粒存储单元未被任何表项占用、且删除所述第三表项后的所述第四物理块上还保存有与所述第三表项属于同一类型的其它表项、并保存有第三类型的表项，其中，第三类型不同于所述第三表项所属的类型。由于所述第四物理块上还保存有与删除的第三表项属于同一类型的其它表项，因此所述第三表项的删除并不会释放带宽，为了防止从所述第二内存移动的表项会占用所述第四物理块的剩余带宽，影响所述第四物理块内其它表项的处理速度，控制器可以指示所述转发设备将所述第二内存中保存的所述第三类型的表项从所述第二内存的一个小颗粒存储单元移动到所述第三小颗粒存储单元。例如，某片内内存的一个物理块上，小颗粒存储单元1和小颗粒存储单元2用于存储A类型的表项，小颗粒存储单元3用于存储B类型的表项，小颗粒存储单元4用于存储C类型的表项，当清空了小颗粒存储单元1内的表项数据后，由于该物理块上的小颗粒存储单元2仍保存着A类型的表项，因此A类型的表项仍占用着该物理块的一部分带宽，转发设备从片外内存搬移表项数据至该小颗粒存储单元1时，可以选择从片外内存搬移B类型的表项或C类型的表项，较佳的，可以选择B类型和C类型中优先级较高的一个类型的表项搬移至该小颗粒存储单元1中。

在第二种情况下，删除了所述第三表项后的所述第四物理块上未保存有与所述第三表项属于同一类型的其它表项，这种情况下，所述第三表项的删除可以释放一部分带宽。因此，所述控制器可以指示所述转发设备将所述第二内存中保存的优先级最高的表项从所述第二内存的一个小颗粒存储单元移动到所述第三小颗粒存储单元。例如，某片内内存的一个物理块上只有一个小颗粒存储单元1用于存储A类型的表项，当清空了该小颗粒存储单元1内的表项数据后，可以回收所述A类型的表项占用的带宽，转发设备可以从片外内存中选择一个存储有优先级最高的表项的小颗粒存储单元2，将该小颗粒存储单元2内的表项搬移至该清空的小颗粒存储单元1中。

可选的，为了增加表项的存储速度，控制器还可以为常用类型的表项预留一个小颗粒存储单元，或是在确定出一个用于存储常用类型的表项的小颗粒存储单元的剩余空间小于设定阈值时，提前申请一个小颗粒存储单元。需要注意的是，这里预留或提前申请的小颗粒存储单元专门用于存储所述常用类型的表项，不允许被其他类型的表项所占用。

为了实现上述表项保存方法，控制器可以预先维护一张表项属性表，用于描述各类型表项的带宽需求和优先级。如下表2所示，为一表项属性表的示例。

表2表项属性表

其中，各类型表项的优先级可以根据各类型表项的使用频率设置，例如，若X类型的表项在所有业务中都会使用到，则可以将X类型的表项的优先级设为最高；若Y类型的表项在多个业务中都会使用到，则可以将Y类型的表项的优先级设为次高；若Z类型的表项只在特定的一个业务中会使用到，则可以将Z类型的表项的优先级设为最低。

控制器还可以基于每个物理块的状态维护一张物理块属性表，用于管理每个物理块的剩余带宽和剩余空间。例如，假设某片内内存包括A、B、C三个物理块，控制器可以维护3张物理块管理表，分别用于管理A物理块、B物理块和C物理块的剩余带宽和剩余空间。如下表3所示，物理块属性表可以包括以下属性：

表3物理块属性表

其中，表3中UsedMem和FreeMem这两个属性可以用于管理小颗粒存储单元的申请和释放。例如，步骤103中控制器可以根据第一物理块的物理块管理表中的FreeMem属性，来判断所述第一物理块是否还有剩余空间。

MemBandwidth这个属性可以用于管理物理块的剩余带宽。例如，步骤103中控制器可以根据第一物理块的物理块管理表中的MemBandwidth属性，来判断所述第一物理块的剩余带宽是否足够。

其中，剩余带宽可以是测量得到的物理块的实时剩余带宽，也可以是根据物理块理论上的初始带宽和该物理块内存储的各表项理论上的消耗带宽计算得到的估计剩余带宽。每个物理块理论上的初始带宽与内存带宽以及内存包括的物理块的数量有关，例如，假设片内内存的带宽为3吉比特每秒(单位：Gbit/s)，片内内存一共包括3个物理块，那么每个物理块理论上的初始带宽为1Gbit/s，当其中一个A物理块分配了一个小颗粒存储单元用于存储B类型的表项后，假设B类型的表项理论上的消耗带宽为0.8Gbit/s，那么可以计算得到A物理块的剩余带宽为0.2Gbit/s，若A物理块继续分配新的小颗粒存储单元用于存储B类型的表项，A物理块的剩余带宽不变仍为0.2Gbit/s，若A物理块分配新的小颗粒存储单元用于存储C类型的表项，那么C类型的表项理论上的消耗带宽需不大于0.2Gbit/s。

控制器还可以维护地址映射表，用于管理所有分配出去的小颗粒存储单元的段地址。所述地址映射表可以将[表类型，表索引]作为每个表项的段地址的索引，实现每个表项与段地址的一对一的映射关系。例如，每个类型的表项可以对应一张地址映射表，控制器在确定了某个表项的存储位置后，可以根据该表项的类型查找到对应的地址映射表，然后根据该表项的索引在该对应的地址映射表中的对应位置写入用于存储该表项的小颗粒存储单元的段地址。相应的，转发设备可以根据表项的表类型和表索引查询地址映射表直接得到表项所在的小颗粒存储单元的段地址，通过段地址找到存储该表项的小颗粒存储单元，然后根据表项的表索引得到表项的偏移量，通过偏移得到该表项在该小颗粒存储单元内的实际地址。

或者，所述地址映射表也可以将[地址映射表标识(ID)，表索引]作为每个小颗粒存储单元的段地址的索引，实现每个小颗粒存储单元与段地址的一对一的映射关系。例如，控制器可以预先规划好各个类型的表项对应的地址映射表的ID，ID的取值可以是1、2、3……等。每张地址映射表包括若干单元，每个单元用于存储一个小颗粒存储单元的段地址，每个单元的位宽可以是转发设备上所有类型表项的理论表位宽中的最大值，例如，共有A、B两种类型的表项，A类型表项的理论表位宽为64bit，B类型表项的理论表位宽为128bit，那么可以将地址映射表的每个单元的位宽设定为128bit。每张地址映射表的首地址即是：地址映射表的ID*地址映射表包括的单元*地址映射表每个单元的位宽/小颗粒存储单元的大小N。

举例来说，假设A类型的表项和B类型的表项共用一张地址映射表，该地址映射表的ID为M，A类型表项的规格是1024个，A类型表项的理论表位宽是64bit，B类型表项的规格是2*1024个，B类型表项的理论表位宽为128bit，每个小颗粒存储单元的大小为128bit*128，那么最多需要4(即)个小颗粒存储单元用于存储A类型的表项，最多需要16(即)个小颗粒存储单元用于B类型的表项，相应的，ID为M的地址映射表中有4个单元内写的是存储A类型表项的小颗粒存储单元的段地址，有16个单元内写的是存储B类型表项的小颗粒存储单元的段地址，若该4个单元在该16单元之前，那么A类型表项在该地址映射表中对应的单元的索引为(M*4*1024*128/N)+A类型表项的索引*64/N，B类型表项在该地址映射表中对应单元的索引为(M*4*1024*128/N)+A类型表项的规格*64/N+B类型表项的索引*128/N。

这样一个小颗粒存储单元内的所有表项可以对应到同一个段地址，可以减小地址映射表占用的空间。

例如，假设每个小颗粒存储单元的大小均为128bit*128，共有大小为1Mbit*128的A类型的表项，每个段地址占用的空间为32bit，如果采用每个表项与段地址一对一映射的地址存储方式，地址映射表的大小为1M*128*32bit＝4096Mbit；如果采用每个小颗粒存储单元与段地址一对一映射的地址存储方式，地址映射表的大小为(1Mbit*128/(128bit*128))*32bit＝256Kbit，一张地址映射表的空间开销占所有A类型表项的空间开销的 $\frac{256Kbit}{1Mit*128}=\frac{1}{512}.$

当控制器申请新的小颗粒存储单元，或是指示转发设备将片内内存中的表项切换到片外内存，或是指示转发设备将片外内存中的表项切换到片内内存，都需要更新物理块属性表和地址映射表中的相关内容。

基于本申请上述提供的表项保存方法，本申请提供一种控制器20，用于实现上述表项保存方法中控制器的功能，如图2所示，控制器20包括：

划分单元201，用于将转发设备的第一内存和第二内存包括的每个物理块划分为多个小颗粒存储单元，每个小颗粒存储单元用于存储同种类型的表项；所述第一内存的带宽大于所述第二内存的带宽。

生成单元202，用于生成第一表项。

确定单元203，若所述第一内存和所述第二内存中未存储有与所述第一表项属于同一类型的表项，则用于在确定所述第一内存包括的第一物理块的剩余带宽和剩余空间不小于所述第一表项需要的带宽和空间时，在所述第一物理块中确定未被任何表项占用的第一小颗粒存储单元，所述第一物理块为所述第一内存包括的各个物理块中的一个，所述第一小颗粒存储单元为对所述第一物理块划分得到的多个小颗粒存储单元中的任意一个。

发送单元204，用于将所述第一表项发送给所述转发设备，并指示所述转发设备将所述第一表项保存到所述第一小颗粒存储单元中。

可选的，所述划分单元201在将转发设备的第一内存和第二内存包括的每个物理块划分为多个小颗粒存储单元时，具体包括：将转发设备的第一内存和第二内存包括的每个物理块划分为大小为N的多个小颗粒存储单元。

可选的，所述确定单元203还可以用于，确定在生成所述第一表项之前已生成的与所述第一表项属于同一类型的其它表项的数量m；若m＝0，则确定所述第一内存或所述第二内存中未存储有与所述第一表项属于同一类型的表项；若m≠0，则确定所述第一内存或所述第二内存中存储有与所述第一表项属于同一类型的表项。

可选的，若m≠0，且m为的整数倍，L为所述第一表项的位宽，则所述确定单元203还可以用于，在确定所述第一物理块的剩余带宽和剩余空间不小于所述第一表项需要的带宽和空间时，在所述第一物理块中确定所述第一小颗粒存储单元。

相应的，所述发送单元204还可以用于，将所述第一表项发送给所述转发设备，并指示所述转发设备将所述第一表项保存到所述第一小颗粒存储单元中。

可选的，若m不为的整数倍，则所述确定单元203还可以用于，确定存储有第二表项的第二小颗粒存储单元；所述第二表项为在所述第一表项前一个生成的、与所述第一表项属于同一类型的表项。

相应的，所述发送单元204还可以用于，将所述第一表项发送给所述转发设备，并指示所述转发设备将所述第一表项保存到所述第二小颗粒存储单元中。

可选的，若m为的整数倍，所述第一内存包括的每个物理块的剩余带宽小于所述第一表项需要的带宽；则所述确定单元203还可以用于，确定在所述第一内存包括的第二物理块上保存的第一类型的表项，以及确定所述第二物理块上用于保存所述第一类型的表项的所有小颗粒存储单元；所述第一类型的表项的优先级低于所述第一表项的优先级，所述第二物理块为所述第一内存包括的各个物理块中的任意一个。

相应的，所述发送单元204还可以用于，将所述第一表项发送给所述转发设备，并指示所述转发设备将所述所有小颗粒存储单元中保存的表项移动到所述第二内存中，以及指示所述转发设备将所述第一表项保存到所述所有小颗粒存储单元中的其中一个小颗粒存储单元中。

可选的，若m为的整数倍，所述第一内存包括的每个物理块的剩余空间小于所述第一表项需要的空间；则所述确定单元203还可以用于，确定在所述第一内存包括的第三物理块上保存的第二类型的表项，以及确定所述第三物理块上用于保存所述第二类型的表项的一个小颗粒存储单元；所述第二类型的表项的优先级低于所述第一表项的优先级，所述第三物理块为所述第一内存包括的各个物理块中的任意一个。

相应的，所述发送单元204还可以用于，将所述第一表项发送给所述转发设备，并指示所述转发设备将所述一个小颗粒存储单元中保存的表项移动到所述第二内存中，以及指示所述转发设备将所述第一表项保存到所述一个小颗粒存储单元中。

可选的，所述控制器20还可以包括：

删除单元，用于删除第三小颗粒存储单元上的第三表项，所述第三小颗粒存储单元位于所述第一内存包括的第四物理块上，所述第四物理块为所述第一内存包括的各个物理块中的任意一个，所述第三小颗粒存储单元为对所述第四物理块划分得到的多个小颗粒存储单元中的任意一个.

若删除所述第三表项后的第三小颗粒存储单元未被任何表项占用、且删除所述第三表项后的所述第四物理块上还保存有与所述第三表项属于同一类型的其它表项、并保存有第三类型的表项，则所述发送单元204还可以用于，指示所述转发设备将所述第二内存中保存的所述第三类型的表项从所述第二内存的一个小颗粒存储单元移动到所述第三小颗粒存储单元，所述第三类型与所述第三表项所属的类型为不同类型。

或者，若删除所述第三表项后的所述第四物理块上未保存有与所述第三表项属于同一类型的其它表项，则所述发送单元204还可以用于，指示所述转发设备将所述第二内存中保存的优先级最高的表项从所述第二内存的一个小颗粒存储单元移动到所述第三小颗粒存储单元。

其中，集成的单元也可以采用硬件的形式实现时，所述发送单元204、所述生成单元202、所述确定单元203和所述删除单元对应的实体硬件设备为处理器；所述发送单元204对应的实体硬件设备为通信接口。

综上所述，本申请提供的技术方案，在转发设备片内内存带宽和空间足够的情况下，让生成的表项优先占用高速的片内内存；在转发设备片内内存带宽或空间不足的情况下，优先将片内内存中优先级较低的表项切换到片外内存；在转发设备片内内存中有表项删除时，优先将片外内存中优先级较高的表项切回至片内内存，从而实现了片内内存的带宽和空间的最大利用，以及提高了转发设备整体的处理速度。此外，本申请提供的技术方案通过将片内内存和片外内存划分为多个小颗粒存储单元，每个小颗粒存储单元用于存储同一类型的表项，减小了管理资源的开销。

本领域内的技术人员应明白，本发明的实施例可提供为方法、系统、或计算机程序产品。因此，本发明可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本发明可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。

本发明是参照根据本发明实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。

这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

尽管已描述了本发明的优选实施例，但本领域内的技术人员一旦得知了基本创造性概念，则可对这些实施例作出另外的变更和修改。所以，所附权利要求意欲解释为包括优选实施例以及落入本发明范围的所有变更和修改。

显然，本领域的技术人员可以对本发明实施例进行各种改动和变型而不脱离本发明实施例的精神和范围。这样，倘若本发明实施例的这些修改和变型属于本发明权利要求及其等同技术的范围之内，则本发明也意图包含这些改动和变型在内。

Claims (12)

1.一种表项保存方法，其特征在于，包括：

控制器将转发设备的第一内存和第二内存包括的每个物理块划分为多个小颗粒存储单元，每个小颗粒存储单元用于存储同种类型的表项；所述第一内存的带宽大于所述第二内存的带宽；

所述控制器生成第一表项；

若所述第一内存和所述第二内存中未存储有与所述第一表项属于同一类型的表项，则所述控制器在确定所述第一内存包括的第一物理块的剩余带宽和剩余空间不小于所述第一表项需要的带宽和空间时，在所述第一物理块中确定未被任何表项占用的第一小颗粒存储单元，所述第一物理块为所述第一内存包括的各个物理块中的一个，所述第一小颗粒存储单元为对所述第一物理块划分得到的多个小颗粒存储单元中的任意一个；

所述控制器将所述第一表项发送给所述转发设备，并指示所述转发设备将所述第一表项保存到所述第一小颗粒存储单元中。

2.如权利要求1所述的方法，其特征在于，控制器将转发设备的第一内存和第二内存包括的每个物理块划分为多个小颗粒存储单元，包括：

控制器将转发设备的第一内存和第二内存包括的每个物理块划分为大小为N的多个小颗粒存储单元；

所述方法还包括：

所述控制器确定在生成所述第一表项之前已生成的与所述第一表项属于同一类型的其它表项的数量m；

若m≠0，则所述控制器确定所述第一内存或所述第二内存中存储有与所述第一表项属于同一类型的表项；

若m≠0，且m为的整数倍，L为所述第一表项的位宽，则所述控制器在确定所述第一物理块的剩余带宽和剩余空间不小于所述第一表项需要的带宽和空间时，在所述第一物理块中确定所述第一小颗粒存储单元；

所述控制器将所述第一表项发送给所述转发设备，并指示所述转发设备将所述第一表项保存到所述第一小颗粒存储单元中。

3.如权利要求2所述的方法，其特征在于，所述方法还包括：

若m不为的整数倍，则所述控制器确定存储有第二表项的第二小颗粒存储单元；所述第二表项为在所述第一表项前一个生成的、与所述第一表项属于同一类型的表项；

所述控制器将所述第一表项发送给所述转发设备，并指示所述转发设备将所述第一表项保存到所述第二小颗粒存储单元中。

4.如权利要求2或3所述的方法，其特征在于，所述方法还包括：

若m为的整数倍，所述第一内存包括的每个物理块的剩余带宽小于所述第一表项需要的带宽；

则所述控制器确定在所述第一内存包括的第二物理块上保存的第一类型的表项，以及确定所述第二物理块上用于保存所述第一类型的表项的所有小颗粒存储单元；所述第一类型的表项的优先级低于所述第一表项的优先级，所述第二物理块为所述第一内存包括的各个物理块中的任意一个；

所述控制器将所述第一表项发送给所述转发设备，并指示所述转发设备将所述所有小颗粒存储单元中保存的表项移动到所述第二内存中，以及指示所述转发设备将所述第一表项保存到所述所有小颗粒存储单元中的其中一个小颗粒存储单元中。

5.如权利要求2或3所述的方法，其特征在于，所述方法还包括：

若m为的整数倍，所述第一内存包括的每个物理块的剩余空间小于所述第一表项需要的空间；

则所述控制器确定在所述第一内存包括的第三物理块上保存的第二类型的表项，以及确定所述第三物理块上用于保存所述第二类型的表项的一个小颗粒存储单元；所述第二类型的表项的优先级低于所述第一表项的优先级，所述第三物理块为所述第一内存包括的各个物理块中的任意一个；

所述控制器将所述第一表项发送给所述转发设备，并指示所述转发设备将所述一个小颗粒存储单元中保存的表项移动到所述第二内存中，以及指示所述转发设备将所述第一表项保存到所述一个小颗粒存储单元中。

6.如权利要求1-5中任一项所述的方法，其特征在于，所述方法还包括：

所述控制器删除第三小颗粒存储单元上的第三表项，所述第三小颗粒存储单元位于所述第一内存包括的第四物理块上，所述第四物理块为所述第一内存包括的各个物理块中的任意一个，所述第三小颗粒存储单元为对所述第四物理块划分得到的多个小颗粒存储单元中的任意一个；

若删除所述第三表项后的第三小颗粒存储单元未被任何表项占用、且删除所述第三表项后的所述第四物理块上还保存有与所述第三表项属于同一类型的其它表项、并保存有第三类型的表项，则所述控制器指示所述转发设备将所述第二内存中保存的所述第三类型的表项从所述第二内存的一个小颗粒存储单元移动到所述第三小颗粒存储单元，所述第三类型与所述第三表项所属的类型为不同类型；或

若删除所述第三表项后的所述第四物理块上未保存有与所述第三表项属于同一类型的其它表项，则所述控制器指示所述转发设备将所述第二内存中保存的优先级最高的表项从所述第二内存的一个小颗粒存储单元移动到所述第三小颗粒存储单元。

7.一种控制器，其特征在于，包括：

划分单元，用于将转发设备的第一内存和第二内存包括的每个物理块划分为多个小颗粒存储单元，每个小颗粒存储单元用于存储同种类型的表项；所述第一内存的带宽大于所述第二内存的带宽；

生成单元，用于生成第一表项；

确定单元，若所述第一内存和所述第二内存中未存储有与所述第一表项属于同一类型的表项，则用于在确定所述第一内存包括的第一物理块的剩余带宽和剩余空间不小于所述第一表项需要的带宽和空间时，在所述第一物理块中确定未被任何表项占用的第一小颗粒存储单元，所述第一物理块为所述第一内存包括的各个物理块中的一个，所述第一小颗粒存储单元为对所述第一物理块划分得到的多个小颗粒存储单元中的任意一个；

发送单元，用于将所述第一表项发送给所述转发设备，并指示所述转发设备将所述第一表项保存到所述第一小颗粒存储单元中。

8.如权利要求7所述的控制器，其特征在于，所述划分单元，在将转发设备的第一内存和第二内存包括的每个物理块划分为多个小颗粒存储单元时，具体包括：

将转发设备的第一内存和第二内存包括的每个物理块划分为大小为N的多个小颗粒存储单元；

所述确定单元还用于：

确定在生成所述第一表项之前已生成的与所述第一表项属于同一类型的其它表项的数量m；

若m≠0，则确定所述第一内存或所述第二内存中存储有与所述第一表项属于同一类型的表项；

若m≠0，且m为的整数倍，L为所述第一表项的位宽，则在确定所述第一物理块的剩余带宽和剩余空间不小于所述第一表项需要的带宽和空间时，在所述第一物理块中确定所述第一小颗粒存储单元；

所述发送单元还用于，将所述第一表项发送给所述转发设备，并指示所述转发设备将所述第一表项保存到所述第一小颗粒存储单元中。

9.如权利要求8所述的控制器，其特征在于，所述确定单元还用于：

若m不为的整数倍，则确定存储有第二表项的第二小颗粒存储单元；所述第二表项为在所述第一表项前一个生成的、与所述第一表项属于同一类型的表项；

所述发送单元还用于，将所述第一表项发送给所述转发设备，并指示所述转发设备将所述第一表项保存到所述第二小颗粒存储单元中。

10.如权利要求8或9所述的控制器，其特征在于，所述确定单元还用于：

若m为的整数倍，所述第一内存包括的每个物理块的剩余带宽小于所述第一表项需要的带宽；

则确定在所述第一内存包括的第二物理块上保存的第一类型的表项，以及确定所述第二物理块上用于保存所述第一类型的表项的所有小颗粒存储单元；所述第一类型的表项的优先级低于所述第一表项的优先级，所述第二物理块为所述第一内存包括的各个物理块中的任意一个；

所述发送单元还用于，将所述第一表项发送给所述转发设备，并指示所述转发设备将所述所有小颗粒存储单元中保存的表项移动到所述第二内存中，以及指示所述转发设备将所述第一表项保存到所述所有小颗粒存储单元中的其中一个小颗粒存储单元中。

11.如权利要求8或9所述的控制器，其特征在于，所述确定单元还用于：

若m为的整数倍，所述第一内存包括的每个物理块的剩余空间小于所述第一表项需要的空间；

则确定在所述第一内存包括的第三物理块上保存的第二类型的表项，以及确定所述第三物理块上用于保存所述第二类型的表项的一个小颗粒存储单元；所述第二类型的表项的优先级低于所述第一表项的优先级，所述第三物理块为所述第一内存包括的各个物理块中的任意一个；

所述发送单元还用于，将所述第一表项发送给所述转发设备，并指示所述转发设备将所述一个小颗粒存储单元中保存的表项移动到所述第二内存中，以及指示所述转发设备将所述第一表项保存到所述一个小颗粒存储单元中。

12.如权利要求7-11中任一项所述的控制器，其特征在于，所述控制器还包括：

删除单元，用于删除第三小颗粒存储单元上的第三表项，所述第三小颗粒存储单元位于所述第一内存包括的第四物理块上，所述第四物理块为所述第一内存包括的各个物理块中的任意一个，所述第三小颗粒存储单元为对所述第四物理块划分得到的多个小颗粒存储单元中的任意一个；

所述发送单元还用于，若删除所述第三表项后的第三小颗粒存储单元未被任何表项占用、且删除所述第三表项后的所述第四物理块上还保存有与所述第三表项属于同一类型的其它表项、并保存有第三类型的表项，则指示所述转发设备将所述第二内存中保存的所述第三类型的表项从所述第二内存的一个小颗粒存储单元移动到所述第三小颗粒存储单元，所述第三类型与所述第三表项所属的类型为不同类型；或

所述发送单元还用于，若删除所述第三表项后的所述第四物理块上未保存有与所述第三表项属于同一类型的其它表项，则指示所述转发设备将所述第二内存中保存的优先级最高的表项从所述第二内存的一个小颗粒存储单元移动到所述第三小颗粒存储单元。