[发明专利]基于决策树高速并行处理的网络流量在线分类方法及装置

权利要求书

1.一种基于决策树高速并行处理策略实现TCP流量在线分类的方法，其特征在于包括以下步骤：

步骤1，前期真实流量数据的采集、分流及手工分类：采集网络真实流量数据集，利用五元组将数据集分离为不同的TCP流，对TCP流的集合进行手工分类，使每一条TCP流都与一种协议类型相对应。

步骤2，提取前期TCP流集合的若干个包特征：提取每一条TCP流中关于数据包的特征，并按照数据包在该TCP流的先后顺序构建初步特征序列，然后对包特征进行筛选，得到最终特征序列。

步骤3，决策树分类模型的建立：对步骤2构成的最终特征序列，利用决策树算法进行建树。

步骤4，对步骤3中建立的决策树进行数据结构转换并存储到硬件设备(如FPGA、CPLD、ASIC等)的存储设备(如RAM、ROM、FLASH等)中：通过对决策树的遍历，一方面提取决策树的中间节点值，对同一属性的各中间节点值进行从小到大的排序，然后对所有属性的各个中间节点值按顺序进行从小到大的编码，另一方面提取决策树的边缘节点值，对边缘节点值同样也进行编码，边缘节点值的编码是一个范围，取决于到达该边缘节点所经历的各中间节点的编码值。中间节点值及其编码以及边缘节点值及其编码分别存储在两块分离的存储设备(如RAM、ROM、FLASH等)中。

步骤5，对待分类的数据包进行分流及类别判断：根据五元组将数据包划分到不同的流并查找流信息表获取分类信息，流信息表用于记录流的五元组信息以及该条流的类别。

步骤6，对当前数据包进行打标签处理并提取待分类TCP流的包特征：利用步骤5提取的类别信息对所有经过的数据包进行打标签处理，若数据包所属的流已经被分类，则打上相应的类别标签，若未分类，则按照一定的原则标记一个默认的标签，然后判断该数据包是否需要被提取包特征并做相应处理。在这里，包特征的提取与步骤2中采用的最终特征序列相对应，需要按包到达顺序进行提取，并构建待分类流的特征序列，待分类流的特征序列存储在参数表中，参数表的一条记录包括五元组、各个包特征值以及参数是否满的标志。

步骤7，决策树查找：利用步骤6所得的待分类流的特征序列对步骤4所得的两块存储设备(如RAM、ROM、FLASH等)进行查找，判断该TCP流的类别值并更新流信息表。

2.根据权利要求1所述的TCP流量在线分类方法，其特征在于：

其中在流量分类装置用于网络流量在线分类之前，以离线处理的方式建立决策树并对决策树进行数据结构转换。

3.根据权利要求1所述的TCP流量在线分类方法，其特征在于：

所述步骤2中，需根据特征选择算法对初步提取的若干个包特征进行处理，筛选出最能体现流类别特性的包特征。

4.根据权利要求1所述的TCP流量在线分类方法，其特征在于：

所述步骤5中，流信息表仅需要保存已分类的流的记录，不需要保存未分类的流的记录，因此对流信息表进行查找时，若不存在记录则可以立即判断为未分类，从而节省查找时间。

5.根据权利要求1所述的TCP流量在线分类方法，其特征在于：

所述步骤6中，包的顺序信息按照到达观测点的时间顺序进行排列，取三次握手的第一个请求包即Setup包作为该流的第一个包。

6.根据权利要求1所述的TCP流量在线分类方法，其特征在于：

所述步骤6中，已分类被打上正确标签的包与未分类打上默认标签且需要进行参数提取的包需要进行时钟同步处理，即插入相应级别的流水线以保证数据包传输路线上的FIFO不会出现溢出现象。

7.根据权利要求1所述的TCP流量在线分类方法，其特征在于：

所述步骤7中，采用并行查找的方式及流水线的结构以提高查找速度，在不考虑其他读写信号及时钟同步处理的情况下，仅需要两个时钟周期即可完成决策树的查找过程。即第一个时钟周期并行比较所有属性的所有中间节点值，确定该流所属的所有中间节点编码值并合并为一个数据，第二个时钟周期利用前一个时钟周期的结果数据并行比较所有边缘节点的编码值，从而确定该流的类别。