一种适用于多类字段的高速数据流分类装置及方法

摘要

本发明提出了一种适用于多类字段的高速数据流分类装置及方法，主要用于解决现有流分类算法中存在的不适合多类字段高速查找的技术问题；其装置包括数据流处理模块、规则编码模块、规则匹配模块、优先级编码模块和指令码提取模块；其方法的步骤包括：用户定义匹配字段属性和数据流分类规则；数据流处理模块提取数据流中待匹配字段的关键信息；规则编码模块对用户定义的规则进行编码；规则编码模块对编码后规则进行存储及匹配；优先级编码模块对匹配结果进行优先级编码获得最终结果；指令码提取模块根据最终结果获取数据流对应的指令码信息。本发明具有支持多类字段的匹配、查找速度快、适用于硬件实现和大规模规则匹配时查找速度快的优点。

说明书

技术领域

本发明属于通信技术领域，涉及一种适用于多类字段的高速数据流分类装置及方法，可用于通信网络中的数据流的识别和分类。

背景技术

随着网络的发展，客户需要更加多样化和更加快速安全的服务。数据流是实时的、连续的、有序项的序列，数据流中蕴含大量信息，可以作为智能决策的依据。数据流分类模块作为交换机中至关重要的模块，承担了区分数据流的作用，流分类模块根据数据流中的信息对数据流进行区分，进而提供不同的操作。流分类模块的性能决定了交换机是否能够根据客户的需求提供精准、快速、多样的服务。

目前，流分类算法主要分为基于硬件实现的流分类算法、基于启发式算法的流分类方法和基于比特向量的流分类方法。基于硬件实现的流分类算法代表为利用TCAM实现的流分类方法，优点是利用硬件实现，查找速度快，缺点是不适于查找范围匹配字段，TCAM的容量小，价格高，功率大，不适合大规模的规则查找。基于启发式算法的流分类方法的代表是RFC流分类方法，优点是适合范围字段、最长前缀匹配字段和精确匹配字段，缺点是所需存储空间大，性能随规则数目增加下降明显。

基于比特向量的流分类方法，特点是将d维流分类问题分割为d个一维流分类子问题，为每个子问题建立一个二叉树结构，然后将子问题的流分类结果进行合并，优点是适合硬件实现，缺点是由于采用了二叉树结构所以不适合范围查找，并且当规则的规模较大时，读取寄存器的次数增加、查找速度变慢。已有研发人员针对比特向量的流分类方法的不适合规则规模大时数据流分类的缺点进行了改进，例如，申请公开号为CN 105959224 A，名称为“基于比特向量的高速路由查找装置及方法”的专利申请，公开了一种基于比特向量的高速路由查找装置及方法，实施步骤为：第一，将路由表中的存放的所有路由表项按网络前缀长度降序排序；第二，将路由表分割成多个路由表块；第三，将路由表块转换为比特向量阵列存放在存储器中；第四，从存储器中读出对应子地址中的比特向量按位相“与”；第五，找出最长前缀匹配的路由表项。该发明的优点是，采用了流水线形式的查找结构，使其保证了大规模规则匹配时的查找速度仍然较快，缺点是不能实现范围匹配，所以不适合多类字段的数据流分类问题。

发明内容

本发明的目的在于克服上述现有技术的不足，提出了一种适用于多类字段的高速数据流分类装置和方法，用于解决现有基于比特向量的流分类算法中存在的不适合多类字段高速查找的技术问题。

为实现上述目的，本发明采取的技术方案为：

一种适用于多类字段的高速数据流分类装置，包括数据流处理模块、规则编码模块、规则匹配模块、优先级编码模块和指令码提取模块，其中：

数据流处理模块，用于根据用户定义的每个匹配字段的属性，提取数据流中的关键信息并输出；

规则编码模块，用于对用户定义的数据流分类规则进行编码，并输出编码结果和指令码；

规则匹配模块，用于存储规则编码模块输出的编码后的数据流分类规则，并将该规则与数据流处理模块输出的关键信息进行匹配，再输出匹配结果；

优先级编码模块，用于对规则匹配模块输出的匹配结果进行优先级分析，得到最优匹配结果并输出；

