CN104468357B - 流表的多级化方法、多级流表处理方法及装置 - Google Patents

Abstract

本发明公开一种流表的多级化方法、多级流表处理方法及装置；多级化方法包括：第一流表和第二流表；第一流表保存有至少一种逻辑规则以及该至少一种逻辑规则对应的所有转发动作，第二流表保存有一种逻辑规则以及该一种逻辑规则的所有转发动作，第一流表以及第二流表正交组成TCAM流表；该方法包括：生成第三流表；将第一流表中的目标逻辑规则和该目标逻辑规则对应的转发动作分离至第三流表，使第一流表、第二流表、第三流表正交后组成TCAM流表，之后继续生成新的流表，直至流表数量达到预设上限。本方案将TCAM流表中的多种逻辑规则进行正交分解，使新生成的每个流表保存一种分离的逻辑规则，从而有效地节省TCAM的存储空间。

Description

流表的多级化方法、多级流表处理方法及装置

技术领域

本发明涉及网络领域，提供一种流表的多级化方法、多级流表处理方法及装置。

背景技术

目前互联网发展迅速，其应用规模的庞大及其地位的重要性，远远超出了设计者们的想象，而现在的互联网主要有以下弊端：特定的范围内没有统一的管理、网络转发机制与策略单一、运营商难以最大限度优化自身网络、以及传统交换机用于转发的功能和协议多且杂，很难配置，系统容易出错等问题。为应对上述弊端，人们提出了Openflow交换机，其将传统交换机上的报文转发和转发策略分离开来，采用专门的一台转发器通过网线和交换机连接。这样原来同在一台交换机设备上的报文转发功能（硬件芯片实现）和报文转发策略（各种软件协议）就被分开到了不同的硬件设备上。而一台转发器还可以控制多台Openflow交换机，从而实现了统一的转发控制端，更有效地控制了网络。

通常的Openflow交换机上的流表是通过把流表配置到TCAM（三态内容寻址存储器）硬件上来实现的。其中，TCAM主要用于快速查找ACL、路由等表项。

现有技术中，Openflow交换机只有一个TCAM流表，假设Openflow交换机需要根据数据包的目的IP字段定义M种IP转发规则，同时要根据数据包的TCP字段进行N种端口过滤规则，那么该TCAM流表就需要有M×N条表项，因此过多占用了TCAM的存储空间。

发明内容

本发明要解决的技术问题是提供一种实现流表多级化的方案以及针对多级流表的处理方案，能够有效地节省TCAM的存储空间，进而节约Openflow交换机的制造成本。

为解决上述技术问题，本发明的实施例提供一种流表的多级化方法，包括：第一流表以及第二流表；所述第一流表保存有至少一种逻辑规则以及与该至少一种逻辑规则对应的所有转发动作，所述第二流表保存有一种逻辑规则以及该一种逻辑规则的所有转发动作，所述第一流表以及第二流表正交组成TCAM流表；其中，所述方法包括：

生成第三流表；

将所述第一流表中的目标逻辑规则以及该目标逻辑规则对应的转发动作分离至所述第三流表，使得所述第一流表、第二流表以及第三流表正交后组成所述TCAM流表，之后继续生成新的流表，直至流表数量达到预设上限。

其中，所述第一流表以及第二流表中的逻辑规则具体包括有一个或多个匹配域，每个匹配域对应有一个或多个转发动作；

将所述第一流表中的目标逻辑规则以及该目标逻辑规则对应的所有转发动作分离至所述第三流表的步骤包括：

计算第一流表中所有逻辑规则的映射收益，将映射收益最大的逻辑规则确定为目标逻辑规则；

将所述第一流表中的目标逻辑规则以及该目标逻辑规则对应的所有转发动作分离至所述第三流表；其中，目标逻辑规则的同一个匹配域不重复保存在所述第三流表中。

其中，所述第一流表配有第一跳转流条目，用于存储第一流表中每个转发动作的跳转地址，所述第二流表配有第二跳转流目条，用于存储第二流表中每个转发动作的跳转地址；其中，所述第一跳转流条目的跳转地址为第二流表或转发器，所述第二跳转流条目的跳转地址为转发器；

在将所述第一流表中的目标逻辑规则以及该目标逻辑规则对应的所有转发动作分离至所述第三流表后，所述方法还包括：

为所述第三流表配置第三跳转流条目；

为所述第三流表中每个转发动作配置跳转地址；

将所述第三流表中每个转发动作的跳转地址保存至所述第三跳转流条目；

更新所述第一跳转流条目以及第二跳转流条目中的跳转地址。

其中，

为所述第三流表中每个转发动作配置跳转地址的步骤包括：

将所述第三流表中每个转发动作的跳转地址配置为转发器；

