基于网络流量统计信息的快速网包分类方法

摘要

本发明涉及一种基于网络流量统计信息的快速网包分类方法，属于网络流量过滤和监控技术领域。根据分类规则集确定包头各个域的空间划分及其规则映射表，建立地址查找表、端口查找表和规则查找表；记录网包包头在各个域空间划分中出现的次数并计算先验分布；根据先验分布建立各个域的字母搜索树；根据字母搜索树及查找表对接收的网包包头进行连续匹配；在更新时刻重新计算先验分布并更新字母搜索树，继续对接收的网络流量进行匹配。本方法从网包分类的两个不同层面使用了分类规则集以及网络流量的启发信息，增强了分类方法的适应性，提高了平均分类效率。本发明查找速度快、可适应性强，能够在多种平台上实现，适用于高性能网络流量的过滤和监控。

说明书

技术领域

本发明涉及一种基于网络流量统计信息的快速网包分类方法，属于网络流量过滤和监控技术领域。

背景技术

互联网已成为当今社会的重要基础设施之一，网络应用对信息交换的高效性和安全性需求也随之不断提高。路由器除需具备传统的转发功能外，还必须能够支持访问控制、QoS、流量计费等功能。这些功能都要求路由器能根据网包包头对网络流量进行分类，并据此对网包进行不同方式的处理。网包分类通常指的是根据网包包头第三层、第四层的域来匹配过滤规则，并根据匹配结果对网包进行相应的处置。网包第三、第四层的包头域主要包括：源/目的网络层地址(各32位)，源/目的传输层端口(各16位)，协议类型(8位)等。大多数的网包分类方法均限制在这5个域上，在根据协议类型进行初分类之后，可以看作是对剩余4个域的网包分类。本发明提出的方法以4个域的分类作为示例，并能够扩展到支持任何维度的多域网包分类问题。

网包分类方法一直是国际学术界和工业界备受关注的课题。现有的千兆级以上的高端路由器大多采用基于ASIC/FPGA等专用芯片的解决方案。然而，基于专用芯片的设备价格昂贵，开发周期长，更新代价高，限制了高性能网关设备的广泛使用。因此，探索和开发具有可移植性、能适应多种硬件平台的高性能网包分类方法，成为推广高性能网关设备使用的有效途径。近年来，学术界提出了一系列网包分类方法，主要包括两类：基于树结构的Grid-of-Trie，ABV，HiCuts，HyperCuts等方法，以及基于表结构的Cross-producting，RFC，HSM等方法。

这些方法从不同角度挖掘网包分类规则集的结构特性，并通过启发信息来缩小搜索空间，从而加速方法执行速度。然而，网包分类问题涉及的是网络流量与分类规则集的匹配问题，现有的大多数方法仅仅从考虑从分类规则集的结构特性中挖掘启发信息来提高网包分类速度，而忽略了利用网络流量统计特性来提高性能。实际上，在网包分类实例中，位于特定网关位置的大部分网络流量往往只匹配规则集中的少量规则，而其余规则却很少被匹配。这是因为网包分类规则具有完备性，需要考虑防备各种可能的非授权访问，而特定网关位置的网络流量大部分属于正常访问流量，或者仅有少量的非授权访问，因此只会匹配规则集中的少量规则。这种网络流量在规则集匹配上的不均匀性，为加快网包分类方法的速率提供了新的途径。

发明内容

本发明的目的在于提供一种基于网络流量统计信息的快速网包分类方法，通过挖掘网络流量的启发信息，优化网包包头各个域的查找树结构，并通过层次化的空间映射表来实现快速的网包分类。

本发明提出的基于网络流量统计信息的快速网包分类方法，包括以下各步骤：

(1)根据用户预先设定的网包分类规则集，分别确定网包包头的源网络层地址、目的网络层地址、源传输层端口、目的传输层端口四个域在各自全空间中的空间划分，为四个域分别建立空间划分与网包分类规则之间的第一、第二、第三、第四规则映射表；

(2)以源网络层地址的空间划分序号SIP₁～SIP_u为列，以目的网络层地址的空间划分序号DIP₁～DIP_v为行，建立地址查找表，根据上述第一和第二规则映射表，分别将与源网络层地址的每个空间划分SIP_a相对应的规则映射和与目的网络层地址的每个空间划分DIP_b相对应的规则映射做“位与”运算，其中1≤a≤u，1≤b≤v，对运算所得的每个非重复的规则映射按出现的先后进行编号，得到地址编号AST₁～AST_p，并将编号1～p写入以SIP_a为列、以DIP_b为行的地址查找表中的相应单元中，同时建立地址编号AST₁～AST_p与网包分类规则之间的第五规则映射表；