指令码提取模块，用于存储规则编码模块输出的指令码，并按照优先级编码模块输出的最优匹配结果提取对应的指令码；

上述的一种适用于多类字段的高速数据流分类装置，所述数据流处理模块，包括关键信息提取模块、范围关键信息拼接模块和其他关键信息拼接模块，其中：

关键信息提取模块，用于对数据流信息进行分析，提取各匹配字段对应的关键信息并输出；

范围关键信息拼接模块，用于将关键信息提取模块输出的所有范围匹配字段对应的关键信息按照用户定义的顺序首尾相接后输出；

其他关键信息拼接模块，用于将关键信息提取模块输出的所有最长前缀匹配字段和精确匹配字段对应的关键信息按照用户定义的顺序首尾相接后输出；

上述的一种适用于多类字段的高速数据流分类装置，所述规则编码模块，包括规则预处理模块、第一规则编码器和第二规则编码器，其中：

规则预处理模块，用于对数据流分类规则按照规则的优先级从高到低的顺序进行排序，排序后将数据流分类规则中的指令码输出、并对其中包含的子规则进行分类；

第一规则编码器，用于对数据流分类规则中的范围匹配字段对应的子规则进行编码并输出；

第二规则编码器，用于对数据流分类规则中的精确匹配字段对应的子规则和最长前缀匹配字段对应的子规则进行编码并输出；

上述的一种适用于多类字段的高速数据流分类装置，所述规则匹配模块，包括并行的第一流水线、第二流水线和结果综合模块，其中：

第一流水线，用于存储第一规则编码器输出的编码结果，并将该规则与数据流处理模块输出的范围关键信息进行匹配；

第二流水线，用于存储第二规则编码器输出的编码结果，并将该规则与数据流处理模块输出的其他关键信息进行匹配；

结果综合模块，用于将第一流水线的匹配结果和第二流水线的匹配结果按位相与，得到数据流中的关键信息和数据流分类规则的匹配结果并输出；

上述的一种适用于多类字段的高速数据流分类装置，所述第一流水线，其存储器采用FPGA中的Block RAM，所述第二流水线，其存储器采用FPGA中的寄存器。

一种适用于多类字段的高速数据流分类方法，包括如下步骤：

(1)用户定义若干个匹配字段的属性和若干条数据流分类规则：

(1a)用户定义若干个匹配字段的属性，每个匹配字段的属性包括协议类型、匹配方式、128bit偏移、16bit偏移和掩码；

(1b)用户定义若干条数据流分类规则，每条数据流分类规则包括规则的优先级、指令码和各匹配字段对应的子规则，其中各匹配字段对应的子规则的定义方法为：

(i)如果匹配字段的匹配方式为精确匹配，则该匹配字段对应的子规则需定义匹配值；

(ii)如果匹配字段的匹配方式为最长前缀匹配，则该匹配字段对应的子规则需定义匹配值和掩码；

(iii)如果匹配字段的匹配方式为范围匹配，则该匹配字段对应的子规则需定义范围下限和范围上限；

(2)数据流处理模块根据用户定义的所有匹配字段的属性，提取数据流中的关键信息并输出：

(2a)关键信息提取模块对持续输入的数据流信息进行分析，并确定当前输入的数据流的两个属性：协议类型和距离起始符的128bit偏移，再将数据流的以上两个属性分别与所有匹配字段的协议类型、128bit偏移逐个比对，如果某匹配字段的协议类型、128bit偏移和数据流的协议类型、距离起始符的128bit偏移都相等时，根据该匹配字段的16bit偏移属性和掩码属性，输出当前数据流中该匹配字段对应的关键信息；否则，输出0；

(2b)范围关键信息拼接模块将所有范围匹配字段对应的关键信息按照用户定义的顺序首尾相接后输出；

(2c)其他关键信息拼接模块将所有最长前缀匹配字段的关键信息和精确匹配字段对应的关键信息按照用户定义的顺序首尾相接后输出；

(3)规则编码模块对用户定义的数据流分类规则进行编码：

(3a)规则预处理模块对数据流分类规则中包含的子规则进行分类：

(3a1)规则预处理模块将数据流分类规则按照规则的优先级从高到低的顺序进行排序，并逐条输出排序后的数据流分类规则的指令码；