更新所述第一跳转流条目以及第二跳转流条目中的跳转地址的步骤包括：

更新所述第一跳转流条目以及第二跳转流条目中的跳转地址，使所述第一跳转流条目的跳转地址为第二流表或第三流表或转发器，并使所述第二跳转流条目的跳转地址为第三流表或转发器。

本发明的实施例还提供一种多级流表的处理方法，所述多级流表按有效位进行排序且能够正交组成一个三态内容寻址存储器TCAM流表；其中，位于第一级的第一流表保存有至少一种逻辑规则以及与该至少一种逻辑规则对应的所有转发动作，其余每个流表均只保存有一种逻辑规则以及该一种逻辑规则的所有转发动作；所述方法包括：

确定目标报文的逻辑规则；

按所述有效位的顺序分别将每个流表所保存逻辑规则与目标报文的逻辑规则进行匹配，得到每个流表与该匹配相符的转发动作集合；

对所有流表的转发动作集合取交集，得到每个转发动作集合共同的转发动作；

根据每个转发动作集合共同的转发动作转发所述目标报文。

其中，每个流表所保存的逻辑规则具体包括有一个或多个匹配域，每个匹配域对应有一个或多个转发动作；所述多级流表中的每个流表还分别设有一个跳转流条目，用于存储其所对应的流表中每个转发动作的跳转地址，从而能够在得到第一流表的转发动作集合后，根据该转发动作集合中每个转发动作所对应的跳转地址向下级流表进行跳转。

其中，所述方法还包括：

当需要对所述多级流表的排序进行变化时，将需要改变的流表以及该流表对应的所有转发动作进行调换，并更新所有流表的跳转流条目。

其中，所述方法包括：

当需要替换掉所述多级流表中的目标流表时，生成一替换流表，在所述替换流表中保存需要替换的逻辑规则，并将所述目标流表替换成所述替换流表，之后配置该替换流表中逻辑规则的转发动作，并更新所有流表的跳转流条目。

本发明的实施例还提供一种流表的多级化装置包括：第一流表以及第二流表；所述第一流表保存有至少一种逻辑规则以及与该至少一种逻辑规则对应的所有转发动作，所述第二流表保存有一种逻辑规则以及该一种逻辑规则的所有转发动作，所述第一流表以及第二流表正交组成TCAM流表；其中，所述装置包括：

生成模块，用于生成第三流表；

分离模块，用于将所述第一流表中的目标逻辑规则以及该目标逻辑规则对应的转发动作分离至所述第三流表，使得所述第一流表、第二流表以及第三流表正交后组成所述TCAM流表，之后继续生成新的流表，直至流表数量达到预设上限。

其中，所述第一流表以及第二流表中的逻辑规则具体包括有一个或多个匹配域，每个匹配域对应有一个或多个转发动作；

所述分离模块包括：

计算子模块，用于计算第一流表中所有逻辑规则的映射收益，将映射收益最大的逻辑规则确定为目标逻辑规则；

分离子模块，用于将所述第一流表中的目标逻辑规则以及该目标逻辑规则对应的转发动作分离至所述第三流表；其中，目标逻辑规则的同一个匹配域不重复保存在所述第三流表中。

其中，所述第一流表配有第一跳转流条目，用于存储第一流表中每个转发动作的跳转地址，所述第二流表配有第二跳转流目条，用于存储第二流表中每个转发动作的跳转地址；其中，所述第一跳转流条目的跳转地址为第二流表或转发器，所述第二跳转流条目的跳转地址为转发器；

所述装置还包括：

第一配置模块，用于在所述分离模块将所述第一流表中的目标逻辑规则以及该目标逻辑规则对应的所有转发动作分离至所述第三流表后，为所述第三流表配置第三跳转流条目；

第二配置模块，用于为所述第三流表中每个转发动作配置跳转地址；

保存模块，用于将所述第三流表中每个转发动作的跳转地址保存至所述第三跳转流条目；

更新模块，用于更新所述第一跳转流条目以及第二跳转流条目中的跳转地址。

其中，其特征在于，

所述第二配置模块具体用于：将所述第三流表中每个转发动作的跳转地址配置为转发器；

所述更新模块具体用于：更新所述第一跳转流条目以及第二跳转流条目中的跳转地址，使所述第一跳转流条目的跳转地址为第二流表或第三流表或转发器，并使所述第二跳转流条目的跳转地址为第三流表或转发器。

本发明的实施例还提供一种多级流表的处理装置，其特征在于，所述多级流表按有效位进行排序且能够正交组成一个三态内容寻址存储器TCAM流表；其中，位于第一级的第一流表保存有至少一种逻辑规则以及与该至少一种逻辑规则对应的所有转发动作，其余每个流表均只保存有一种逻辑规则以及该一种逻辑规则的所有转发动作；所述装置包括：