(3)以源传输层端口的空间划分序号SP₁～SP_m为列，以目的传输层端口的空间划分序号DP₁～DP_n为行建立端口查找表，根据上述第三和第四规则映射表，分别将与源传输层端口的每个空间划分SP_c相对应的规则映射和与目的传输层端口的每个空间划分DP_d相对应的规则映射做“位与”运算，其中1≤c≤m，1≤d≤n，对运算所得的每个非重复的规则映射按出现的先后进行编号，得到端口编号PST₁～PST_q，并将编号1～q写入以SP_c为列、以DP_d为行的端口查找表的单元中，同时建立端口编号PST₁～PST_q与网包分类规则之间的第六规则映射表；

(4)以地址查找表中的地址编号AST₁～AST_p为列，以端口查找表中的端口编号PST₁～PST_q为行，建立规则查找表，根据上述第五和第六规则映射表，分别将与地址查找表中的每个地址编号AST_e相对应的规则映射和与端口查找表中的每个端口编号PST_f相对应的规则映射做“位与”运算，其中1≤e≤p，1≤f≤q，从右至左在运算所得的每个的规则映射中查找第一个为1的比特位的序号，将该序号写入以AST_e为列、以PST_f为行的端口查找表的单元中，该序号为匹配的优先级最高的规则序号，删除第一至第六规则映射表；

(5)根据用户设定的采样间隔，记录网络流量中输入的网包包头在各个域的空间划分中出现的次数，并在更新时刻对各个域的统计信息做归一化处理，从而得到各个域在空间划分中的先验分布；

(6)根据各个域在空间划分中的先验分布，利用字母搜索树分别建立一棵空间搜索树；

(7)对接收到的网包进行规则匹配：

根据网包包头的源/目的网络层地址，源/目的传输层端口四个域，利用四个域的字母搜索树分别确定网包包头四个域所在的空间划分的序号；

利用源/目的网络层地址的空间划分序号，检索地址查找表，同时利用源/目的传输层端口的空间序号检索端口查找表；

利用检索地址查找表得到的地址编号以及检索端口查找表得到的端口编号检索规则查找表，得到最终匹配的网包分类规则序号，并根据此序号指示的规则对网包进行放行或者阻止操作；

(8)重复步骤(7)，对网络流量中的网包进行连续匹配，并根据用户预先设定的更新频率，在更新时刻到来时，重新执行步骤(5)～(8)。

上述方法的步骤(5)中，根据用户设定的采样间隔，记录网络流量输入的网包包头在各个域的空间划分中的出现的次数，并在更新时刻对各个域的统计信息做归一化处理，从而得到各个域在空间划分中的先验分布，其具体过程如下：

(5-1)设采样间隔为N个网包，从输入的网络包头信息队列中每N个连续到达的网包中抽取一个五元组包头信息作为一个采样样本，每个样本由下述四个域组成的数据组：

32位源网络层地址，用int32 SIP表示，int表示整数类型，下同；

32位目标网络层地址，用int32 DIP表示；

16位源传输层端口，用int16 SP表示；

16位目标传输层端口，用int16 DP表示；

(5-2)记录采样所得的样本网包包头在各个域的空间划分中出现的次数：

用数组int32 Stats_SIP[u]记录采样的网络包头在源网络层地址的u个空间划分中分别出现的次数；

用数组int32 Stats_DIP[v]记录采样的网络包头在目的网络层地址的v个空间划分中分别出现的次数；

用数组int32 Stats_SP[m]记录采样的网络包头在源传输层端口的m个空间划分中分别出现的次数；

用数组int32 Stats_DP[n]记录采样的网络包头在目的传输层端口的n个空间划分中分别出现的次数；

(5-3)最后做归一化，得到网包包头各个域在其空间划分中的先验分布，归一化的方法为：

对于源网络层地址，其空间划分的先验分布为：

$\mathrm{Prior}\_\mathrm{SIP}\left[i\right]=\frac{\mathrm{Stats}\_\mathrm{SIP}\left[i\right]}{\underset{j=1}{\overset{u}{\Sigma }}\mathrm{Stats}\_\mathrm{SIP}\left[j\right]},$其中1≤i≤u，

对于目的网络层地址，其空间划分的先验分布为：

$\mathrm{Prior}\_\mathrm{DIP}\left[i\right]=\frac{\mathrm{Stats}\_\mathrm{DIP}\left[i\right]}{\underset{j=1}{\overset{v}{\Sigma }}\mathrm{Stats}\_\mathrm{DIP}\left[j\right]},$其中1≤i≤v，

对于源传输层端口，其空间划分的先验分布为：

