线速软多元组报文分类方法

摘要

本发明公开了一种线速软多元组报文分类方法，其步骤为：(1)将规则中的端口字段转换为对应的前缀闭包，得到一个不连续掩码前缀集；首先将端口字段转为对应的前缀闭包，即形成一个覆盖其区间且可以表示为前缀形式的最短的区间；然后将五维前缀集的各个维度连接起来，得到一个不连续掩码的前缀集；(2)通过上述不连续掩码前缀集构造CMT数据结构；(3)使用CMT结构查找算法实现高速报文分类。本发明具有查找速度快、硬件开销小、能耗低等优点。

权利要求

1.一种线速软多元组报文分类方法，其特征在于，步骤为：

(1)将规则中的端口字段转换为对应的前缀闭包，得到一个不连续掩码前缀集；首先将端口字段转为对应的前缀闭包，即形成一个覆盖其区间且可以表示为前缀形式的最短的区间；然后将五维前缀集的各个维度连接起来，得到一个不连续掩码的前缀集；

(2)通过上述不连续掩码前缀集构造公共掩码树CMT数据结构；

(3)使用公共掩码树CMT结构查找算法实现高速报文分类；

所述步骤(2)的具体步骤为：

(2.a)将整个前缀集作为公共掩码树CMT结构的根节点；

(2.b)使用根节点的公共掩码修剪前缀集中的每一项，如果修剪后的前缀集和之前不一致，该前缀将被移入该项的子节点中；

(2.c)对节点中的所有项进行排序，使前缀相同的项位于相邻的位置；

(2.d)合并前缀相同的项，将这些项的子节点合并成一个大的子节点，并更新该子节点的公共掩码。

2.根据权利要求1所述的线速软多元组报文分类方法，其特征在于，所述步骤(2)还包括：步骤(2.e)：若子节点出现冲突，即子节点掩码与父节点相等，则进行分表操作，否则对所有新生成的子节点递归的执行组织算法。

3.根据权利要求2所述的线速软多元组报文分类方法，其特征在于，在进行分表算法时，将整个节点分为多个次级节点；即：针对节点N，取一个表项集合X，从N中第一项开始，若当前前缀加入X后，X的公共掩码将与N的父节点掩码相等，则将该前缀移入一个新的次级节点N’，否则将其加入X中；若之后N’仍处于冲突状态，则递归的对N’进行分表操作。

4.根据权利要求1～3中任意一项所述的线速软多元组报文分类方法，其特征在于，所述步骤(1)的具体步骤为：(1.1)将端口范围转化为二进制表示；

(1.2)对于上下界的二进制表示，从最高位开始，如果上界和下界相等，则前缀闭包在该位上取相应的值，否则之后无论上下界是否相等都取*。

5.根据权利要求1～3中任意一项所述的线速软多元组报文分类方法，其特征在于，所述步骤(3)的具体步骤为：搜索时，首先在公共掩码树CMT的根节点中根据第一次划分的公共掩码对五元组数据进行修剪，找到根节点中对应的等价类；之后，使用该子节点的公共掩码递归的对五元组数据进行后续的查找，直到不存在额外的子节点为止。

6.根据权利要求1～3中任意一项所述的线速软多元组报文分类方法，其特征在于，还包括步骤(4)：更新步骤，使用公共掩码树CMT插入、删除和重构方法实现规则集更新操作。

7.根据权利要求6所述的线速软多元组报文分类方法，其特征在于，所述插入操作是根据公共掩码树CMT的结构将新规则置入相应的节点中，若新规则不适应公共掩码树CMT已有的结构，则在其最后一次可置入的节点中新加一个线性表，将规则置于其中，并在每次查找到该节点时检查这个线性表；在新规则数达到一定规模的时候可对公共掩码树CMT进行重构操作，即将每一个存在线性表的节点中的所有规则提出，将这些规则重新组织为一个新的节点，并替换原来的节点。