确定模块，用于确定目标报文的逻辑规则；

匹配模块，用于按所述有效位的顺序分别将每个流表所保存逻辑规则与目标报文的逻辑规则进行匹配，得到每个流表与该匹配相符的转发动作集合；

处理模块，用于对所有流表的转发动作集合取交集，得到每个转发动作集合共同的转发动作；

转发模块，用于根据每个转发动作集合共同的转发动作转发所述目标报文。

其中，每个流表所保存的逻辑规则具体包括有一个或多个匹配域，每个匹配域对应一个或多个转发动作；所述多级流表中的每个流表还分别设有一个跳转流条目，用于存储其所对应的流表中每个转发动作的跳转地址，从而能够使匹配模块在得到第一流表的转发动作集合后，根据该转发动作集合中每个转发动作所对应的跳转地址向下级流表进行跳转。

其中，所述装置还包括：

流表调换模块，用于当需要对所述多级流表的排序进行变化时，将需要改变的流表以及该流表对应的所有转发动作进行调换，并更新所有流表的跳转流条目。

其中，所述装置包括：

流表替换模块，用于当需要替换掉所述多级流表中的目标流表时，生成一替换流表，在所述替换流表中保存需要替换的逻辑规则，并将所述目标流表替换成所述替换流表，之后配置该替换流表中逻辑规则的转发动作，并更新所有流表的跳转流条目。

本发明的方案所能带来的有益效果：

本发明的方案将Openflow交换机维护的TCAM流表中的多种逻辑规则逐一分离出来，使得新生成的每个流表保存一种分离的逻辑规则，从而对TCAM流表中的逻辑规则进行正交分解，因此能够有效地节省TCAM的存储空间，进而节约Openflow交换机的制造成本。

附图说明

图1为本发明中流表的多级化方法的步骤示意图；

图2为本发明中现有TCAM流表的具体示意图；

图3-图5为本发明中流表的多级化方法的具体实施示意图；

图6为本发明中多级流表的处理方法的步骤示意图；

图7为本发明中流表的多级化装置的结构示意图；

图8为本发明中多级流表的处理装置的结构示意图。

具体实施方式

为使本发明要解决的技术问题、技术方案和优点更加清楚，下面将结合附图及具体实施例进行详细描述。

一种流表的多级化方法，包括：第一流表以及第二流表；所述第一流表保存有至少一种逻辑规则以及与该至少一种逻辑规则对应的所有转发动作，所述第二流表保存有一种逻辑规则以及该一种逻辑规则的所有转发动作，所述第一流表以及第二流表正交组成TCAM流表；其中，所述方法包括：

步骤1，生成第三流表；

步骤2，将所述第一流表中的目标逻辑规则以及该目标逻辑规则对应的转发动作分离至所述第三流表，使得所述第一流表、第二流表以及第三流表正交后组成所述TCAM流表，之后继续生成新的流表，直至流表数量达到预设上限。

本方法将Openflow交换机维护的TCAM流表中的多种逻辑规则逐一分离出来，使得新生成的每个流表保存一种分离的逻辑规则，从而对TCAM流表中的逻辑规则进行正交分解，因此能够有效地节省TCAM的存储空间，进而节约Openflow交换机的制造成本。

此外，在上述实施例的基础之上，本发明还提供了一种具体实现TCAM流划分成多流表的方法，其中，所述第一流表以及第二流表中的逻辑规则具体包括有一个或多个匹配域，每个匹配域对应一个或多个转发动作；步骤2包括：

步骤21，计算第一流表中所有逻辑规则的映射收益，将映射收益最大的逻辑规则确定为目标逻辑规则；

步骤22，将所述第一流表中的目标逻辑规则以及该目标逻辑规则对应的转发动作分离至所述第三流表；其中，目标逻辑规则的同一个匹配域不重复保存在所述第三流表中。

如图2所示，对于目前的TCAM流表来说，其查找字段即为上文所述的逻辑规则，而一个查找字段中的某一匹配域（即一具体的地址）可能对应多种转发动作（如图2中查找字段Eth type中的匹配域0×8100），因此TCAM流表就会建立更多的表项用于重复保存匹配域（同一种匹配域，其对应几种转发动作，就在TCAM流表重复保存了几遍）；此外，如果生成流表过多，其流表间的跳转时间就会越长，致使报文转发的速度下降，因此基于上文中提到的重复的匹配域只保存一个，本实施例在流表数量有限的情况下，从TCAM流表中分离出映射收益（在一种查找字段中，其匹配域的重复程度即为该查找字段的映射收益）大的逻辑规则，从而更加合理地节约了TCAM流表的资源。