$\mathrm{Prior}\_\mathrm{SP}\left[i\right]=\frac{\mathrm{Stats}\_\mathrm{SP}\left[i\right]}{\underset{j=1}{\overset{m}{\Sigma }}\mathrm{Stats}\_\mathrm{SP}\left[j\right]},$其中1≤i≤m，

对于目的传输层端口，其空间划分的先验分布为：

$\mathrm{Prior}\_\mathrm{DP}\left[i\right]=\frac{\mathrm{Stats}\_\mathrm{DP}\left[i\right]}{\underset{j=1}{\overset{n}{\Sigma }}\mathrm{Stats}\_\mathrm{DP}\left[j\right]},$其中1≤i≤n。

本发明提出的基于网络流量统计信息的网包分类方法，不仅利用网包分类规则集的空间划分启发式信息来建立快速查找表，并且通过挖掘网络流量中的启发信息，进一步优化单个域的查找速度。本方法集成了两个不同层面的启发式信息来优化算法数据结构，避免了单一式启发算法在特定网络环境下性能骤降所带来的缺陷，从而达到较好的稳定性和平衡性。并且，由于采用网络流量统计信息作为先验知识，使得本方法具有自适应性调节能力，提高平均分类效率。

与现有的网包分类方法相比，现有的千兆级以上的高端路由器大多采用基于ASIC/FPGA等专用芯片的解决方案。然而，基于专用芯片的设备价格昂贵，开发周期长，更新代价高，限制了高性能网关设备的广泛使用。本发明提出的网包分类方法查找速度快，可适应性强，并且能够在多种平台上实现，包括通用处理器平台、网络处理器平台、以及多核处理器平台。本发明结合高性能处理器平台的软硬件一体化方案，为降低高端路由器和防火墙的成本提供了可能，势必推动网络安全设备的广泛实施。

附图说明

图1是本发明中对接收的网包进行规则匹配的流程框图。

图2是本发明方法的数据结构图示例。

图3是目的传输层端口的字母搜索树示例。

图4是目的传输层端口的平衡二叉搜索树示例。

图5是更新后的目的传输层端口的字母搜索树示例。

具体实施方式

本发明提出的基于网络流量统计信息的快速网包分类方法，包括以下各步骤：

(1)根据用户预先设定的网包分类规则集，针对网包包头的源网络层地址(SIP)、目的网络层地址(DIP)、源传输层端口(SP)、目的传输层端口(DP)四个域，分别确定其在各自全空间中的空间划分，然后分别为四个域建立其空间划分与网包分类规则之间的规则映射表(Rule Bitmap)，以标识每个域的每个空间划分被哪些规则所覆盖：

网包分类规则集中的每条规则通常包含6个属性：规则序号用来标记规则，同时也给出了规则的优先级，序号越小，优先级越高。源地址给出32位的源地址范围，目的地址给出32位的目的地址范围，源端口给出16位源端口范围，目的端口给出16位目的端口范围，动作指出对匹配该规则的网包所进行的动作，即放行或阻止该网包；

源网络层地址的全空间大小为2³²，按照网包分类规则集中的所有规则将源网络层地址全空间分割为互不重叠的空间划分，将空间划分分别编号为SIP₁～SIP_u，每个空间划分对应一个规则映射(Bitmap)(即一个比特串)，规则映射从低位至高位的第k个比特位标识了该空间划分是否被网包分类规则集的第k条规则覆盖，1表示被覆盖，0表示不被覆盖；

目的网铬层地址的全空间大小为2³²，按照网包分类规则集中的所有规则将目的网络层地址全空间分割为互不重叠的空间划分，其空间划分分别编号为DIP₁～DIP_v，每个空间划分对应一个规则映射(Bitmap)(即一个比特串)，规则映射从低位至高位的第k个比特位标识了该空间划分是否被网包分类规则集的第k条规则覆盖，1表示被覆盖，0表示不被覆盖；

源传输层端口的全空间大小为2¹⁶，按照网包分类规则集中的所有规则将源传输层端口全空间分割为互不重叠的空间划分，其空间划分分别编号为SP₁～SP_m，每个空间划分对应一个规则映射(Bitmap)(即一个比特串)，规则映射从低位至高位的第k个比特位标识了该空间划分是否被网包分类规则集的第k条规则覆盖，1表示被覆盖，0表示不被覆盖；

目的传输层端口的全空间大小为2¹⁶，按照网包分类规则集中的所有规则将目的传输层端口全空间分割为互不重叠的空间划分，其空间划分分别编号为DP₁～DP_n，每个空间划分对应一个规则映射(Bitmap)(即一个比特串)，规则映射从低位至高位的第k个比特位标识了该空间划分是否被网包分类规则集的第k条规则覆盖，1表示被覆盖，0表示不被覆盖；