(3a2)规则预处理模块将排序后的数据流分类规则中包含的子规则分为两类：一类为范围匹配字段对应的子规则，一类为最长前缀匹配字段对应的子规则和精确匹配字段对应的子规则；

(3b)第一规则编码器对数据流分类规则中的范围匹配字段对应的子规则进行范围比特向量编码并输出；

(3c)第二规则编码器对数据流分类规则中的精确匹配字段对应的子规则和最长前缀匹配字段对应的子规则进行跨步比特向量编码并输出；

(4)规则匹配模块对数据流分类规则编码结果进行存储和匹配：

(4a)第一流水线对第一规则编码器输出的编码结果进行存储，并将该规则的编码结果与数据流处理模块输出的范围关键信息进行匹配；

(4b)第二流水线对第二规则编码器输出的编码结果进行存储，并将该规则的编码结果与数据流处理模块输出的其他关键信息进行匹配；

(4c)结果综合模块将第一流水线的匹配结果和第二流水线的匹配结果按位相与，得到数据流中的关键信息和数据流分类规则的匹配结果并输出；

(5)优先级编码模块对规则匹配模块输出的匹配结果进行优先级分析：

优先级编码模块从高位向低位遍历规则匹配模块输出的匹配结果，确定其中第一个‘1’出现的位置，并将该位置的位置信息作为最优匹配结果并输出；

(6)指令码提取模块提取优先级编码模块输出的最优匹配结果对应的指令码：

(6a)指令码提取模块将规则编码模块输出的指令码存储在自身的指令码存储器中；

(6b)指令码提取模块将优先级编码模块输出的匹配结果作为指令码存储器的读地址，读取数据流对应的指令码信息，实现对数据流的分类。

本发明与现有技术相比，具有如下优点：

第一，本发明由于数据流处理模块、规则编码模块和规则匹配模块根据匹配方式不同，将匹配字段对应的关键信息和子规则都进行了分类处理，针对范围匹配字段对应的子规则进行了范围比特编码及对应的查找，克服了现有技术中不适合多类字段查找的缺点，可以同时完成高速最长前缀匹配、精确匹配和范围匹配，有效地扩大了数据流分类装置及方法的使用范围。

第二，本发明由于规则匹配模块采用的查找算法是基于比特向量的查找算法，内部结构采用两条并行流水线，其优点是查找速度快、适合硬件实现，在规则数目增大时仍能保证其性能，大大提升了数据流分类装置及方法的处理速度。

第三，本发明由于数据流处理模块是根据预定义的匹配字段属性进行数据流关键信息的提取，与数据流的协议无关，可匹配的字段灵活可变，只要预先根据数据流的一般结构对其定义即可，克服了现有方案只能完成特定字段提取的缺点，进一步扩大了数据流分类装置及方法的使用范围。

附图说明

图1为本发明分类装置的整体结构示意图；

图2为本发明分类方法的实现流程图；

图3为范围比特向量编码的流程图；

图4为跨步比特向量编码的流程图。

具体实施方式

下面结合附图和实施例，对本发明作进一步详细描述。

参照图1，一种适用于多类字段的高速数据流分类装置，包括数据流处理模块、规则编码模块、规则匹配模块、优先级编码模块和指令码提取模块，其中：

数据流处理模块，包括关键信息提取模块、范围关键信息拼接模块和其他关键信息拼接模块，用于根据用户定义的每个匹配字段的属性，提取数据流中的关键信息并输出，其中：

关键信息提取模块，用于对数据流信息进行分析，提取各匹配字段对应的关键信息并输出；

范围关键信息拼接模块，用于将关键信息提取模块输出的所有范围匹配字段对应的关键信息按照用户定义的顺序首尾相接后输出；

其他关键信息拼接模块，用于将关键信息提取模块输出的所有最长前缀匹配字段和精确匹配字段对应的关键信息按照用户定义的顺序首尾相接后输出；

规则编码模块，包括规则预处理模块、第一规则编码器和第二规则编码器，用于对用户定义的数据流分类规则进行编码，并输出编码结果和指令码，其中：