8.根据权利要求6所述的线速软多元组报文分类方法，其特征在于，所述删除操作是在每个节点中记录此节点所有后裔中所包含的规则数量，删除规则时将此规则所在的节点，及该节点所有祖先的计数减1，同时删掉计数为0的节点。

9.根据权利要求6所述的线速软多元组报文分类方法，其特征在于，所述重构方法是从根节点开始搜索含有线性表的节点，如果发现了这样的节点，重构方法会将此节点及其所有子孙中所包含的前缀集合成一个额外的节点，并针对此节点执行构造方法，最后用此不包含线性表的节点替换原节点。

说明书

线速软多元组报文分类方法

技术领域

[0001] 本发明主要涉及到网络技术中报文转发领域，特指一种线速软多元组报文分类方法。

背景技术

[0002] 数据包分类(Packet Classification)是实现报文转发的一项关键步骤，也是完成报文转发的关键技术。数据包分类可描述为：针对IP数据包头内的五元组信息(源目IP，源目端口，协议号)，找出匹配该数据包头的最佳规则。其中，每一条规则由五段范围组成(源目IP，源目端口，协议号)，源目IP以前缀形式表示，源目端口以区间形式表示，协议号一般为精确值。这里“最佳规则”是指所有匹配规则中掩码最精确，区间最短的规则。

[0003] 目前，大部分高端路由器的数据包分类算法都由TCAM实现。TCAM采用了线性查找的方式逐条判断每一条规则是否匹配，并通过并行化、流水线等硬件技术获得了接近一次访存的查找效率。TCAM有着很高的能耗和价格，而且规则数不能太大(当前主流的TCAM容量一般为512K条规则)。此外，一些网络设备在设计时没有提供TCAM硬件，进一步限制了该算法的应用场景。

[0004] 另外，相应的软件分类方法也有很多，大概可分为基于叉乘(Cross Producting)、组空间(Tuple Space)、决策树(Decision Tree)的三种。基于叉乘的方法(如RFC)有着极高的内存开销，基于组空间的方法(Tuple Space Search)只适用于掩码种类不大的规则集，基于决策树的方法(如EGT-PC)则有着很慢的规则更新速度。

发明内容

[0005] 本发明要解决的技术问题就在于：针对现有技术存在的技术问题，本发明提供一种查找速度快、硬件开销小、能耗低的线速软多元组报文分类方法。

[0006] 为解决上述技术问题，本发明采用以下技术方案：

[0007] 一种线速软多元组报文分类方法，其步骤为：

[0008] (1)将规则中的端口字段转换为对应的前缀闭包，得到一个不连续掩码前缀集；首先将端口字段转为对应的前缀闭包，即形成一个覆盖其区间且可以表示为前缀形式的最短的区间；然后将五维前缀集的各个维度连接起来，得到一个不连续掩码的前缀集；

[0009] (2)通过上述不连续掩码前缀集构造CMT数据结构；

[0010] (3)使用CMT结构查找算法实现高速报文分类。

[0011] 作为本发明的进一步改进：所述步骤(2)的具体步骤为：

[0012] (2.a)将整个前缀集作为CMT结构的根节点；

[0013] (2.b)使用根节点的公共掩码修剪前缀集中的每一项，如果修剪后的前缀集和之前不一致，该前缀将被移入该项的子节点中；

[0014] (2.c)对节点中的所有项进行排序，使前缀相同的项位于相邻的位置；

[0015] (2.d)合并前缀相同的项，将这些项的子节点合并成一个大的子节点，并更新该子节点的公共掩码。

[0016] 作为本发明的进一步改进：所述步骤(2)还包括：步骤(2.e)：若子节点出现冲突，即子节点掩码与父节点相等，则进行分表操作，否则对所有新生成的子节点递归的执行组织算法。

[0017] 作为本发明的进一步改进：在进行分表算法时，将整个节点分为多个次级节点；即：针对节点N，取一个表项集合X，从N中第一项开始，若当前前缀加入X后，X的公共掩码将与N的父节点掩码相等，则将该前缀移入一个新的次级节点N’，否则将其加入X中；若之后N’仍处于冲突状态，则递归的对N’进行分表操作。