(2)以源网络层地址的空间划分序号SIP₁～SIP_u为列，以目的网络层地址的空间划分序号DIP₁～DIP_v为行，建立地址查找表(Address Search Table)，根据上述第一和第二规则映射表，分别将与源网络层地址的每个空间划分SIP_a(1≤a≤u)相对应的规则映射和与目的网络层地址的每个空间划分DIP_b(1≤b≤v)相对应的规则映射做“位与”运算，对运算所得的每个非重复的规则映射按出现的先后进行编号，得到地址编号AST₁～AST_p，并将编号1～p写入以SIP_a为列、以DIP_b为行的地址查找表中的相应单元中，同时建立地址编号AST₁～AST_p与网包分类规则之间的第五规则映射表；

(3)以源传输层端口的空间划分序号SP₁～SP_m为列，以目的传输层端口的空间划分序号DP₁～DP_n为行建立端口查找表(Port Search Table)，根据上述第三和第四规则映射表，分别将与源传输层端口的每个空间划分SP_c(1≤c≤m)相对应的规则映射和与目的传输层端口的每个空间划分DP_d(1≤d≤n)相对应的规则映射做“位与”运算，对运算所得的每个非重复的规则映射按出现的先后进行编号，得到端口编号PST₁～PST_q，并将编号1～q写入以SP_c为列、以DP_d为行的端口查找表的单元中，同时建立端口编号PST₁～PST_q与网包分类规则之间的第六规则映射表；

(4)以地址查找表中的地址编号AST₁～AST_p为列，以端口查找表中的端口编号PST₁～PST_q为行，建立规则查找表(Policy Lookup Table)，根据上述第五和第六规则映射表，分别将与地址查找表中的每个地址编号AST_e(1≤e≤p)相对应的规则映射和与端口查找表中的每个端口编号PST_f(1≤f≤q)相对应的规则映射做“位与”运算，在运算所得的每个的规则映射(比特串)从低位至高位找出第一个为1的比特位的序号，将该序号写入以AST_e为列、以PST_f为行的端口查找表的单元中，该序号为匹配的优先级最高的规则序号，删除第一至第六规则映射表；

(5)根据用户设定的采样间隔，记录网络流量输入的网包包头在各个域的空间划分中的出现的次数，并在更新时刻对各个域的统计信息做归一化处理，从而得到各个域在空间划分中的先验分布；

假设采样间隔为N个网包，那么采样单元从输入的网络包头信息队列中的每N个连续到达的网包中抽取一个五元组包头信息作为一个采样样本，每个样本是一个由下述四个域组成的数据组：

32位源网络层地址，用int32 SIP表示，int表示整数类型，下同；

32位目标网络层地址，用int32 DIP表示；

16位源传输层端口，用int16 SP表示；

16位目标传输层端口，用int16 DP表示；

记录统计量：记录采样所得的样本网包包头在各个域的空间划分中出现的次数：

用数组int32 Stats_SIP[u]来记录采样的网络包头在源网络层地址的u个空间划分中分别出现的次数；

用数组int32 Stats_DIP[v]来记录采样的网络包头在目的网络层地址的v个空间划分中分别出现的次数；

用数组int32 Stats_SP[m]来记录采样的网络包头在源传输层端口的m个空间划分中分别出现的次数；

用数组int32 Stats_DP[n]来记录采样的网络包头在目的传输层端口的n个空间划分中分别出现的次数；

最后做归一化，得到网包包头各个域在其空间划分中的先验分布。归一化的方法为：

对于源网络层地址，其空间划分的先验分布为：

$\mathrm{Prior}\_\mathrm{SIP}\left[i\right]=\frac{\mathrm{Stats}\_\mathrm{SIP}\left[i\right]}{\underset{j=1}{\overset{u}{\Sigma }}\mathrm{Stats}\_\mathrm{SIP}\left[j\right]},$其中1≤i≤u，

对于目的网络层地址，其空间划分的先验分布为：

$\mathrm{Prior}\_\mathrm{DIP}\left[i\right]=\frac{\mathrm{Stats}\_\mathrm{DIP}\left[i\right]}{\underset{j=1}{\overset{v}{\Sigma }}\mathrm{Stats}\_\mathrm{DIP}\left[j\right]},$其中1≤i≤v，

对于源传输层端口，其空间划分的先验分布为：

$\mathrm{Prior}\_\mathrm{SP}\left[i\right]=\frac{\mathrm{Stats}\_\mathrm{SP}\left[i\right]}{\underset{j=1}{\overset{m}{\Sigma }}\mathrm{Stats}\_\mathrm{SP}\left[j\right]},$其中1≤i≤m，