规则预处理模块，用于对数据流分类规则按照规则的优先级从高到低的顺序进行排序，排序后将数据流分类规则中的指令码输出、并对其中包含的子规则进行分类；

第一规则编码器，用于对数据流分类规则中的范围匹配字段对应的子规则进行编码并输出；

第二规则编码器，用于对数据流分类规则中的精确匹配字段对应的子规则和最长前缀匹配字段对应的子规则进行编码并输出；

规则匹配模块，包括并行的第一流水线、第二流水线和结果综合模块，用于存储规则编码模块输出的编码后的数据流分类规则，并将该规则与数据流处理模块输出的关键信息进行匹配，再输出匹配结果，其中：

第一流水线，其存储器采用FPGA中的Block RAM，用于存储第一规则编码器输出的编码结果，并将该规则与数据流处理模块输出的范围关键信息进行匹配；

第二流水线，其存储器采用FPGA中的寄存器，用于存储第二规则编码器输出的编码结果，并将该规则与数据流处理模块输出的其他关键信息进行匹配；

结果综合模块，用于将第一流水线的匹配结果和第二流水线的匹配结果按位相与，得到数据流中的关键信息和数据流分类规则的匹配结果并输出；

优先级编码模块，用于对规则匹配模块输出的匹配结果进行优先级分析，得到最优匹配结果并输出；

指令码提取模块，用于存储规则编码模块输出的指令码，并按照优先级编码模块输出的最优匹配结果提取对应的指令码。

参照图2，一种适用于多类字段的高速数据流分类方法，包括如下步骤：

步骤1)用户定义若干个匹配字段的属性和若干条数据流分类规则：

步骤1a)用户定义若干个匹配字段的属性，每个匹配字段的属性包括协议类型、匹配方式、128bit偏移、16bit偏移和掩码，其中：

协议类型：表示定义的匹配字段所处的协议类型；

匹配方式：分为范围匹配、最长前缀匹配和精确匹配三种方式，‘1’表示范围匹配方式，‘0’表示最长前缀匹配方式和精确匹配方式；

128bit偏移：表示匹配字段位于数据流起始位置之后的第n个128bit内；

16bit偏移：表示位于已确定的128bit中的第m个16bit内；

掩码：表示在已确定的16bit中的有效位；

例如，以太网MAC帧中包含的Vlan_id号处于距离数据流起始位置的第117位到第128位，且属于范围匹配字段，所以，Vlan_id的协议类型设置为00，匹配方式设置为1，128bit偏移配置为0，16bit偏移配置为7，掩码设置为0000_1111_1111_1111；

步骤1b)用户定义若干条数据流分类规则，每条数据流分类规则包括规则的优先级、指令码和各匹配字段对应的子规则，其中各匹配字段对应的子规则的定义方法为：

(i)如果匹配字段的匹配方式为精确匹配，则该匹配字段对应的子规则需定义匹配值；

(ii)如果匹配字段的匹配方式为最长前缀匹配，则该匹配字段对应的子规则需定义匹配值和掩码；

(iii)如果匹配字段的匹配方式为范围匹配，则该匹配字段对应的子规则需定义范围下限和范围上限；

步骤2)数据流处理模块根据用户定义的所有匹配字段的属性，提取数据流中的关键信息并输出：

步骤2a)关键信息提取模块对持续输入的数据流信息进行分析，并确定当前输入的数据流的两个属性：协议类型和距离起始符的128bit偏移，再将数据流的以上两个属性分别与所有匹配字段的协议类型、128bit偏移逐个比对，如果某匹配字段的协议类型、128bit偏移和数据流的协议类型、距离起始符的128bit偏移都相等时，根据该匹配字段的16bit偏移属性和掩码属性，输出当前数据流中该匹配字段对应的关键信息；否则，输出0；

步骤2b)范围关键信息拼接模块将所有范围匹配字段对应的关键信息按照用户定义的顺序首尾相接后输出；

步骤2c)其他关键信息拼接模块将所有最长前缀匹配字段的关键信息和精确匹配字段对应的关键信息按照用户定义的顺序首尾相接后输出；

步骤3)规则编码模块对用户定义的数据流分类规则进行编码：

步骤3a)规则预处理模块对数据流分类规则中包含的子规则进行分类：