[0018] 作为本发明的进一步改进：所述步骤(1)的具体步骤为：

[0019] (1.1)将端口范围转化为二进制表示；

[0020] (1.2)对于上下界的二进制表示，从最高位开始，如果上界和下界相等，则前缀闭包在该位上取相应的值，否则之后无论上下界是否相等都取*。

[0021] 作为本发明的进一步改进：所述步骤(3)的具体步骤为：搜索时，首先在CMT的根节点中根据第一次划分的公共掩码对五元组数据进行修剪，找到根节点中队应的等价类；之后，使用该子节点的公共掩码递归的对五元组数据进行后续的查找，直到不存在额外的子节点为止。

[0022] 作为本发明的进一步改进：还包括步骤(4)：更新步骤，使用CMT插入、删除和重构方法实现规则集更新操作。

[0023] 作为本发明的进一步改进：所述插入操作是根据CMT的结构将新规则置入相应的节点中，若新规则不适应CMT已有的结构，则在其最后一次可置入的节点中新加一个线性表，将规则置于其中，并在每次查找到该节点时检查这个线性表；在新规则数达到一定规模的时候可对CMT进行重构操作，即将每一个存在线性表的节点中的所有规则提出，将这些规则重新组织为一个新的节点，并替换原来的节点。

[0024] 作为本发明的进一步改进：所述删除操作是在每个节点中记录此节点所有后裔中所包含的规则数量，删除规则时将此规则所在的节点，及该节点所有祖先的计数减1，同时删掉计数为0的节点。

[0025] 作为本发明的进一步改进：所述重构方法是从根节点开始搜索含有线性表的节点，如果发现了这样的节点，重构方法会将此节点及其所有子孙中所包含的前缀集合成一个额外的节点，并针对此节点执行构造方法，最后用此不包含线性表的节点替换原节点。

[0026] 与现有技术相比，本发明的优点在于：

[0027] 1、本发明的线速软多元组报文分类方法，具有极快的查找速度，极快的规则更新速度，且内存占用开销小、能耗低，能够支持IP字段前缀掩码不连续的规则，支持任意维度的多元组规则，且维度的增加不会对性能造成明显的影响。

[0028] 2、本发明的线速软多元组报文分类方法，应用场景广泛，成本低廉，能耗节约的数据包分类方法；其基本方法为将规则集中的每一条规则转换为相应的多维前缀，并利用这些前缀的公共掩码将传统前缀匹配问题转化为多级精确匹配问题，后者可用哈希表达到接近O(1)的查找速率。同时，利用CPU提供的原子操作实现了一套多核环境中的快速规则更新算法。

附图说明

[0029] 图1是本发明在具体应用实例中规则集及转换后的前缀集示意图。

[0030] 图2是本发明在具体应用实例中前缀集及对应的CMT数据结构示意图。

[0031] 图3是本发明在具体应用实例中由示例前缀集构造CMT的构造方法的示意图。

[0032] 图4是本发明在具体应用实例中构造过程出现冲突情况的示意图。

[0033] 图5是本发明在具体应用实例中为解决冲突所采用的分表算法伪代码。

[0034] 图6是本发明在具体应用实例中CMT的插入规则算法伪代码。

[0035] 图7是本发明在具体应用实例中CMT的重构算法伪代码。

[0036] 图8是本发明在具体应用实例中CMT的删除规则算法伪代码。

[0037] 图9是本发明在具体应用实例中CMT的查找算法伪代码。

[0038] 图10是本发明的流程示意图。

具体实施方式

[0039] 以下将结合说明书附图和具体实施例对本发明做进一步详细说明。为清晰表述本发明的方法，以下假设规则的IP，端口字段皆为4个位宽，协议号字段为2个位宽，不连续掩码前缀为4个位宽。