对于目的传输层端口，其空间划分的先验分布为：

$\mathrm{Prior}\_\mathrm{DP}\left[i\right]=\frac{\mathrm{Stats}\_\mathrm{DP}\left[i\right]}{\underset{j=1}{\overset{n}{\Sigma }}\mathrm{Stats}\_\mathrm{DP}\left[j\right]},$其中1≤i≤n。

(6)根据各个域空间划分的先验分布，利用已有的字母搜索树(Alphabetic Search Tree)分别建立一棵空间搜索树，至此预处理完成；

(7)对接收到的网包进行规则匹配：

根据网包包头的源/目的网络层地址，源/目的传输层端口四个域，利用四个域的字母搜索树分别确定网包包头四个域所在的空间划分的序号；

利用源/目的网络层地址的空间划分序号，检索地址查找表，同时利用源/目的传输层端口的空间序号检索端口查找表；

利用检索地址查找表得到的地址编号以及检索端口查找表得到的端口编号检索规则查找表，得到最终匹配的网包分类规则序号，并根据此序号指示的规则对网包进行放行或者阻止操作；

(8)重复步骤(7)，对网络流量中的网包进行连续匹配，并根据用户预先设定的更新频率，在更新时刻到来时，重新执行步骤(5)～(8)。

以下介绍本发明的一个实施例：

本发明方法包括的八个步骤，可以分为三个阶段，预处理阶段、分类规则匹配阶段、以及数据结构更新阶段。预处理阶段包括步骤一至步骤六，其目的在于生成网包分类所需的数据结构；分类规则匹配阶段即步骤七，其目的是对输入的网络流量进行扫描和过滤；数据结构更新阶段即步骤八，其目的是在更新时刻到来时重新生成包头各个域的空间搜索树。以下就按照八个步骤的次序举例说明本发明的具体实施方法。

步骤一：根据网包分类规则集，针对网包包头的源网络层地址(SIP)、目的网络层地址(DIP)、源传输层端口(SP)、目的传输层端口(DP)四个域，分别确定其空间划分(Segmentation)，并为每个域的空间划分建立规则映射表(Rule Bitmap)。

网包分类规则集中的每条规则通常包含6个属性：规则序号用来标记规则，同时也给出了规则的优先级，序号越小，优先级越高。源地址给出32位的源地址范围，目的地址给出32位的目的地址范围，源端口给出16位源端口范围，目的端口给出16位目的端口范围，动作指出对匹配该规则的网包所进行的动作，即放行或阻止该网包。表1给出了一个网包分类规则集的示例，下面以目的传输层端口为例说明确定单个域空间划分以及为每个空间划分建立规则映射的过程。

  规则序号  源地址  目的地址  源端口  目的端口  动作  1  0.0.0.0～64.0.0.0.0  32.0.0.0～64.0.0.0  0～65535  20～21  放行  2  32.0.0.0～128.0.0.0  64.0.0.0～192.0.0.0  0～5000  53～53  阻止  3  32.0.0.0～192.0.0.0  64.0.0.0～128.0.0.0  0～65535  80～88  放行  4  0.0.0.0～255.255.255.255  0.0.0.0～255.255.255.255  0～65535  0～65535  阻止

表1网包分类规则集示例

按照表1所示的规则集，目的端口被4条规则分割成7个空间划分(Segmentation)，分割的方法是将各条规则目的端口的起始值和终止值作为分界点，将空间划分为没有交叉的单元，具体如表2第二列所示。

规则映射的生成方法是：针对每个空间划分，用一个比特串(Bitmap)来标识该空间划分被哪几条规则所覆盖。比特串从低位到高位分别代表规则1、2、3、4。例如，空间划分DP1只被规则4覆盖，那么其规则映射为1000；空间划分DP2被规则1和规则4所覆盖，那么其规则映射为1001。将目的端口的空间划分及其规则映射列成一张表，即构成了目的端口的规则映射表(即第四规则映射表)，如表2第三列所示。

此处以目的传输端口为例说明了空间划分和规则映射的生成方法，其他三个域的空间划分和规则映射生成方法与此相同。按照表1所示的规则集，源网络层地址、目的网络层地址的空间划分以及它们对应的第一、第二、第三规则映射表分别如表3、表4、表5所示。

  空间划分  取值范围  规则映射  DP1  0～19  1000  DP2  20～21  1001  DP3  22～52  1000  DP4  53～53  1010  DP5  54～79  1000  DP6  80～88  1100  DP7  89～65535  1000