步骤3a1)规则预处理模块将数据流分类规则按照规则的优先级从高到低的顺序进行排序，并逐条输出排序后的数据流分类规则的指令码；

步骤3a2)规则预处理模块将排序后的数据流分类规则中包含的子规则分为两类：一类为范围匹配字段对应的子规则，一类为最长前缀匹配字段对应的子规则和精确匹配字段对应的子规则；

步骤3b)第一规则编码器对数据流分类规则中的范围匹配字段对应的子规则进行范围比特向量编码并输出，其编码过程如图3所示：

步骤3b1)第一规则编码器将范围匹配字段对应的子规则[A_lower,A_upper]，分为第一级子范围[A1_lower,A1_upper]和第二级子范围[A2_lower,A2_upper]，其中，第一级子范围的范围下限A1_lower是A_lower的高8bit，范围上限A1_upper是A_upper的高8bit；第二级子范围的范围下限A2_lower是A_lower的低8bit，范围上限A2_upper是A_upper的低8bit；

步骤3b2)第一规则编码器对第一级子范围进行编码，第一级子范围[A1_lower,A1_upper]的编码结果可以写为二维数组B1[0:2][0:511]的形式，对于如果c＝A1_lower，那么B1[0:2][c]编码为‘001’；如果c＝A1_lower＝A1_upper，那么B1[0:2][c]编码为‘010’；如果c＝A1_upper，那么B1[0:2][c]编码为‘100’；如果A1_lower<c<A1_upper，那么B1[0:2][c]编码为‘111’；其他情况下，B1[0:2][c]编码为‘000’；

步骤3b3)第一规则编码器对第二级子范围进行编码，第二级子范围[A2_lower,A2_upper]的编码结果可以写为二维数组B2[0:1][0:511]的形式，对于如果A2_lower≤c≤A2_upper，那么B2[0:1][c]编码为‘11’；如果c≤A2_upper且c<A2_lower，那么B2[0:1][c]编码为‘10’；如果c≥A2_lower且c>A2_upper，那么B2[0:1][c]编码为‘01’；其他情况下，B2[0:1][c]编码为‘00’；

步骤3b4)第一规则编码器将编码结果输出；

步骤3c)第二规则编码器对数据流分类规则中的精确匹配字段对应的子规则和最长前缀匹配字段对应的子规则进行跨步比特向量编码并输出，其编码步骤如图4所示：

步骤3c1)第二规则编码器将最长前缀匹配字段对应的子规则和精确匹配字段对应的子规则进行分级，每级的子规则长度为4bit；

步骤3c2)第二规则编码器对4bit子规则进行编码，4bit子规则A的编码结果可写为B[0:15]，编码规则为：如果子规则A可以写成A1、A2、A3、A4等多种等价形式，编码时将B[A1]、B[A2]、B[A3]、B[A4]等设置为‘1’，B的其余位设置为‘0’，如规则‘110*’(*表示当前比特位和‘0’或‘1’都匹配)可以写为‘1100’和‘1101’，其编码结果为‘0000_0000_0000_1100’；

步骤3c3)第二规则编码器将编码结果输出；

步骤4)规则匹配模块对数据流分类规则编码结果进行存储和匹配：

步骤4a)第一流水线对第一规则编码器输出的编码结果进行存储，并将该规则的编码结果与数据流处理模块输出的范围关键信息进行匹配，需注意：子规则存储的顺序应和步骤2c中范围关键信息拼接的顺序相同，即如果3个字段分别为A、B、C，其对应的关键信息拼接顺序为BAC，那么字段对应的子规则的编码结果的存储顺序必须为BAC；

第一流水线对第一规则编码器输出的编码结果进行存储，并将该规则的编码结果与数据流处理模块输出的范围关键信息进行匹配，具体步骤如下：

步骤4a1)第一流水线将第一级子范围的编码结果和第二级子范围的编码结果分别存储在FPGA中不同的Block RAM中，对于N条规则，第一级子范围的编码结果存储在位宽为3N，深度为512的Block RAM：bram1[0:3N-1][0:511]中，规则K的第一级子范围的编码结果应存储在bram1[3K-3:3K-1][0]到bram1[3K-3:3K-1][511]中；第二级子范围的编码结果存储在位宽为2N，深度为512的Block RAM：bram2[0:2N-1][0:511]中，规则K的第二级子范围的编码结果应存储在bram2[2K-2:2K-1][0]到bram2[2K-2:2K-1][511]中；