[0040] 本发明的线速软多元组报文分类方法，为：将规则集中的每一条规则转换为相应的多维前缀，并利用这些前缀的公共掩码将传统前缀匹配问题转化为多级精确匹配问题；多级精确匹配问题用哈希表达到接近O(1)的查找速率。进一步，还可以在上述方法的基础上，利用CPU提供的原子操作实现了一套多核环境中的快速规则更新方法。

[0041] 如图10所示，本发明的线速软多元组报文分类方法，其具体步骤为：

[0042] (1)将规则中的端口字段转换为对应的前缀闭包，从而得到一个不连续掩码前缀集。

[0043] 如图1所示，任何一个五元组规则都可以转化为一个掩码不连续的前缀集。由于五元组规则中的端口字段不是前缀，所以首先将端口字段转为对应的前缀闭包，即，形成一个覆盖其区间且可以表示为前缀形式的最短的区间。然后，将五维前缀集的各个维度连接起来，得到一个不连续掩码的前缀集。

[0044] 例如，针对一个4位的机器，[5,6]的前缀闭包为01**即[4,7]，这样即可将五元组规则集转化为一个五维的前缀集，将这五个维度合起来就成了一个不连续掩码前缀集(为表述方便，下文中的规则集特指此转化后的不连续掩码前缀集)。

[0045] 在具体应用实例中，步骤(1)的具体步骤为：

[0046] (1.1)将端口范围转化为二进制表示，如：[5,6]可表示为[1001,1010]；

[0047] (1.2)对于上下界的二进制表示，从最高位开始，如果上界和下界相等，则前缀闭包在该位上取相应的值，否则之后无论上下界是否相等都取*。如：[1001,1010]的前缀闭包为10**，即[4,7]。

[0048] (2)通过上述不连续掩码前缀集构造CMT数据结构。

[0049] 通过步骤(1)获取了整个规则集的公共掩码，即所有规则掩码的与(&)操作结果，并根据每一条规则被公共掩码修剪后的值对整个规则集做一个划分。针对被划分到同一个等价类中的多条规则，采用递归的方法，通过这个等价类的公共掩码继续对这个子集进行划分，直到每个等价类中的所有规则掩码都相等。由于一次划分可能产生多个等价类，这样就用多叉树来表示这些等价类之间的关系，每一个等价类对应于CMT中的一个节点，将这样的数据结构称为公共掩码树(Common Mask Tree,CMT)。

[0050] 如图2所示，CMT数据结构为一个多叉树，其中每一个节点由以下几个部分组成：I、一组以哈希表形式存储的前缀集(表项)；II、该前缀集的公共掩码(灰色部分)。其中，每个表项有可能关联一个子节点，图中以实箭头表示。

[0051] 另外，在构造CMT的过程中有可能出现冲突，为了解决冲突，将一个节点分为多个次级节点，次级节点之间用虚箭头连接表示。

[0052] 如图3所示，在一个具体应用实例中，对于以下示例前缀集：

[0053] p1 0101；

[0054] p2 111*；

[0055] p3 1***；

[0056] p4 01**；

[0057] p5 101*；

[0058] 本发明可以按图中a～e所示的步骤构造出一个CMT数据结构：

[0059] (2.a)将整个前缀集作为CMT结构的根节点；

[0060] (2.b)使用根节点的公共掩码修剪前缀集中的每一项，如果修剪后的前缀集和之前不一致，该前缀将被移入该项的子节点中；

[0061] (2.c)对节点中的所有项进行排序，使前缀相同的项位于相邻的位置；

[0062] (2.d)合并前缀相同的项，将这些项的子节点合并成一个大的子节点，并更新该子节点的公共掩码；

[0063] 作为较佳的实施例，本实例中进一步包括解决某个节点的掩码和其父节点掩码相等情况的步骤。步骤(2.e)：若子节点出现冲突(即子节点掩码与父节点相等)，则进行分表操作，否则对所有新生成的子节点递归的执行组织算法。