表2目的传输层端口的空间划分与第四规则映射表示例

  空间划分  取值范围  规则映射  SIP1  0.0.0.0～31.255.255.255  1001  SIP2  32.0.0.0～63.255.255.255  1111  SIP3  64.0.0.0～127.255.255.255  1110  SIP4  128.0.0.0～191.255.255.255  1100  SIP5  192.0.0.0～255.255.255.255  1000

表3源网络层地址的空间划分与第一规则映射表示例

  空间划分  取值范围  规则映射  DIP1  0.0.0.0～31.255.255.255  1000  DIP2  32.0.0.0～63.255.255.255  1001  DIP3  64.0.0.0～127.255.255.255  1110  DIP4  128.0.0.0～191.255.255.255  1010  DIP5  192.0.0.0～255.255.255.255  1000

表4目的网络层地址的空间划分与第二规则映射表示例

  空间划分  取值范围  规则映射  SP1  0～5000  1111  SP2  5000～65535  1101

表5源传输层端口的空间划分与第三规则映射表示例

步骤二：根据源/目的网络层地址的空间划分对应的第一/第二规则映射表建立地址查找表(Address Search Table)，并为地址查找表中的每个单元设定相应的规则映射，从而建立与地址查找表对应的第五规则映射表。

依照表3和表4所示源/目的网络层地址的空间划分对应的第一/第二规则映射表，将得到如表6所示的地址查找表以及如表7所示的与地址查找表对应的第五规则映射表。其生成过程为：将SIP₁～SIP₅的规则映射分别与DIP₁～DIP₅的规则映射做“位与”运算，并对每个非重复的规则映射按出现的先后进行地址编号，并将序号记入地址查找表中，同时将序号及其规则映射存储在与地址查找表对应的第五规则映射表中。具体来说：首先，将SIP₁的规则映射1001与DIP₁的规则映射1000做“位与”运算，得到的规则映射为1000，将其编号为1，在地址查找表中将SIP₁与DIP₁的交叉位置记录序号1，并将序号1和规则映射1000存储在地址查找表的规则映射表中；接着，将SIP₁的规则映射1001与DIP₂的规则映射1001做“位与”运算，得到的规则映射为1001，将其编号为2，在地址查找表中将SIP₁与DIP₂的交叉位置记录序号2，并将序号2和规则映射1001存储在地址查找表的规则映射表中；然后，将SIP₁的规则映射1001与DIP₃的规则映射1110做“位与”运算，得到的规则映射为1000，由于已经出现过，其序号为1，因此只需在地址查找表中SIP₁与DIP₃的交叉位置记录序号1，而无需再次写入规则映射表；最后，依此规律完成SIP₁～SIP₅的规则映射与DIP₁～DIP₅的规则映射的“位与”运算。

  AST  SIP1  SIP2  SIP3  SIP4  SIP5  DIP1  1  1  1  1  1  DIP2  2  2  1  1  1  DIP3  1  3  3  5  1  DIP4  1  4  4  1  1  DIP5  1  1  1  1  1

表6地址查找表(Address Search Table)

  空间划分  规则映射  AST1  1000  AST2  1001  AST3  1110  AST4  1010  AST5  1100

表7与地址查找表对应的第五规则映射表

步骤三：根据源/目的传输层端口的空间划分对应的第三/第四规则映射表建立端口查找表(Port Search Table)，并为端口查找表中的每个单元设定相应的规则映射表，从而建立与端口查找表对应的第六规则映射表。

依照表5和表2所示源/目的网络层地址的空间划分对应的第三/第四规则映射表，将得到如表8所示的端口查找表以及如表9所示的端口查找表对应的第六规则映射表。其生成过程为：将SP₁～SP₂的规则映射分别与DP₁～DP₇的规则映射做“位与”运算，并对每个非重复的规则映射按出现的先后进行端口编号，，并将序号记入端口查找表中，同时将序号及其规则映射存储在与端口查找表对应的第六规则映射表中。其具体操作类似步骤二，不再赘述。

  PST  SP1  SP2  DP1  1  1

  DP2  2  2  DP3  1  1  DP4  3  1  DP5  1  1  DP6  4  4  DP7  1  1

表8端口查找表(Port Search Table)

  空间划分  规则映射  PST1  1000  PST2  1001  PST3  1010  PST4  1100

表9与端口查找表对应的第六规则映射表

步骤四：根据地址查找表对应的第五规则映射表以及端口查找表对应的第六规则映射表，建立规则查找表(Policy Lookup Table)，删除所有的规则映射表。