此外，为了保证流表之间更加灵活的进行跳转，在本发明的上述实施例中，所述第一流表配有第一跳转流条目，用于存储第一流表中每个转发动作的跳转地址，所述第二流表配有第二跳转流目条，用于存储第二流表中每个转发动作的跳转地址；其中，所述第一跳转流条目的跳转地址为第二流表或转发器，所述第二跳转流条目的跳转地址为转发器；所述流表的多级化方法还包括：

步骤3，为所述第三流表配置第三跳转流条目；

步骤4，为所述第三流表中每个转发动作配置跳转地址；

步骤5，将所述第三流表中每个转发动作的跳转地址保存至所述第三跳转流条目；

步骤6，更新所述第一跳转流条目以及第二跳转流条目中的跳转地址。

本实施例为每个流表引入了跳转地址的跳转流条目，从而直接根据跳转流条目进行跳转地址，无需在获取每个一个流表一个流表地全部进行游历以获取转发动作，从而减少了报文转发所需要的时间。

具体地，在本发明的上述实施例中，步骤3包括：

将所述第三流表中每个转发动作的跳转地址配置为转发器；

步骤6包括：

更新所述第一跳转流条目以及第二跳转流条目中的跳转地址，使所述第一跳转流条目的跳转地址为第二流表或第三流表或转发器，并使所述第二跳转流条目的跳转地址为第三流表或转发器。

本实施例将最后一个流表（即当前的第三流表）中所有转发动作的跳转地址设置为转发器，在经过最后一流表后可直接通过转发器来转发报文，由于之后每添加一个新的流表都会使的最后一个流表发生变化，因此需要对之前的第一流表以及第二流表的跳转流条目进行更新。

下面对上述流表的多级化方法的具体实施进行详细描述：

如图3所示，假设原始的TCAM流表具有10个表项的流表，每个表项对应3种逻辑规则（即查找字段Eth Dst\IP Src\IP Dst），TCAM流表中每个表项对应有其各自的转发动作即ACTION表（转发器）中的转发动作ACT1-ACT10。

第一步，按照其优先级进行表项排序，这里按照优先级的大小顺序先后标记为R1到R10（即标号较小的表项具有较高的优先级）；其中R1到R10分别对应转发动作ACT1-ACT10。

第二步，计所有逻辑规则的映射增益，根据图中实例来看，查找字段Eth Dst具有最大的映射增益（即匹配域重复的程度最高）；

第三步，如图4所示，生成第二流表，将第一流表（原TCAM流表）中的Eth Dst（携带有其对应的转发动作即规则R1-R4和R5-R10）分离至第二流表（重复的匹配域至保存一个），并维护一个J1变量（即上文所述的跳转流条目）来指示第一流表的跳转地址，其中，J1的取值，由Eth Dst的匹配域来决定，由于Eth Dst的R5-R10均为任意匹配“*”（“*”即符合所有的数值），所以在报文转发过程中，如果通过流表1确定出R5-R10对应的转发动作，那么就无需在第二流表中进行查找，可以直接跳转到action表，而具体的匹配域如00：FF则在J1对应为2（位数为2的第二流表）。

之后将为第二流表建立一个J2变量（即第二流表的跳转流条目），由于此时的第二流表为最后一个流表，J2对应的匹配域的跳转地址都可指向3(3对应于ACTION表)。

第四步，根据映射增益，逻辑规则IP Dst具有次高的增益值，与步骤三类似，生成第三流表，将第一流标中的IP Dst分离至第三流表，此后为第三流表配置跳转流条目J3，由于此时第三流表为最后一个流表，将IP Dst的匹配域对应J3设置为4，并更新J1以及J2，最终得到如图5所示的多级流表。例如：Eth Dst中的R5对应为任意匹配“*”，而IP Dst的R5对应为10*，因此10*并不能适用于任意的数值，此时J1对应的R5的跳转地址应该略过第二流表，到达第三流表，由于第三流表对应的位数为3，因此R5在J1中依然为3，但与原先的3代表的意义有所不同（原先的3表示跳转至ACTION表）；而R6、R8、R10在Eth Dst、以及IP Dst均为任意匹配“*”，因此在J1中对应为4（即直接跳转到ACTION表）；相对于J2的匹配域，在IP Dst中R2为任意匹配“*”，因此将R2对应的J2改为4（即跳过第三流表后，来到ACTION表）。

需要指出的是，本实施例将查找字段定义为逻辑规则，只是其中的一种优选方式，对于原TCAM流表，其每个纵向的表项以及每个横向的表项都可以视作为一种逻辑规则，进行分离，其分离原理与本实施例所提出的方法一样，在此不做赘述。此外，对于原TCAM流表保存了多种逻辑规则的情况，可权衡报文转发所需的时间，来设定相应的需要分离逻辑规则的数量。