[0064] 如图4所示，在构造CMT结构时，如果出现某个节点的掩码和其父节点掩码相等的情况，上述构造有可能会陷入死循环，将这种情况下称之为：节点存在冲突(clogged)。为解决冲突，如图5所示，进行的分表算法，将整个节点分为多个次级节点。具体步骤如下，针对节点N，取一个表项集合X，从N中第一项开始，若当前前缀加入X后，X的公共掩码将与N的父节点掩码相等，则将该前缀移入一个新的次级节点N’(行6)，否则将其加入X中(行8)。若之后N’仍处于冲突状态，则递归的对N’进行分表操作(行11)。

[0065] (3)使用CMT结构查找算法实现高速报文分类。

[0066] 搜索时，首先在CMT的根节点中根据第一次划分的公共掩码对五元组数据进行修剪，从而找到根节点中队应的等价类(子节点)。之后，使用该子节点的公共掩码递归的对五元组数据进行后续的查找，直到不存在额外的子节点为止。由于节点中所有规则的掩码都相等，每次查找仅需1次左右的访存次数。

[0067] (4)更新步骤：使用CMT插入、删除和重构方法实现规则集更新操作。

[0068] 更新步骤具体可以分为插入和删除两个部分。

[0069] 插入操作是根据CMT的结构将新规则置入相应的节点中，若新规则不适应CMT已有的结构，则在其最后一次可置入的节点中新加一个线性表，将规则置于其中，并在每次查找到该节点时检查这个线性表。由于不可置入的新规则会降低CMT的查找效率，在新规则数达到一定规模的时候可对CMT进行重构操作，即将每一个存在线性表的节点中的所有规则提出，将这些规则重新组织为一个新的节点，并替换原来的节点。

[0070] 删除操作是在每个节点中记录此节点所有后裔中所包含的规则数量，删除规则时将此规则所在的节点，及该节点所有祖先的计数减1，同时删掉计数为0的节点。为了保证多核平台上的查找效率，所有针对节点的操作都通过CPU所提供的原子操作进行。考虑到交换后废弃的数据结构中可能存在未决的访问，将其统一关联到一个待删除的缓冲中，并等待一个明显长于访问时间的间隔后再删除它们，以避免读写冲突。

[0071] 如图6所示，CMT允许在已构造好的情况下动态的插入新的前缀，具体步骤如下：从根节点开始，如果前缀掩码比节点掩码更详细，则将其插入到对应的子节点中(行2)，否则保存到一个线性表中(行9)。查找的时候遇到了这样的线性表会进行线性查找，因此在插入前缀数目多过的情况下，需要对整个数据结构进行重构操作。

[0072] 如图7所示，重构方法是从根节点开始搜索含有线性表的节点，如果发现了这样的节点，重构算法会将此节点及其所有子孙中所包含的前缀集合成一个额外的节点(行2)，并针对此节点执行构造算法，最后用此不包含线性表的节点替换原节点即可。

[0073] 如图8所示，CMT在每个节点中记录了此节点所有后裔中所包含的规则数量，删除规则时将此规则所在的节点，及该节点所有祖先的计数减1(行3)，同时删掉计数为0的节点(行4)。

[0074] 如图9所示，由于除了常规的节点外，CMT中还可能包含次级结点和线性表。对于待查找的数据v，首先使用CMT根结点对v进行修剪(行2)，计算修剪后的数据的哈希。如果根节点中存在匹配的项，则到该项的子节点中继续查找。为保证子节点的规则优先得到匹配，采用了先递归再报告的技巧(行4)。如果在某节点N匹配失败，则到N的次级节点中继续查找(行10)，如果还是没有找到匹配的规则且N存在线性表，则到N的线性表中执行线性查找(行8)。

[0075] 以上仅是本发明的优选实施方式，本发明的保护范围并不仅局限于上述实施例，凡属于本发明思路下的技术方案均属于本发明的保护范围。应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理前提下的若干改进和润饰，应视为本发明的保护范围。