基于决策树高速并行处理的网络流量在线分类方法及装置技术领域
本发明涉及一种网络流量在线分类的方法及装置，尤其涉及一种基于决策树高速并行处理策略实现TCP流量在线分类的方法及装置，属于通信技术领域。
背景技术
如今，网络技术的发展越来越迅速，基于网络的应用越来越多、越来越复杂。各种各样的应用不但抢占着越来越多的网络资源，而且也对QoS和网络安全带来了巨大的威胁。在这样的背景下，如何给广大的互联网用户提供一个安全、可靠、高效的使用环境，如何发现并避免网络的异常流量，是网络管理领域需要解决的重要问题。为了解决上述这些问题，网络研究人员提出了流量调度、容量规划等一系列策略来提高网络的运营效率。然而，无论是对现有网络进行扩容改造，还是进行QoS调度，都必须对网络流量中的各种应用(如P2P、Web、IM、视频流量等)进行准确的分类与识别。此外，在网络安全、流量计费、应用趋势分析等研究领域，准确的流量分类也具有极其重要的意义。有线宽带和3G/4G的迅速推广，使得流量分类这一有效进行网络精细化管理的工具更有广阔的应用前景。
传统的流量分类技术主要基于传输层的端口信息，然而近年来，在互联网网络带宽不断提高以及应用层协议逐渐复杂多样的趋势下，许多网络应用与端口的相关性越来越小，伪装端口以及动态端口等情况使得上述方法已经很难适应技术和应用的发展与需求，这就迫切需要引入新的理论和技术，深层次挖掘网络应用的内在特征。为了适应Internet流量数据庞大、应用属性动态变化的特点，利用机器学习方法处理流量分类问题成为当前网络测量领域内一个新兴的研究热点。例如：朴素贝叶斯算法、改进贝叶斯算法、决策树算法、KNN算法、支持向量机算法、神经网络算法以及各种聚类算法等等。基于机器学习的流量分类技术不依赖于传输层端口号或解析有效负载来识别网络应用，而是利用流量在传输过程中表现出来的流的各种统计特征如包长、包间隔时间等来识别网络应用，方法本身不受伪装端口、动态端口、有效负载加密甚至网络地址转换的影响，在分类性能和灵活性方面，较之前述各种方法都有所突破。
然而，目前业界对流量分类技术的研究还远远无法满足业务发展的需求，主要体现在目前大多数技术都采用离线分类的手段，无法实现实时在线的分类。这就限制了流量分类技术在高速骨干网中的应用。
为了满足目前和未来高速骨干网的需要，流量分类技术迫切需要满足以下几点要求：1)分类准确性较高，避免采用端口或者净荷作为主要识别特征；2)算法复杂度较低，具体实现设计上要有并行化处理的特性，易于硬件实现(如FPGA、CPLD、ASIC等)，保证网络流量的高速在线分类；3)分类稳定性较好，能够适用于复杂多变的网络环境。
发明内容
本发明提供了一种基于决策树高速并行处理策略实现TCP流量在线分类的方法及装置，能够实现网络流量的高速实时在线分类，稳定性好，准确性高。
为实现上述的发明目的，本发明采用下述的技术方案：
一种基于决策树高速并行处理策略实现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中采用的最终特征序列相对应，需要按包到达顺序进行提取，并构建待分类流的特征序列，包的顺序信息按照到达观测点的时间顺序进行排列，取三次握手的第一个请求包即Setup包作为该流的第一个包。待分类流的特征序列存储在参数表中，参数表的一条记录包括五元组、各个包特征值以及参数是否满的标志。已分类被打上正确标签的包与未分类打上默认标签且需要进行参数提取的包需要进行时钟同步处理，即插入相应级别的流水线以保证数据包传输路线上的FIFO不会出现溢出现象。
步骤7，决策树查找：利用步骤6所得的待分类流的特征序列对步骤4所得的两块存储设备(如RAM、ROM、FLASH等)进行查找，判断该TCP流的类别值并更新流信息表。在查找过程中采用并行处理策略，仅需要两个时钟周期即可完成决策树的查找过程。即第一个时钟周期并行比较所有属性的所有中间节点值，确定该流所属的所有中间节点编码值并合并为一个数据，第二个时钟周期利用前一个时钟周期的结果数据并行比较所有边缘节点的编码值，从而确定该流的类别。
一种基于硬件设备(如FPGA、CPLD、ASIC等)的流量在线分类装置，用于实现上述的利用决策树高速并行处理策略实现TCP流量在线分类的装置包括在线部分和离线部分，其中离线部分具有决策树建树模块、决策树结构转换模块、分类结果处理模块；在线部分包括顺序连接的MAC层处理模块一、数据包轮询管理模块、分流判断模块、流量信息提取及打标签模块、决策树查找模块、MAC层处理模块二。其中，离线部分的决策树结构转换模块与在线部分的决策树查找模块相连接，离线部分的分类结果处理模块与在线部分的决策树查找模块通过一个流信息表间接连接。在线部分采用流水线处理技术。
决策树建树模块，用于根据前期真实网络数据流量建立决策树模型。
决策树结构转换模块，用于将决策树模型的结构进行转换，使之成为易于硬件实现的另一种数据结构并存储到硬件设备(如FPGA、CPLD、ASIC等)的存储设备(如RAM、ROM、FLASH等)中：通过对决策树的遍历，一方面提取决策树的中间节点值，对同一属性的各中间节点值进行从小到大的排序，然后对所有属性的各个中间节点值按顺序进行从小到大的编码，另一方面提取决策树的边缘节点值，对边缘节点值同样也进行编码，边缘节点值的编码是一个范围，取决于到达该边缘节点所经历的各中间节点的编码值。中间节点值及其编码以及边缘节点值及其编码分别存储在两块分离的存储设备(如RAM、ROM、FLASH等)中。
MAC层处理模块如今有许多现成的IP核可以采用。
数据包轮询管理模块，用于从N个数据包缓冲队列中读取数据包，此处采用轮询式访问每个输入队列，直到从一个队列读完一个完整的数据包才转到下一个队列。
分流判断模块，用于根据五元组将数据包划分到不同的流，判断该条流是否被分类，如果被分类，类别值是多少，并维护流信息表。流信息表用于记录流的五元组信息以及该条流的类别。流信息表仅由决策树查找模块进行更新处理，其他模块均不能对流信息表进行写操作。
流量信息提取及打标签模块，用于对未分类的数据包进行流特征提取并对所有数据包进行打标签处理。该模块需要维护一张参数表，参数表记录各条流的五元组信息、特征值以及特征值是否满的标志。特征值满的流的参数信息被发送到决策树查找模块。
决策树查找模块，用于利用流量信息提取及打标签模块发送的待分类流的特征序列对决策树结构转换模块所得的两块存储设备(如RAM、ROM、FLASH等)进行查找，判断该TCP流的类别值并更新流信息表。在查找过程中采用并行处理策略，仅需要两个时钟周期即可完成决策树的查找过程。即第一个时钟周期并行查找所有属性的所有中间节点值，确定该流所属的所有中间节点编码值并合并为一个数据，第二个时钟周期利用前一个时钟周期的结果数据并行查找所有边缘节点的编码值，从而确定该流的类别，并将分类结果发送至流信息表以对流信息表中的记录进行更新。
分类结果处理模块，用于对流量分类的结果进行汇总、处理及界面显示。
因此，本发明提供的流量分类方法和装置，具有以下优点：对决策树的结构进行了转换，使之转换成一种易于硬件实现的数据结构，降低了算法本身的复杂度；决策树查找过程中使用了并行查找和流水线技术，提高了处理速度；选取的包特征提取过程简单，易于在线完成；利用了决策树本身所具有的准确度高、稳定性好的特点。总之，较低的算法复杂度、高效的硬件在线实现方式、准确稳定的流量分类结果构成了本发明的最大特色。
附图说明
为了更清楚地说明本发明，下面将对本发明实施例描述中所需要使用的附图作简单的介绍，显然地，下面描述中的附图仅仅是本发明的流量分类方法流程图、流量分类装置的结构示意图，对于本领域普通技术人员来讲，在不付出创造性劳动前提下，还可以根据这些附图获得的更多的附图。
图1是本发明一个实施例提供的流量分类方法流程图；
图2是本发明一个实施例提供的流量分类装置的结构示意图；
具体实施方式
下面将结合本发明实施例的附图，对本发明实施例中的技术方案和装置进行清楚、完整地描述。此具体实施方式以决策树中C4.5算法为例进行详细描述，但是此方法同样适适用于其它决策树算法。此实施例基于FPGA实现，采用的存储设备是RAM，同样适用于其他硬件设备(如FPGA、CPLD、ASIC等)及存储设备(如RAM、ROM、FLASH等)。显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明的保护范围。
图1为本发明一个实施例提供的流量分类方法的流程图，该方法包括：
S101：在不同时间从不同地点收集多个网络流量数据集，并对数据集进行分流和手工分类。
网络流量分类装置一般部署在一定的网络中。决策树算法需要利用网络中的真实流量进行训练，以构建决策树分类模型，因此需要在准备部署的网络中设置网络探针，以便从网络中采集真实流量。上述的真实流量数据集包括用于手工分类确定流量协议类型所需的信息，以及数据包长、包间隔时间、包方向等后续步骤所需的特征参数；从传输层协议上看，数据流中至少包含TCP流和UDP流。需要把流量数据集按照{源地址、目的地址、源端口、目的端口、传输层协议类型}五元组将所得流量数据集分离为不同的TCP流，这样流量数据集就变为了TCP流的集合；其中，TCP流的头部的判断依据可以使用但不限于TCP流中的Setup、Setup/ACK、ACK数据包；并且一个数据流中数据包必须按照达到观测点的先后顺序排列。采用载荷分析等方法，以离线方式获得TCP数据流的协议类型，如WWW、MAIL、FTP、P2P等。
S102：提取前期TCP流集合的若干个包特征。
提取每一条TCP流中关于数据包的特征，即提取每条流头部10个包的包长、包间隔时间以及包传送方向。在本步骤，提取的每条流的包特征有三大类，一类是包长属性，一类是包间隔属性、另一类是包方向。也就是第一个包的包长、第二个包的包长、第三个包的包长……第十个包的包长；第一个包与第零个包的间隔时间(为0)、第二个包与第一个包的间隔时间、第三个包与第二个包的间隔时间…….第十个包与第九个包的间隔时间；第一个包的方向、第二个包的方向、第三个包的方向……第十个包的方向。并按照数据包在该TCP流的先后顺序构建初步特征序列，然后利用特征选择算法对包特征进行筛选，得到最终特征序列。
S103：建立决策树分类模型。
利用高级编程语言如Java、Matlab等或直接利用机器学习Weka软件，根据前期真实网络数据流量，基于经典的C4.5算法建立决策树模型。
S104：对决策树进行结构转换并存储到FPGA的RAM中。
通过对决策树的遍历，一方面提取决策树的中间节点值，即对所有的路径进行从上到下的遍历及中间节点值的提取。一条路径上可能有基于不同属性的中间节点，同一种属性的中间节点也可能存在于不同的路径上。对一棵树的所有中间节点值进行提取后汇总结果，然后对同一属性的各中间节点值进行从小到大的排序，然后对所有属性的各个中间节点值按顺序进行从小到大的编码。例如，若包长属性的中间节点值从小到大分别为70、80、90、100、110，编码位数为3，则中间节点值70编码为000，中间节点值80编码为001，中间节点值90编码为010，中间节点值100编码为011，中间节点值110编码为100；包间隔属性及包方向属性中间节点值的编码与此类似。另一方面提取决策树的边缘节点值，对边缘节点值同样也进行编码，边缘节点值的编码是一个范围，取决于到达该边缘节点的路径所经历的各中间节点的编码值。中间节点值及其编码以及边缘节点值及其编码分别存储在两块分离的RAM中。其中在流量分类装置用于网络流量在线分类之前，以离线处理的方式建立决策树并对决策树进行数据结构转换。
两块RAM的存储结构如表1、表2所示。表中一行为一个记录，每一个记录存储一个中间节点值及该中间节点值的编码值。其中，n1表示第1个属性的中间节点总数，n2表示第2个属性的中间节点总数，nk表示第k个属性的中间节点总数，m表示协议类型的总数。
表1中间节点值及其编码值在RAM中的存储方式
| 中间节点值 | 中间节点编码值 |
| 第1个属性第1个中间节点值 | 第1个属性第1个中间节点编码值 |
| 第1个属性第2个中间节点值 | 第1个属性第2个中间节点编码值 |
| … | … |
| 第1个属性第n1个中间节点值 | 第1个属性第n1个中间节点编码值 |
| 第2个属性第1个中间节点值 | 第2个属性第1个中间节点编码值 |
| 第2个属性第2个中间节点值 | 第2个属性第2个中间节点编码值 |
| … | … |
| 第2个属性第n2个中间节点值 | 第2个属性第n2个中间节点编码值 |
| …………………… | ……………………….. |
| 第k个属性第1个中间节点值 | 第k个属性第1个中间节点编码值 |
| 第k个属性第2个中间节点值 | 第k个属性第2个中间节点编码值 |
| … | … |
| 第k个属性第nk个中间节点值 | 第k个属性第nk个中间节点编码值 |
表2节点值及其编码值在RAM中的存储方式
| 节点值(即类别值) | 节点编码值 |
| 第1种协议类型值 | 第1种协议类型编码值范围 |
| 第2种协议类型值 | 第2种协议类型编码值范围 |
| …………………… | ……………………. |
| 第m种协议类型值 | 第m种协议类型编码值范围 |
S105：对待分类的数据包进行分流
根据{源地址、目的地址、源端口、目的端口、传输层协议类型}五元组将数据包划分到不同的流并维护流信息表，流信息表用于记录流的五元组信息以及该条流的类别。在此，仅对语义完整的TCP流进行分析。以TCP的3次握手为流的开始，以TCP的FIN＝1或RST＝1作为流的结束。根据网络中报文的五元组信息{源地址、目的地址、源端口、目的端口、传输层协议类型}判断是否为一条流。若五元组相同，则属于同一个流。否则，为不同的流。其中，若两个包的源地址相同，则属于同向网络流；若源地址与目的地址相同，则属于反向网络流；并约定，以第一个报文的转发方向为该网络流的上行方向。此外，若两个报文间隔超过一定时间，则属于不同的网络流。流信息表中每一条记录包括如下内容：标识一条流的ID、{源地址、目的地址、源端口、目的端口、传输层协议类型}五元组、识别出来的协议类型。流信息表仅需要保存已分类的流的记录，不需要保存未分类的流的记录，因此对流信息表进行查找时，若不存在记录则可以立即判断为未分类，从而节省查找时间。
S106：判断该数据包所属的TCP流是否已分类
利用S105提取的数据包的五元组信息，对流信息表进行查找，看表中是否已存在该五元组代表的流所对应的记录，如果存在记录，则读出该条流的类别值，如果不存在记录，则该条流未被分类。
S107：对已分类的数据包打上正确标签
利用步骤S106获取的类别信息对所有经过的数据包进行打标签处理，若数据包所属的流已经被分类，则打上相应的类别标签，分类结束。
S108：对未分类的数据包打上默认标签并提取待分类TCP流的包特征
对于未分类的数据包，按照一定的原则标记一个默认的标签，然后判断该数据包是否需要被提取包特征并做相应处理。在这里，包特征的提取与S102中采用的最终特征序列相对应，即提取第某个包或某些包的某个属性或某些属性是与S102中的最终特征序列相一致的，需要按包到达顺序进行提取，并构建待分类流的特征序列。与流信息表类似，流量信息提取模块也要维护一张参数表，参数表中每一条记录包括如下内容：标识一条流的ID、源地址、目的地址、源端口、目的端口、传输层协议类型}五元组、某个包与前一个包的间隔时间、某个包的包长、某个包的包方向、该条流参数是否已满标志。
网络数据(即数据包传输过程中的帧)传输是不受影响的，原因在于流量信息提取模块像一颗数据探针，仅仅将路过该模块的参数信息拷贝出来，而不改变任何数据以及数据的传输时序。
S109，决策树查找。
利用S108所得的待分类流的特征序列对S104所得的两块RAM进行查找，判断该TCP流的类别值并更新流信息表。在查找过程中采用并行处理策略，仅需要两个时钟周期即可完成决策树的查找过程。即第一个时钟周期并行比较所有属性的所有中间节点值，确定该流所属的所有中间节点编码值。也就是说，第一个时钟周期需要完成第1个属性的n1个中间节点值的比较以确定第1个属性所属的中间节点值范围区间，完成第2个属性的n2个中间节点值的比较以确定第2个属性所属的中间节点值范围区间……完成第k个属性的nk个中间节点值的比较以确定第k个属性所属的边缘节点值范围区间，而这n1+n2+…+nk个比较器是同时并行开始执行的。第一个时钟周期结束后，即可确定该流所属的所有属性的中间节点范围，通过RAM中的记录同时可以确定该流所属的所有中间节点编码值，其中一个属性对应一个中间节点编码值，则一条流对应k个中间节点编码值，将这k个中间节点编码值合并为一个数据，第二个时钟周期利用前一个时钟周期的合并结果数据并行比较所有边缘节点编码值，从而确定该流的边缘节点值，也就是协议类别值。
图2为本发明所提供的流量分类装置的结构示意图。
从功能上看，该流量分类装置可以分为在线和离线两个部分。离线部分主要完成决策树的构造及数据结构转换；在线部分主要负责未知数据流的分类。离线部分包括顺序连接的前期数据流量采集模块201、前期数据流分流模块202、前期数据流人工分类模块203、前期数据流特征提取模块204、决策树建树模块205、决策树结构转换模块206以及后期的分类结果处理模块207；在线部分包括顺序连接的MAC层处理模块一211、数据包轮询管理模块212、分流判断模块213、流量信息提取及打标签模块214、决策树查找模块215、MAC层处理模块二216。
在本流量分类装置中，前期数据流量采集模块201、前期数据流分流模块202、前期数据流人工分类模块203、前期数据流特征提取模块204、决策树建树模块205、决策树结构转换模块206可在装置部署前完成，因此不是使用流量分类的装置或者系统的必要组成部分。而MAC层处理模块一211、数据包轮询管理模块212、分流判断模块213、流量信息提取及打标签模块214、决策树查找模块215、MAC层处理模块二216、分类结果处理模块207一般应在使用流量分类的装置或系统中出现。
每一模块具体功能和处理流程如下：在带有流量分类的装置或系统使用前，需要使用前期数据流量采集模块201、前期数据流分流模块202、前期数据流人工分类模块203、、前期数据流特征提取模块204、决策树建树模块205、决策树结构转换模块206完成图1中S101～S104的工作，形成的经过转换的决策树数据结构置于装置中的RAM中。当一个未知类别的数据包进入流量分类装置后，而MAC层处理模块一211、数据包轮询管理模块212对数据包进行预处理，分流判断模块213根据{源地址、目的地址、源端口、目的端口、传输层协议类型}五元组将数据包划分到不同的流并维护流信息表，然后对流信息表进行查找以确定数据包所属的类别，完成图1中S105～S106的工作。流量信息提取及打标签模块214根据分流判断模块213所获取的类别信息对数据包进行打标签处理，同时按数据包先后顺序，依次提取包长、修正包间隔时间、传送方向等参数，形成特征序列，送入决策树查找模块215、完成图1中S107～S109的工作。流信息表仅由决策树查找模块215进行更新处理，其他模块均不能对流信息表进行写操作。MAC层处理模块二216及分类结果处理模块207对数据包进行后续的处理并显示分类结果。
本实施例提供的方法和装置，对采用C4.5算法建立的决策树进行了数据结构转换，使之转换成一种易于硬件实现的数据结构，降低了算法本身的复杂度；决策树查找过程中使用了并行查找和流水线技术，提高了处理速度；选取的包特征提取过程简单，易于在线完成；利用了C4.5算法本身所具有的准确度高、稳定性好的特点。因此，本实施例可以方便的实现网络流量的高速在线分类。
最后应说明的是：以上实施例仅用以说明本发明的技术方案及装置，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解；其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。