此外，本发明的实施例还提供一种多级流表的处理方法，所述多级流表按有效位进行排序且能够正交组成一个三态内容寻址存储器TCAM流表；其中，位于第一级的第一流表保存有至少一种逻辑规则以及与该至少一种逻辑规则对应的所有转发动作，其余每个流表均只保存有一种逻辑规则以及该一种逻辑规则的所有转发动作；所述方法包括：

步骤61，确定目标报文的逻辑规则；

步骤62，按所述有效位的顺序分别将每个流表所保存逻辑规则与目标报文的逻辑规则进行匹配，得到每个流表与该匹配相符的转发动作集合；

步骤63，对所有流表的转发动作集合取交集，得到每个转发动作集合共同的转发动作；

步骤64，根据每个转发动作集合共同的转发动作转发所述目标报文。

上述实施例提供了一种多级流表的处理方法，根据每个流表中的逻辑规则获取对应的具有一个或多个转发动作的转发动作集合，并对每个流表中这些获取到的转发动作集合取交集，从而得到符合所有流表保存的逻辑规则对应的转发动作，从而完成报文的转发。

此外，在本发明的上述实施例中，每个流表所保存的逻辑规则具体包括有一个或多个匹配域，每个匹配域对应有一个或多个转发动作；所述多级流表中的每个流表还分别设有一个跳转流条目，用于存储其所对应的流表中每个转发动作的跳转地址，从而能够在得到第一流表的转发动作集合后，根据该转发动作集合中每个转发动作所对应的跳转地址向下级流表进行跳转。

本实施例为每个流表的转发动作保存了相应的跳转地址，从而直接根据跳转地址进行向下游流表进行跳转，无需在一个流表一个流表地全部进行游历以获取转发动作，从而减少了报文转发所需要的时间。

此外，在本发明的上述实施例中，所述方法还包括：

步骤65，当需要对所述多级流表的排序进行变化时，将需要改变的流表以及该流表对应的所有转发动作进行调换，并更新所有流表的跳转流条目。

此外，为了对流表进行更改，在本发明的上述实施例中，所述方法还包括：

步骤66，当需要替换掉所述多级流表中的目标流表时，生成一替换流表，在所述替换流表中保存需要替换的逻辑规则，并将所述目标流表替换成所述替换流表，之后配置该替换流表中逻辑规则的转发动作，并更新所有流表的跳转流条目。

下面对上述多级流表的处理方法的具体实施过程进行详细描述：

<报文转发过程>

同样如图5所示的多级流表，假设目标报文从输入端口接收，其三个数据域(即该目标报文的逻辑规则)分别为“00：1F”，“0010*”和“1110*”。三个数据域分别被提取并发送到三个流表进行查找，在第一流表中得到匹配域对应的表项为R1，R2，R3，R4，R9的转发动作集合（如R1中的001*，其*可对应任意数值，当*为0*时，此时第一流表中R1即为0010*，符合目标报文的数据域，），之后R1，R2，R3，R4，R9对应的J₁进行跳转，最终从第二个流表中找出符合的的转发动作集合：R3以及“*”对应的R5-R10，从第三个流表中找出符合的的转发动作集合：R3，R4，R7，R9和“*”对应的R2，R6，R8，R10。之后对每个流表获取的转发动作集合取交集，最终确定出R3和R4符合所有流表中的逻辑规则，由于图5所示的多级流表中每个表项进行了优先级排序，所以这里可以确定出R3对应的转发动作优先级最高，最终执行R3对应的转发动作执行报文转发操作。

<流表改变过程>

流表改变过程分为两种情况：第一种情况下，只是多级流表的排序发生改变，假设有3个流表，从1到4分别表示3个流表和一个action表。更新流程有三步：第一步，将所有流表中的跳转流目条都恢复为默认值，即没有跳转地址；第二步，将流表互换。第三步，更新每个流表对应的跳转流目条中的跳转地址，其更新方法与上文所述的方法一致，在此不做赘述。

第二种情况是流表中的逻辑规则发生了变化，比如第三流表保存的逻辑规则需要改变，可生成一个新的流表作为替换流表，保存需要改变的逻辑规则至替换流表，将第三流表替换成所述替换流表，之后更新所有流表的跳转流条目即可实现第三流表的替换工作。

此外，本发明还提供一种流表的多级化装置，包括：第一流表以及第二流表；所述第一流表保存有至少一种逻辑规则以及与该至少一种逻辑规则对应的所有转发动作，所述第二流表保存有一种逻辑规则以及该一种逻辑规则的所有转发动作，所述第一流表以及第二流表正交组成TCAM流表；其中，如图7所示，所述装置包括：