步骤4a2)第一流水线将已存储的编码后的数据流分类规则与数据流处理模块输出的范围关键信息进行匹配，关键信息的前8bit作为bram1的读地址，读取结果为a[0:3N-1]，后8bit作为bram2的读地址，读取结果为b[0:2N-1]；

步骤4a3)第一流水线对Block RAM的读取结果进行分析：第K条规则对应的第一级的查找结果为a[3K-3:3K-1]，第二级的查找结果为b[2K-2:2K-1]，将两级查找结果分别简写为a[0:2]和b[0:1]，如果(a[0:2]＝＝3′b111)||(a[0]＝＝1′b1&&b[0]＝＝1′b1)||(a[1]＝＝1′b1&&b[0:1]＝＝2′b11)||(a[2])＝＝1′b1 && b[1]＝＝1′b1)＝＝1，则表示当前数据流中的范围关键信息与第K条规则匹配成功，记作res[k]＝1，否则，匹配失败，记作res[k]＝0，res即为数据流处理模块输出的范围关键信息和范围匹配字段对应的子规则的匹配结果；

第一流水线中的存储器为Block RAM，每个Block RAM在完成一次查找并将查找结果存储在当前模块后即可进行下一数据流的匹配，而不必等待其他Block RAM的查找结果，采用了流水线的思想，加快了查找速度。

步骤4b)第二流水线对第二规则编码器输出的编码结果进行存储，并将该规则的编码结果与数据流处理模块输出的其他关键信息进行匹配，需注意：子规则存储的顺序应和步骤2c中其他关键信息拼接的顺序相同，保证匹配结果的正确；

第二流水线对第二规则编码器输出的编码结果进行存储，并将该规则的编码结果与数据流处理模块输出的其他关键信息进行匹配，具体步骤如下：

步骤4b1)第二流水线将第二规则编码器输出的编码结果存储在FPGA中的寄存器中，对于N条规则，每级编码结果的存储空间为16个位宽为N的寄存器：ram[0:N-1][0:15]，规则K的编码结果BK[0:15]存储在ram[K][0]到ram[K][15]中；

步骤4b2)第二流水线将存储的规则与数据流处理模块输出的其他关键信息进行匹配，每4bit作为一级规则寄存器的读地址，读取结果为位宽N的比特向量，将每一级的读取的比特向量按位相与，得到数据流处理模块输出的其他关键信息和最长前缀匹配字段对应的子规则以及精确匹配字段的子规则的匹配结果；

第二流水线中的存储器为寄存器，每级寄存器在完成一次查找并将查找结果存储在当前模块后即可进行下一数据流的匹配，而不必等待其他寄存器的查找结果，采用了流水线的思想，加快了查找速度。

步骤4c)结果综合模块将第一流水线的匹配结果和第二流水线的匹配结果按位相与，得到数据流中的关键信息和数据流分类规则的匹配结果并输出，以N条规则为例，匹配结果为位宽N的比特向量，比特向量的高位至低位，依次表示优先级从高到低的规则的匹配结果，如果第m比特为1，则表示当前数据流和第m条规则匹配成功；

步骤5)优先级编码模块对规则匹配模块输出的匹配结果进行优先级分析：

优先级编码模块从高位向低位遍历规则匹配模块输出的匹配结果，确定其中第一个‘1’出现的位置，并将该位置的位置信息作为最优匹配结果并输出，优先级编码模块的输入为位宽N的比特向量，输出为位宽的位置信息，如优先级模块的输入为‘0110100’时输出为‘001’(位置信息从0开始)；

步骤6)指令码提取模块提取优先级编码模块输出的最优匹配结果对应的指令码：

步骤6a)指令码提取模块将规则编码模块输出的指令码存储在自身的指令码存储器中；

步骤6b)指令码提取模块将优先级编码模块输出的匹配结果作为指令码存储器的读地址，读取数据流对应的指令码信息，实现对数据流的分类。