1.本发明属于报文数据查找技术领域，尤其涉及一种基于决策树的并行报文分类查找方法及系统。
背景技术：2.本部分的陈述仅仅是提供了与本发明相关的背景技术信息，不必然构成在先技术。
3.报文分类是许多网络服务的基础，在服务质量、策略路由、网络安全等服务中得到广泛应用。报文分类的速度和功能将直接影响这些服务的性能，对当前网络性能有关键影响，因此报文分类是当前网络研究的重要课题之一。报文分类的目标是根据预定义的规则列表和报文头部的特定字段值将报文分为不同的流，从而提供差异化的服务。
4.基于决策树的解决方案作为主流的报文分类技术得到了广泛研究。由于规则集复杂性的增加及规则集规模的扩大，设计高效的决策树算法非常具有挑战性，而发明人发现，已有的决策树算法并未在分类速度和内存开销之间取得较好折衷，且可扩展性较差，无法满足日益正常的网络带宽的需要。
技术实现要素：5.为了解决上述背景技术中存在的技术问题，本发明提供一种基于决策树的并行报文分类查找方法及系统，其能够提升报文分类速度，并且能支持大规模的规则集。
6.为了实现上述目的，本发明采用如下技术方案：
7.本发明的第一个方面提供一种基于决策树的并行报文分类查找方法，其包括：
8.获取报文信息；
9.采用多条流水线并行查找若干决策树，得到所述报文信息的类别；所述流水线包括决策树的树节点遍历流水线和报文分类规则并行匹配流水线；
10.其中，所述决策树的构建过程为：
11.基于报文字段的前缀长度彼此接近的规则属于同一子集原则，将报文规则集进行自适应分区，得到多个报文规则子集；
12.基于多比特切割方法为每个报文规则子集构建一棵决策树。
13.本发明的第二个方面提供一种基于决策树的并行报文分类查找系统，其包括：
14.报文信息获取模块，其用于获取报文信息；
15.报文信息分类模块，其用于采用多条流水线并行查找若干决策树，得到所述报文信息的类别；所述流水线包括决策树的树节点遍历流水线和报文分类规则并行匹配流水线；
16.其中，所述决策树的构建过程为：
17.基于报文字段的前缀长度彼此接近的规则属于同一子集原则，将报文规则集进行自适应分区，得到多个报文规则子集；
18.基于多比特切割方法为每个报文规则子集构建一棵决策树。
19.本发明的第三个方面提供一种计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现如上述所述的基于决策树的并行报文分类查找方法中的步骤。
20.本发明的第四个方面提供一种计算机设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现如上述所述的基于决策树的并行报文分类查找方法中的步骤。
21.与现有技术相比，本发明的有益效果是：
22.本发明的基于决策树的并行报文分类查找方法采用多条流水线并行查找若干决策树，得到所述报文信息的类别；其中，流水线包括决策树的树节点遍历流水线和报文分类规则并行匹配流水线，进一步提升了报文分类的速度，降低了并行分类查找方法的内存消耗。
23.本发明在决策树的构建过程中，基于报文字段的前缀长度彼此接近的规则属于同一子集原则，将报文规则集进行自适应分区，得到多个报文规则子集；基于多比特切割方法为每个报文规则子集构建一棵决策树，使得并行分类查找方法具有良好的可扩展性，能支持较大规模的规则集。
24.本发明附加方面的优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本发明的实践了解到。
附图说明
25.构成本发明的一部分的说明书附图用来提供对本发明的进一步理解，本发明的示意性实施例及其说明用于解释本发明，并不构成对本发明的不当限定。
26.图1为本发明实施例的基于决策树的并行报文分类查找方法的总体流程图；
27.图2为本发明实施例的决策树构建算法的框架示意图；
28.图3为基于决策树的并行报文分类查找硬件实现示意图；
29.图4为本发明实施例的规则集的源i本发明实施例的p地址前缀长度分布规律；
30.图5为本发明实施例的规则集的目的ip地址前缀长度分布规律；
31.图6为本发明实施例的基于决策树的并行报文分类查找系统结构示意图。
具体实施方式
32.下面结合附图与实施例对本发明作进一步说明。
33.应该指出，以下详细说明都是例示性的，旨在对本发明提供进一步的说明。除非另有指明，本文使用的所有技术和科学术语具有与本发明所属技术领域的普通技术人员通常理解的相同含义。
34.需要注意的是，这里所使用的术语仅是为了描述具体实施方式，而非意图限制根据本发明的示例性实施方式。如在这里所使用的，除非上下文另外明确指出，否则单数形式也意图包括复数形式，此外，还应当理解的是，当在本说明书中使用术语“包含”和/或“包括”时，其指明存在特征、步骤、操作、器件、组件和/或它们的组合。
35.实施例一
36.如图1所示，本实施例提供了一种基于决策树的并行报文分类查找方法，其具体包
括如下步骤：
37.s101：获取报文信息。
38.s102：遍历查找预先构建的若干决策树，得到所述报文信息的类别。
39.其中，在步骤s102中，如图2所示，所述决策树的构建过程为：
40.s1021：基于报文字段的前缀长度彼此接近的规则属于同一子集原则，将报文规则集进行自适应分区，得到多个报文规则子集。
41.具体地，自适应规则集分区：基于对规则集几何分布特征的观察结果，选择一些适当的字段作为规则集分区的基础。然后使用聚类算法k-means实现快速自适应的规则集分区，从而获得多个子集，其中字段的前缀长度彼此接近的规则属于同一子集。因为设置了理想的初始聚类数量和中心点，因此仅需有限的几次迭代就能完成聚类，聚类的迭代次数和时间开销都非常低。
42.规则集分布具有一定的几何特征，利用这些特征有助于构建性能更优的决策树，提升算法的性能。分别对acl、fw和ipc类型规则集进行统计分析，结果如图4和图5所示。
43.(1)ip地址字段。ip地址字段属于前缀匹配，其中前缀长度倾向于边缘分布，即位于0或32附近，且前缀长度取值在24以上的占很大比例。因此ip地址前缀长度是非均匀分布的，前缀长度较长的规则数占较大比例。
44.从图4可以看出源ip与目的ip地址的联合分布与单个ip地址分布具有类似特点，即大部分规则前缀集中在一个小范围内。
45.(2)端口字段。端口字段属于范围匹配，其中源端口号通常为通配符，目的端口号则为通配符(wildcard，wc)、精确值(exact match，em)和任意范围(any range，ar)的组合。
46.(3)协议字段。协议字段属于精确匹配。协议类型取值范围有限，主要为tcp、udp、icmp协议或通配符。
47.基于上述分析，协议字段分布相对简单，为有限的几种取值，端口号中为通配符的比例较大，而ip地址字段为最有区分性的字段，取值范围较广，且分布相对集中，因此在聚类算法中，使用ip地址字段作为聚类的依据。
48.具体来说，首先获取每条规则的源ip和目的ip地址前缀长度，并以二维坐标系上的点来表示，其中x轴表示源ip地址的前缀长度，y轴表示目的ip地址前缀的长度。如sip为192.168.1.1/24与dip为192.168.2.1/28的规则映射到ip前缀二维坐标系中为(24，28)，通过观察图4和图5可以发现二维坐标系中，出现在坐标系起点和终点附近的点较多，因此可以快速完成聚类。
49.主要的聚类算法包括层次聚类与基于划分的聚类等。本实施例中使用基于划分的聚类算法k-means，因其计算速度快，时间复杂度低，适用于大规模的数据集，并且对于分布相对集中的数据分类效果较好。
50.k-means算法中关键在于类的数量和初始中心点的选择。将规则集映射到ip地址前缀的二维坐标系中后，基于其分布特征，以及k-means算法对类初始中心点距离尽可能远的要求，设置类的数量k＝4，每个类的初始中心点分别为c0(0,0)，c1(0,24)，c2(24,0)与c3(24,24)，需要注意的是，类数量和初始中心点的选择对于聚类效果有很大影响。经过验证本发明中选择的类数量和初始中心点是合理的，一般只需2-4次迭代就可完成规则集的划分。
51.在选定4个初始中心点之后，计算每个报文对应二维坐标系的点到k个中心点的距离，并将每个报文划分到最近的类，然后计算每个类的平均值，作为新的中心点，之后重复上述过程，直到满足收敛条件。聚类的目的在于将地址前缀长度更接近的规则放在一类里，这样属于同一类的规则拥有相差不大的前缀长度，从而提供更多可选比特用于之后构建决策树。
52.s1022：基于多比特切割方法为每个报文规则子集构建一棵决策树。
53.在得到多个子集后，使用一种多比特切割方案为每个子集构建树，该方案使用比特分离能力和通配符比率作为选择有效的切割比特的标准。此外，还使用了一种从最大子集中选择有效比特的策略，消除了位之间的相关性问题。得益于精心选择的有效比特，可以构建一棵短的决策树。
54.具体地，步骤s1022的基于多比特切割方法为每个报文规则子集构建一棵决策树的过程为：
55.s10221：对报文信息中的ip地址前缀超过设定长度的子集，使用规则中的有效比特将规则分离到不同的树节点中。
56.其中，在基于报文字段的前缀长度彼此接近的规则属于同一子集原则，将报文规则集进行自适应分区的过程中，基于最有区分性的报文字段进行子集聚类。
57.s10222：再判断此时树节点内规则数量是否不大于预定于的阈值或此时规则不可再分离，若是则构造叶节点，否则重复比特选择过程，最终构建层次化的决策树。
58.在完成规则集分区后，得到多个子集，然后使用比特切割技术为每个子集构建决策树。构建比特切割决策树的关键在于如何选择最佳的有效比特来分离规则。有效比特选择标准具体如下：
59.对于维度为d，长度为l的规则(如ipv4五元组d＝5，l＝104bit)，为每个规则创建一个比特串，比特串每一位的取值可能为0，1或*(通配符)。从比特串中选择有效比特将规则均匀分布到子节点中。
60.本发明中使用两个参数来判断最佳的比特：比特可分离性、通配符比率。比特可分离性决定在该比特上的规则分布是否均匀，值越大说明能更均匀的将规则分离开；通配符比率决定规则的复制程度，越少的通配符比率意味着内存消耗更低，最后选取可分离性大、通配符比率少的那些比特。
61.比特可分离性的计算如下：对于一个规则数量为n的规则集，某一比特的可分离值为num0*num1，其中num0是对应比特位置上值为0的规则数量，num1是值为1的规则数量，注意由于通配符的存在，num0与num1之和少于等于n。因此比特可分离性也可用数学理论来解释，即当两数之和为定值(或不大于)，则两数之积越大，两数之差越小。而当num0与num1值更接近，则该比特能将规则集更均匀分布到子节点中。
62.除考虑分布均匀程度外，还需考虑规则复制程度，因为在将规则分派到子节点中时，通配符(*)被复制为0和1，引入通配符比例来衡量规则复制程度。通配符比例的计算公式为：p(ration)＝#wildcard/n，选择p值更少的比特能有效减少规则复制程度，降低算法的内存消耗。
63.综合考虑可分离性与通配符比例，构建评价函数f＝a*separate+b*p(ratio)，通过调节系数a与b的取值来选择面向特定目标优化的比特。
64.当规则数量较多时，需要一次选择多个比特才能更好的分离规则。在后续比特选择中，如果简单使用比特可分离性作为标准，将会产生比特相关性的问题，即规则集在这些比特上的0/1表现完全一样，因此选择这两个比特与只选择其中一个比特的效果是一样的。
65.消除比特相关性有两种方案，计算比特之间的相关性以及从子节点选择的标准。然而计算比特相关性将带来大量额外的计算量，并且容易计算两比特的相关性，但计算3个及以上比特的相关性是困难的。本发明中提出了从“最大子节点选择”的原则，即选择的有效比特在前一次形成的规则数最多的子节点中产生，这样可以使得选择的比特进一步分离最大子节点，而不会与之前有效比特发生相关性问题。
66.通过比特切割构建的决策树是一个迭代的过程，最终形成层次化的树结构，需要判断何时停止比特切割过程。停止比特切割的条件包括：
67.(1)节点内的规则数量是否不大于预定义的阈值。若叶节点内的规则数不大于该阈值，则停止比特切割过程，并将当前节点初始化为叶节点。
68.(2)当前节点内的规则已经不能用比特分离，此时再进行切割已经没有作用，因此也将停止比特切割过程，并将当前节点初始化为叶节点。
69.通过多比特切割后构建了多棵决策树。为了对报文进行分类，需要遍历决策树，并在叶节点处找到匹配规则。
70.要搜索树，首先查看其根节点并检查该节点的类型。如果它是叶节点，则使用线性搜索或者硬件中的并行查找来获取匹配规则。否则，使用存储在内部节点中的有效比特信息从报文头部获得索引，直到到达叶节点为止。
71.决策树的节点数据结构如表1所示。使用1个字节来表示节点的类型：内部节点或叶节点。对于每个内部节点，使用1个字节表示有效位的数量，并使用8个字节表示有效位的信息，包括维度和位置。叶节点使用1个字节作为叶节点覆盖的规则数。内部节点和叶节点都使用4个字节来存储数组指针。
72.表1决策树的节点数据结构
[0073][0074]
在一个或多个实施例中，对于硬件实现查找，采用多条流水线并行查找的方式，如图3所示。采用多条流水线并行查找若干决策树，所述流水线包括决策树的树节点遍历流水线和报文分类规则并行匹配流水线。多条流水线之间也使用并行匹配的方式以进一步提高吞吐量。每条流水线的匹配结果最终通过一个优先级解析器，从而得到最佳的匹配规则，即
优先级最高的规则。
[0075]
硬件分类则使用并行查找的方式。具体为将每一棵决策树映射到fpga等硬件平台的流水线上，然后充分利用fpga上可用的并行性，多条流水线并行查找以得到最终的查找结果。
[0076]
在其他实施例中，对于软件实现查找，在遍历若干决策树的过程中，从决策树的根节点开始遍历，经过中间节点到达叶节点，在叶节点处使用线性搜索来查找报文匹配的规则；在遍历完一棵树之后，将继续遍历剩余的决策树。
[0077]
考虑到有多棵决策树，为避免不必要的查找，为每棵树引入一个优先级，该值设置为树中包含的所有规则的最大优先级；在查找时，如果已匹配规则的优先级大于该决策树的优先级，则跳过该树。
[0078]
实施例二
[0079]
如图6所示，本实施例提供了一种基于决策树的并行报文分类查找系统，其具体包括如下模块：
[0080]
(1)报文信息获取模块，其用于获取报文信息；
[0081]
(2)报文信息分类模块，其用于采用多条流水线并行查找若干决策树，得到所述报文信息的类别；所述流水线包括决策树的树节点遍历流水线和报文分类规则并行匹配流水线.
[0082]
其中，所述决策树的构建过程为：
[0083]
步骤a：基于报文字段的前缀长度彼此接近的规则属于同一子集原则，将报文规则集进行自适应分区，得到多个报文规则子集；
[0084]
步骤b：基于多比特切割方法为每个报文规则子集构建一棵决策树。
[0085]
在具体实施过程中，基于多比特切割方法为每个报文规则子集构建一棵决策树的过程为：
[0086]
步骤b1：对报文信息中的ip地址前缀超过设定长度的子集，使用规则中的有效比特将规则分离到不同的树节点中；
[0087]
步骤b2：再判断此时树节点内规则数量是否不大于预定于的阈值或此时规则不可再分离，若是则构造叶节点，否则重复比特选择过程，最终构建层次化的决策树。
[0088]
此处需要说明的是，本实施例中的各个模块与实施例一中的各个步骤一一对应，其具体实施过程相同，此处不再累述。
[0089]
实施例三
[0090]
本实施例提供了一种计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现如上述所述的基于决策树的并行报文分类查找方法中的步骤。
[0091]
实施例四
[0092]
本实施例提供了一种计算机设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现如上述所述的基于决策树的并行报文分类查找方法中的步骤。
[0093]
本发明是参照根据本发明实施例的方法、设备(系统)和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指
令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。
[0094]
以上所述仅为本发明的优选实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。