所述装置包括：

生成模块，用于生成第三流表；

分离模块，用于将所述第一流表中的目标逻辑规则以及该目标逻辑规则对应的转发动作分离至所述第三流表，使得所述第一流表、第二流表以及第三流表正交后组成所述TCAM流表，之后继续生成新的流表，直至流表数量达到预设上限。

本装置将Openflow交换机维护的TCAM流表中的多种逻辑规则逐一分离出来，使得新生成的每个流表保存一种分离的逻辑规则，从而对TCAM流表中的逻辑规则进行正交分解，因此能够有效抵节省TCAM的存储空间，进而节约Openflow交换机的制造成本。

其中，在本发明的上述实施例中，所述第一流表以及第二流表中的逻辑规则具体包括有多个匹配域，每个匹配域对应有一个或多个转发动作；所述分离模块包括：

计算子模块，用于计算第一流表中所有逻辑规则的映射收益，将映射收益最大的逻辑规则确定为目标逻辑规则；

分离子模块，用于将所述第一流表中的目标逻辑规则以及该目标逻辑规则对应的转发动作分离至所述第三流表；其中，目标逻辑规则的同一个匹配域不重复保存在所述第三流表中。

其中，在本发明的上述实施例中，所述第一流表配有第一跳转流条目，用于存储第一流表中每个转发动作的跳转地址，所述第二流表配有第二跳转流目条，用于存储第二流表中每个转发动作的跳转地址；其中，所述第一跳转流条目的跳转地址为第二流表或转发器，所述第二跳转流条目的跳转地址为转发器；

所述装置还包括：

第一配置模块，用于在所述分离模块将所述第一流表中的目标逻辑规则以及该目标逻辑规则对应的所有转发动作分离至所述第三流表后，为所述第三流表配置第三跳转流条目；

第二配置模块，用于为所述第三流表中每个转发动作配置跳转地址；

保存模块，用于将所述第三流表中每个转发动作的跳转地址保存至所述第三跳转流条目；

更新模块，用于更新所述第一跳转流条目以及第二跳转流条目中的跳转地址。

其中，在本发明的上述实施例中，

所述第二配置模块具体用于：将所述第三流表中每个转发动作的跳转地址配置为转发器；

所述更新模块具体用于：更新所述第一跳转流条目以及第二跳转流条目中的跳转地址，使所述第一跳转流条目的跳转地址为第二流表或第三流表或转发器，并使所述第二跳转流条目的跳转地址为第三流表或转发器。

显然，本实施例的装置与本发明中一种流表的多级化方法相对应，该流表的多级化方法所能达到的技术效果，本实施例的装置也同样能够达到。

此外，本发明的实施例一种多级流表的处理装置，所述多级流表按有效位进行排序且能够正交组成一个三态内容寻址存储器TCAM流表；其中，位于第一级的第一流表保存有至少一种逻辑规则以及与该至少一种逻辑规则对应的所有转发动作，其余每个流表均只保存有一种逻辑规则以及该一种逻辑规则的所有转发动作；如图8所示，所述装置包括：

确定模块，用于确定目标报文的逻辑规则；

匹配模块，用于按所述有效位的顺序分别将每个流表所保存逻辑规则与目标报文的逻辑规则进行匹配，得到每个流表与该匹配相符的转发动作集合；

处理模块，用于对所有流表的转发动作集合取交集，得到每个转发动作集合共同的转发动作；

转发模块，用于根据每个转发动作集合共同的转发动作转发所述目标报文。

上述实施例提供了一种多级流表的处理装置，根据每个流表中的逻辑规则获取对应的具有一个或多个转发动作的转发动作集合，并对每个流表中这些获取到的转发动作集合取交集，从而得到符合所有流表保存的逻辑规则对应的转发动作，从而完成报文的转发。

其中，在本发明的上述实施例中，每个流表所保存的逻辑规则具体包括有多个匹配域，每个匹配域对应一个转发动作；所述多级流表中的每个流表还分别设有一个跳转流条目，用于存储其所对应的流表中每个转发动作的跳转地址，从而能够使匹配模块在得到第一流表的转发动作集合后，根据该转发动作集合中每个转发动作所对应的跳转地址向下级流表进行跳转。

其中，在本发明的上述实施例中，所述装置还包括：

流表调换模块，用于当需要对所述多级流表的排序进行变化时，将需要改变的流表以及该流表对应的所有转发动作进行调换，并更新所有流表的跳转流条目。

其中，在本发明的上述实施例中，所述装置还包括：