根据表7所示的与地址查找表对应的第五规则映射表以及表9所示的与端口查找表对应的第六规则映射表，将得到如表10所示的规则查找表。其生成方法为：将AST₁～AST₅的规则映射分别与PST₁～PST₄的规则映射做“位与”运算，将分别得到一个规则映射，由于规则映射指示了所匹配的规则序号，根据规则的优先级，将得到最终匹配的规则序号，将其存储在规则查找表中。举例来说，将AST₁的规则映射1000与PST₂的规则映射1001做“位与”运算，将得到规则映射1000，它指示了匹配的规则为规则4，因此在AST₁与PST₂的交叉位置写入规则序号4；再如，将AST₃的规则映射1110与PST₄的规则映射1100做“位与”运算，将得到规则映射1100，它指示了匹配的规则为规则3和规则4，根据规则的优先级，最终匹配的规则为规则3，因此在AST₃和PST₄的交叉位置写入规则序号3。依此类推。

在生成规则查找表之后，所有的规则映射表的作用已经完成，因此删除所有的规则映射表，包括源/目的网路层地址对应的第一/第二规则映射表，源/目的传输层端口对应的第三/第四规则映射表，地址查找表对应的第五规则映射表，以及端口查找表对应的第六规则映射表。

  PLT  AST1  AST2  AST3  AST4  AST5  PST1  4  4  4  4  4  PST2  4  1  4  4  4  PST3  4  4  2  2  4  PST4  4  4  3  4  3

表10规则查找表(Policy Lookup Table)

步骤五：采样单元根据采样间隔记录网络流量输入的网包包头在各个域的空间划分中的出现的次数，并在更新时刻对各个域的统计信息做归一化处理，从而得到各个域在其空间划分中的先验分布。

假设采样间隔为N个网包，那么采样单元从输入的网络包头信息队列中的每N个连续到达的网包中抽取一个五元组包头信息作为一个采样样本，每个样本是一个由下述四个域组成的数据组：

32位源网络层地址，用int32 SIP表示，int表示整数类型，下同；

32位目标网络层地址，用int32 DIP表示；

16位源传输层端口，用int16 SP表示；

16位目标传输层端口，用int16 DP表示；

记录统计量：记录采样所得的样本网包包头在各个域的空间划分中出现的次数。用数组int32 Stats_SIP[5]来记录采样的网络包头在源网络层地址的5个空间划分中分别出现的次数，用数组int32 Stats_DIP[5]来记录采样的网络包头在目的网络层地址的5个空间划分中分别出现的次数，用数组int32 Stats_SP[2]来记录采样的网络包头在源传输层端口的2个空间划分中分别出现的次数，用数组int32 Stats_DP[7]来记录采样的网络包头在目的传输层端口的7个空间划分中分别出现的次数。

最后做归一化，得到网包包头各个域在其空间划分中的先验分布。归一化的方法如下：

对于源网络层地址，其空间划分的先验分布为：

$\mathrm{Prior}\_\mathrm{SIP}\left[i\right]=\frac{\mathrm{Stats}\_\mathrm{SIP}\left[i\right]}{\underset{j=1}{\overset{u}{\Sigma }}\mathrm{Stats}\_\mathrm{SIP}\left[j\right]},$其中1≤i≤u，

对于目的网络层地址，其空间划分的先验分布为：

$\mathrm{Prior}\_\mathrm{DIP}\left[i\right]=\frac{\mathrm{Stats}\_\mathrm{DIP}\left[i\right]}{\underset{j=1}{\overset{v}{\Sigma }}\mathrm{Stats}\_\mathrm{DIP}\left[j\right]},$其中1≤i≤v，

对于源传输层端口，其空间划分的先验分布为：

$\mathrm{Prior}\_\mathrm{SP}\left[i\right]=\frac{\mathrm{Stats}\_\mathrm{SP}\left[i\right]}{\underset{j=1}{\overset{m}{\Sigma }}\mathrm{Stats}\_\mathrm{SP}\left[j\right]},$其中1≤i≤m，

对于目的传输层端口，其空间划分的先验分布为：

$\mathrm{Prior}\_\mathrm{DP}\left[i\right]=\frac{\mathrm{Stats}\_\mathrm{DP}\left[i\right]}{\underset{j=1}{\overset{n}{\Sigma }}\mathrm{Stats}\_\mathrm{DP}\left[j\right]},$其中1≤i≤n。

步骤六：根据各个域空间划分的先验分布，利用字母搜索树(Alphabetic Search Tree)分别建立一棵空间搜索树，至此预处理完成。

得到各个域空间划分的先验分布之后，为每个域建立一棵字母搜索树，其优点在于：相比于普通的二叉平衡搜索树，能够利用先验概率得到更短的平均树深度(Tree Depth)。在此，依然以目的传输层端口为例，假设表2所示的目的传输层端口的空间划分具有如表11所示的先验分布。

  空间划分 取值范围  先验概率  DP1 0～19  0.01  DP2 20～21  0.01  DP3 22～52  0.02  DP4 53～53  0.10  DP5 54～79  0.12  DP6 80～88  0.60  DP7 89～65535  0.14