流表替换模块，用于当需要替换掉所述多级流表中的目标流表时，生成一替换流表，在所述替换流表中保存需要替换的逻辑规则，并将所述目标流表替换成所述替换流表，之后配置该替换流表中逻辑规则的转发动作，并更新所有流表的跳转流条目。

显然，本实施例的装置与本发明中一种多级流表的处理方法相对应，该多级流表的处理方法所能达到的技术效果，本实施例的装置也同样能够达到。

以上所述是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明所述原理的前提下，还可以作出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。

Claims (16)

1.一种流表的多级化方法，其特征在于，包括：第一流表以及第二流表；所述第一流表保存有至少一种逻辑规则以及与该至少一种逻辑规则对应的所有转发动作，所述第二流表保存有一种逻辑规则以及该一种逻辑规则的所有转发动作，所述第一流表以及第二流表正交组成三态内容寻址存储器TCAM流表；其中，所述方法包括：

生成第三流表；

将所述第一流表中的目标逻辑规则以及该目标逻辑规则对应的转发动作分离至所述第三流表，使得所述第一流表、第二流表以及第三流表正交后组成所述TCAM流表，之后继续生成新的流表，直至流表数量达到预设上限。

2.根据权利要求1所述的方法，其特征在于，所述第一流表以及第二流表中的逻辑规则具体包括有一个或多个匹配域，每个匹配域对应有一个或多个转发动作；

将所述第一流表中的目标逻辑规则以及该目标逻辑规则对应的所有转发动作分离至所述第三流表的步骤包括：

计算第一流表中所有逻辑规则的映射收益，将映射收益最大的逻辑规则确定为目标逻辑规则；

将所述第一流表中的目标逻辑规则以及该目标逻辑规则对应的所有转发动作分离至所述第三流表；其中，目标逻辑规则的同一个匹配域不重复保存在所述第三流表中。

3.根据权利要求2所述的方法，其特征在于，所述第一流表配有第一跳转流条目，用于存储第一流表中每个转发动作的跳转地址，所述第二流表配有第二跳转流目条，用于存储第二流表中每个转发动作的跳转地址；其中，所述第一跳转流条目的跳转地址为第二流表或转发器，所述第二跳转流条目的跳转地址为转发器；

在将所述第一流表中的目标逻辑规则以及该目标逻辑规则对应的所有转发动作分离至所述第三流表后，所述方法还包括：

为所述第三流表配置第三跳转流条目；

为所述第三流表中每个转发动作配置跳转地址；

将所述第三流表中每个转发动作的跳转地址保存至所述第三跳转流条目；

更新所述第一跳转流条目以及第二跳转流条目中的跳转地址。

4.根据权利要求3所述的方法，其特征在于，

为所述第三流表中每个转发动作配置跳转地址的步骤包括：

将所述第三流表中每个转发动作的跳转地址配置为转发器；

更新所述第一跳转流条目以及第二跳转流条目中的跳转地址的步骤包括：

更新所述第一跳转流条目以及第二跳转流条目中的跳转地址，使所述第一跳转流条目的跳转地址为第二流表或第三流表或转发器，并使所述第二跳转流条目的跳转地址为第三流表或转发器。

5.一种多级流表的处理方法，其特征在于，所述多级流表为按照权利要求1至4任一项形成的流表，且所述多级流表按有效位进行排序且能够正交组成一个三态内容寻址存储器TCAM流表；其中，位于第一级的第一流表保存有至少一种逻辑规则以及与该至少一种逻辑规则对应的所有转发动作，其余每个流表均只保存有一种逻辑规则以及该一种逻辑规则的所有转发动作；所述方法包括：

确定目标报文的逻辑规则；

按所述有效位的顺序分别将每个流表所保存逻辑规则与目标报文的逻辑规则进行匹配，得到每个流表与该匹配相符的转发动作集合；

对所有流表的转发动作集合取交集，得到每个转发动作集合共同的转发动作；

根据每个转发动作集合共同的转发动作转发所述目标报文。

6.根据权利要求5所述的方法，其特征在于，每个流表所保存的逻辑规则具体包括有一个或多个匹配域，每个匹配域对应有一个或多个转发动作；所述多级流表中的每个流表还分别设有一个跳转流条目，用于存储其所对应的流表中每个转发动作的跳转地址，从而能够在得到第一流表的转发动作集合后，根据该转发动作集合中每个转发动作所对应的跳转地址向下级流表进行跳转。

7.根据权利要求6所述的方法，其特征在于，所述方法还包括：

当需要对所述多级流表的排序进行变化时，将需要改变的流表以及该流表对应的所有转发动作进行调换，并更新所有流表的跳转流条目。

8.根据权利要求6所述的方法，其特征在于，所述方法包括：