表11目的传输层端口的先验分布示例

按照字母搜索树的生成方式，根据表11所示的先验概率分布，将得到如图3所示的目的传输层端口的字母搜索树，其深度为3.2。而如果采用不考虑先验概率的平衡二叉搜索树，其树结构将如图4所示，其深度为3.88。可见，在此示例中，采用字母搜索树能够将平均搜索深度减小18％。字母搜索树是加权搜索树的一种，其原理参见文献T.C.Hu and A.C.Tucker，Optimal computer search trees and variable length alphabetic codes，SIAM Journal onApplied Mathematics，21：514-532，1971.

其他三个域的字母搜索树的生成方式与此相同。

步骤七：对接收到的网包进行规则匹配：首先，针对网包包头的四个域，利用各个域的字母搜索树分别确定其所在的空间划分；其次，利用源/目的网络层地址的空间划分序号索引地址查找表，同时利用源/目的传输层端口的空间序号索引端口查找表；最后，利用索引地址查找表得到的序号以及索引端口查找表得到的序号索引规则查找表，得到最终匹配的网包分类规则序号。

举例来说，假设接收到的网包包头源网络层地址为166.111.120.83，目的网络层地址为72.155.10.25，源传输层端口为3300，目的传输层端口为80，而规则集依然如表1所示。首先，利用四个域的字母搜索树，将得到源网络层地址所在的空间划分为SIP₄，目的网络层地址所在的空间划分为DIP₃，源传输层端口所在的空间划分为SP₁，目的传输层端口所在的空间划分为DP₆。其次，利用源网络层地址所在的空间划分序号SIP₄和目的网络层地址所在的空间划分序号DIP₃索引地址查找表，按照表6所示的地址查找表将得到序号5，同时利用源传输层端口所在的空间划分SP₁以及目的传输层端口所在的空间划分DP₆索引端口查找表，按照表8所示的端口查找表将得到序号4。最后，利用索引地址查找表得到的序号AST₅，以及索引端口查找表得到的序号PST₄，索引表10所示的规则查找表，将得到最终的匹配规则序号3。

步骤八：重复步骤七，对网络流量中的网包进行连续匹配，并根据预先设定的更新频率，在更新时刻到来时，重新执行步骤五～步骤八。

按照步骤七的方法，对接收到的网包包头进行连续匹配，并根据匹配的规则做相应的放行或阻止操作。

在更新时刻到来时，重新执行步骤五～步骤八，即将上一个更新时刻至本更新时刻之间的统计量进行归一化，并据此更新各个域的字母搜索树结构，然后利用新产生的搜索树继续查找过程，即对网络流量中的网包进行连续匹配。

在此，特别举例说明调整字母搜索树的过程。假设表11所示的目的传输层端口的先验分布中，DP₂的先验概率变为0.6，而DP₆的先验概率变为0.01，那么图3所示的目的传输层端口的搜索树深度将为4.88，反而大于平衡二叉树搜索树的深度3.88，因此调整字母搜索树结构变得非常必要。根据新的先验概率分布，将得到图5所示的更新后的目的传输层端口的字母搜索树。

更新后的字母搜索树深度为3.79，仍然小于平衡二叉搜索树的深度3.88，更远小于更新之前的字母搜索树深度4.88。

本发明中根据网络流量统计信息来定时更新单个域空间搜索树的思想，能够根据不同网络的流量特性以及网络不同时段的统计特性来变换网包分类方法的数据结构，从而加速网包分类方法速度，同时增加了网络分类方法的可适应性和稳定性。除此之外，本发明利用了网络分类规则的特性来提取启发信息，通过规则映射表的辅助，生成了三张空间查找表(地址查找表、端口查找表及规则查找表)，这样在得到各个域的空间划分序号之后，只需要额外的三次表格索引即可得到最终的匹配规则序号。

本方法从网包分类问题的两个不同层面结合使用了分类规则集以及网络流量的启发信息，避免了单一启发式算法性能受数据结构变化影响较大带来的问题。流量统计特性的引入，使得该方法通过先验概率而具有贝叶斯分类器特性，从而能够根据特定的网络结构和网络流量特性进行自适应调节，提高平均分类效率。

本发明提出的网包分类方法查找速度快，可适应性强，并且能够在多种平台上实现，包括通用处理器平台、网络处理器平台、以及多核处理器平台。本发明结合高性能处理器平台的软硬件一体化方案，为降低高端路由器和防火墙的成本提供了可能，势必推动网络安全设备的广泛实施。