当需要替换掉所述多级流表中的目标流表时，生成一替换流表，在所述替换流表中保存需要替换的逻辑规则，并将所述目标流表替换成所述替换流表，之后配置该替换流表中逻辑规则的转发动作，并更新所有流表的跳转流条目。

9.一种流表的多级化装置，其特征在于，包括：第一流表以及第二流表；所述第一流表保存有至少一种逻辑规则以及与该至少一种逻辑规则对应的所有转发动作，所述第二流表保存有一种逻辑规则以及该一种逻辑规则的所有转发动作，所述第一流表以及第二流表正交组成TCAM流表；其中，所述装置包括：

生成模块，用于生成第三流表；

分离模块，用于将所述第一流表中的目标逻辑规则以及该目标逻辑规则对应的转发动作分离至所述第三流表，使得所述第一流表、第二流表以及第三流表正交后组成所述TCAM流表，之后继续生成新的流表，直至流表数量达到预设上限。

10.根据权利要求9所述的装置，其特征在于，所述第一流表以及第二流表中的逻辑规则具体包括有一个或多个匹配域，每个匹配域对应有一个或多个转发动作；

所述分离模块包括：

计算子模块，用于计算第一流表中所有逻辑规则的映射收益，将映射收益最大的逻辑规则确定为目标逻辑规则；

分离子模块，用于将所述第一流表中的目标逻辑规则以及该目标逻辑规则对应的转发动作分离至所述第三流表；其中，目标逻辑规则的同一个匹配域不重复保存在所述第三流表中。

11.根据权利要求10所述的装置，其特征在于，所述第一流表配有第一跳转流条目，用于存储第一流表中每个转发动作的跳转地址，所述第二流表配有第二跳转流目条，用于存储第二流表中每个转发动作的跳转地址；其中，所述第一跳转流条目的跳转地址为第二流表或转发器，所述第二跳转流条目的跳转地址为转发器；

所述装置还包括：

第一配置模块，用于在所述分离模块将所述第一流表中的目标逻辑规则以及该目标逻辑规则对应的所有转发动作分离至所述第三流表后，为所述第三流表配置第三跳转流条目；

第二配置模块，用于为所述第三流表中每个转发动作配置跳转地址；

保存模块，用于将所述第三流表中每个转发动作的跳转地址保存至所述第三跳转流条目；

更新模块，用于更新所述第一跳转流条目以及第二跳转流条目中的跳转地址。

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

所述第二配置模块具体用于：将所述第三流表中每个转发动作的跳转地址配置为转发器；

所述更新模块具体用于：更新所述第一跳转流条目以及第二跳转流条目中的跳转地址，使所述第一跳转流条目的跳转地址为第二流表或第三流表或转发器，并使所述第二跳转流条目的跳转地址为第三流表或转发器。

13.一种多级流表的处理装置，其特征在于，所述多级流表为按照权利要求1至4任一项形成的流表，且所述多级流表按有效位进行排序且能够正交组成一个三态内容寻址存储器TCAM流表；其中，位于第一级的第一流表保存有至少一种逻辑规则以及与该至少一种逻辑规则对应的所有转发动作，其余每个流表均只保存有一种逻辑规则以及该一种逻辑规则的所有转发动作；所述装置包括：

确定模块，用于确定目标报文的逻辑规则；

匹配模块，用于按所述有效位的顺序分别将每个流表所保存逻辑规则与目标报文的逻辑规则进行匹配，得到每个流表与该匹配相符的转发动作集合；

处理模块，用于对所有流表的转发动作集合取交集，得到每个转发动作集合共同的转发动作；

转发模块，用于根据每个转发动作集合共同的转发动作转发所述目标报文。

14.根据权利要求13所述的装置，其特征在于，每个流表所保存的逻辑规则具体包括有一个或多个匹配域，每个匹配域对应一个或多个转发动作；所述多级流表中的每个流表还分别设有一个跳转流条目，用于存储其所对应的流表中每个转发动作的跳转地址，从而能够使匹配模块在得到第一流表的转发动作集合后，根据该转发动作集合中每个转发动作所对应的跳转地址向下级流表进行跳转。

15.根据权利要求14所述的装置，其特征在于，所述装置还包括：

流表调换模块，用于当需要对所述多级流表的排序进行变化时，将需要改变的流表以及该流表对应的所有转发动作进行调换，并更新所有流表的跳转流条目。

16.根据权利要求14所述的装置，其特征在于，所述装置包括：

流表替换模块，用于当需要替换掉所述多级流表中的目标流表时，生成一替换流表，在所述替换流表中保存需要替换的逻辑规则，并将所述目标流表替换成所述替换流表，之后配置该替换流表中逻辑规则的转发动作，并更新所有流表的跳转流条目。