一种提高大规格ACL匹配效率的方法和装置

摘要

本发明涉及多核软转发技术领域，提供了一种提高大规格ACL匹配效率的方法和装置。其中，根据匹配规则中设置的流表加速标志位信息，判断是否进行HASH流表加速处理；若不进行HASH流表加速处理，则按普通ACL流程进行处理；在进行HASH流表加速处理时，若所述匹配项的HASH KEY字段为预设值，则跳过相应的特征项的匹配；若所述匹配项记录有HASH KEY值，则对数据报中相应特征项进行HASH计算，并与相应HASH KEY值进行匹配。在本发明中保证了ACL规格，流量只需做一次HASH匹配就可以得到匹配结果，极大提升了ACL匹配效率，预处理机制和表项压缩机制保证了可接受的内存消耗。

权利要求

1.一种提高大规格ACL匹配效率的方法，其特征在于，包括：

根据匹配规则中设置的流表加速标志位信息，判断是否进行HASH流表加速处理；

若不进行HASH流表加速处理，则按普通ACL流程进行处理；

若进行HASH流表加速处理，检查加速匹配项标志位中包含的各个比特位，将加速匹配项标志位为0的，且对应于所述加速匹配项标志位的HASH KEY字段置为预设值；其中，每一个加速匹配项标志位对应于一个HASH KEY字段；

在进行HASH流表加速处理时，若所述匹配项的HASH KEY字段为预设值，则跳过相应的特征项的匹配，并分析下一个匹配项；若所述匹配项记录有HASH KEY值，则对数据报中相应特征项进行HASH计算，并与相应HASH KEY值进行匹配，以便完成相应数据包的ACL流程。

2.根据权利要求1所述的提高大规格ACL匹配效率的方法，其特征在于，检查加速匹配项标志位中包含的各个比特位，若加速匹配项标志位中对应端口号和/或VRF的比特位为1，则所述方法还包括：若所有匹配规则均包含相应比特位所对应的匹配项，且数据报文中相应匹配项信息与bitmap中记录的不匹配，则返回匹配未命中结果；

若部分匹配规则包含相应比特位所对应的匹配项，且数据报文中相应匹配项信息与bitmap中记录的不匹配，相应比特位所对应匹配项的HASH KEY字段置预设值；

若数据报文中相应比特位所对应的匹配项信息在bitmap中存在，则记录相应比特位所对应匹配项的HASH KEY值。

3.根据权利要求2所述的提高大规格ACL匹配效率的方法，其特征在于，在相应的匹配规则中包含有端口号和/或VRF匹配项时，在检查加速匹配项标志位中包含的各个比特位之前，所述方法还包括：根据匹配项中的端口号和/或VRF，将bitmap中的相应比特位置1；其中，bitmap中相应比特位在转换为十进制时，直接与所述端口号和/或VRF值相一致。

4.根据权利要求1所述的提高大规格ACL匹配效率的方法，其特征在于，检查加速匹配项标志位中包含的各个比特位，如果源目的IP地址的加速匹配项标志位的比特位为1，方法还包括：若所有匹配规则均包含该加速匹配项，且数据报文中源目的IP地址小于IP地址区间的极小值或大于IP地址区间的极大值，则返回未命中的匹配结果；

若部分匹配规则包含该加速匹配项，且数据报文中源目的IP地址小于IP地址区间的极小值或大于IP地址区间的极大值，则加速匹配项的HASH KEY值置预设值；

若数据报文中源目的IP地址在源目的IP地址的极大值和源目的IP地址的极小值之间，则加速匹配项的HASH KEY值按照记录的最大掩码位数，进行HASH KEY值结果中摘取与最大掩码位数对应的简化处理。

5.根据权利要求4所述的提高大规格ACL匹配效率的方法，其特征在于，在相应的匹配规则中包含有源目的IP地址匹配项时，所述方法还包括：根据ACL内各匹配规则中对应的源目的IP地址匹配项，得到对应各匹配规则的源目的IP地址的最小值和源目的IP地址的最大值；

并在所有匹配规则的源目的IP地址的最小值和源目的IP地址的最大值中取得源目的IP地址的极小值和源目的IP地址的极大值。

6.根据权利要求1所述的提高大规格ACL匹配效率的方法，其特征在于，所述流表加速标志位信息，按照如下方法进行设置：根据ACL内所有匹配规则的匹配项信息更新流表加速标志位，如果有一条匹配规则的匹配项含有加速匹配项以外的内容，则将流表加速标志位置为无效，等待下次ACL中有匹配规则更新、匹配规则添加、匹配规则删除时更新所述流表加速标志位。

7.根据权利要求1‑6任一所述的提高大规格ACL匹配效率的方法，其特征在于，所述方法还包括：根据所述HASH KEY值记录结果，对需要进行流表处理的报文进行HASH流表查找处理，根据HASH流表的查找结果选择生成HASH流表并记录匹配结果，更新流表的时间戳，以便防止相应流表被老化。

8.根据权利要求1所述的提高大规格ACL匹配效率的方法，其特征在于，所述进行HASH流表加速处理，具体包括：按照记录的HASH KEY值进行HASH流表查找，如果找到HASH KEY值则读取已经记录的ACL的匹配结果，并跳过普通ACL中提取报文信息并进行算法匹配的过程；

如果没有找到HASH KEY值，则进行HASH流表写表处理生成该报文对应的HASH流表，再进行普通ACL处理得到ACL匹配结果并记录在HASH流表中。

9.根据权利要求8所述的提高大规格ACL匹配效率的方法，其特征在于，方法还包括启动流表老化定时器，定时轮询HASH流表，具体的：读取已存在的HASH流表的时间戳，若时间戳与当前时间的差值超过设置的老化时间，则将该HASH流表老化删除，并清空对应的HASH流表匹配结果。

10.一种提高大规格ACL匹配效率的装置，其特征在于，所述装置包括：

至少一个处理器；以及，与所述至少一个处理器通信连接的存储器；其中，所述存储器存储有可被所述至少一个处理器执行的指令，所述指令被所述处理器执行，用于执行权利要求1‑9任一所述的提高大规格ACL匹配效率的方法。

说明书

一种提高大规格ACL匹配效率的方法和装置

【技术领域】

[0001] 本发明涉及多核软转发技术领域，特别是涉及一种提高大规格ACL匹配效率的方法和装置。【背景技术】

[0002] 随着物联网与5G网络的快速发展，支撑5G演进的ICT/NFV架构解决方案也显得尤为重要，而多核软转发由于通用硬件虚拟化的成本控制、内存规格、可拓展性、转发性能等综合性能优秀，作为ICT/NFV流量快速转发的基石在其中也扮演着重要的角色。

[0003] 多核软转发的ACL功能依赖纯软件实现，主要涉及以下三种软件算法：DPDK ACL字典树算法匹配效率较低，对设备转发性能影响较大，无法满足设备高吞吐量性能需求；RFC算法匹配效率较高但大页内存消耗巨大，无法满足设备ACL大规格表项需求；OpenFlow流表只适用于SDN场景，由SDN控制器下发流表规则，且需要根据优先级从高到低多次匹配，效率不高。【发明内容】

[0004] 本发明要解决的技术问题是ACL以及QoS流策略在实际业务中有着广泛的应用，目前多核软转发ACL以及QoS流策略软件算法由于效率问题无法满足大业务流量的报文匹配需求。

[0005] 本发明采用如下技术方案：

[0006] 第一方面，本发明提供了一种提高大规格ACL匹配效率的方法，包括：

[0007] 根据匹配规则中设置的流表加速标志位信息，判断是否进行HASH流表加速处理；

[0008] 若不进行HASH流表加速处理，则按普通ACL流程进行处理；

[0009] 若进行HASH流表加速处理，检查加速匹配项标志位中包含的各个比特位，将加速匹配项标志位为0的，且对应于所述加速匹配项标志位的HASH KEY字段置为预设值；其中，每一个加速匹配项标志位对应于一个HASH KEY字段；

[0010] 在进行HASH流表加速处理时，若所述匹配项的HASH KEY字段为预设值，则跳过相应的特征项的匹配；若所述匹配项记录有HASH KEY值，则对数据报中相应特征项进行HASH计算，并与相应HASH KEY值进行匹配，以便完成相应数据包的ACL流程。

[0011] 优选的，检查加速匹配项标志位中包含的各个比特位，若加速匹配项标志位中对应端口号和/或VRF的比特位为1，则所述方法还包括：

[0012] 若所有匹配规则均包含相应比特位所对应的匹配项，且数据报文中相应匹配项信息与bitmap中记录的不匹配，则返回匹配未命中结果；

[0013] 若部分匹配规则包含相应比特位所对应的匹配项，且数据报文中相应匹配项信息与bitmap中记录的不匹配，相应比特位所对应匹配项的HASH KEY字段置预设值；

[0014] 若数据报文中相应比特位所对应的匹配项信息在bitmap中存在，则记录相应比特位所对应匹配项的HASH KEY值。

[0015] 优选的，在相应的匹配规则中包含有端口号和/或VRF匹配项时，在检查加速匹配项标志位中包含的各个比特位之前，所述方法还包括：

[0016] 根据匹配项中的端口号和/或VRF，将bitmap中的相应比特位置1；其中，bitmap中相应比特位在转换为十进制时，直接与所述端口号和/或VRF值相一致。

[0017] 优选的，检查加速匹配项标志位中包含的各个比特位，如果源目的IP地址的加速匹配项标志位的比特位为1，方法还包括：

[0018] 若所有匹配规则均包含该加速匹配项，且数据报文中源目的IP地址小于IP地址区间的极小值或大于IP地址区间的极大值，则返回未命中的匹配结果；

[0019] 若部分匹配规则包含该加速匹配项，且数据报文中源目的IP地址小于IP地址区间的极小值或大于IP地址区间的极大值，则加速匹配项的HASH KEY值置预设值；

[0020] 若数据报文中源目的IP地址在源目的IP地址的极大值和源目的IP地址的极小值之间，则加速匹配项的HASH KEY值按照记录的最大掩码位数，进行HASH KEY值结果中摘取与最大掩码位数对应的简化处理。

[0021] 优选的，在相应的匹配规则中包含有源目的IP地址匹配项时，所述方法还包括：

[0022] 根据ACL内各匹配规则中对应的源目的IP地址匹配项，得到对应各匹配规则的源目的IP地址的最小值和源目的IP地址的最大值；

[0023] 并在所有匹配规则的源目的IP地址的最小值和源目的IP地址的最大值中取得源目的IP地址的极小值和源目的IP地址的极大值。

[0024] 优选的，所述流表加速标志位信息，按照如下方法进行设置：

[0025] 根据ACL内所有匹配规则的匹配项信息更新流表加速标志位，如果有一条匹配规则的匹配项含有加速匹配项以外的内容，则将流表加速标志位置为无效，等待下次ACL中有匹配规则更新、匹配规则添加、匹配规则删除时更新所述流表加速标志位。

[0026] 优选的，所述方法还包括：

[0027] 根据所述HASH KEY值记录结果，对需要进行流表处理的报文进行HASH流表查找处理，根据HASH流表的查找结果选择生成HASH流表并记录匹配结果，更新流表的时间戳，以便防止相应流表被老化。

[0028] 优选的，所述进行HASH流表加速处理，具体包括：

[0029] 按照记录的HASH KEY值进行HASH流表查找，如果找到HASH KEY值则读取已经记录的ACL的匹配结果，并跳过普通ACL中提取报文信息并进行算法匹配的过程；

[0030] 如果没有找到HASH KEY值，则进行HASH流表写表处理生成该报文对应的HASH流表，再进行普通ACL处理得到ACL匹配结果并记录在HASH流表中。

[0031] 优选的，方法还包括启动流表老化定时器，定时轮询HASH流表，具体的：

[0032] 读取已存在的HASH流表的时间戳，若时间戳与当前时间的差值超过设置的老化时间，则将该HASH流表老化删除，并清空对应的HASH流表匹配结果。

[0033] 第二方面，本发明还提供了一种提高大规格ACL匹配效率的装置，用于实现第一方面所述的提高大规格ACL匹配效率的方法，所述装置包括：

[0034] 至少一个处理器；以及，与所述至少一个处理器通信连接的存储器；其中，所述存储器存储有可被所述至少一个处理器执行的指令，所述指令被所述处理器执行，用于执行第一方面所述的提高大规格ACL匹配效率的方法。

[0035] 第三方面，本发明还提供了一种非易失性计算机存储介质，所述计算机存储介质存储有计算机可执行指令，该计算机可执行指令被一个或多个处理器执行，用于完成第一方面所述的提高大规格ACL匹配效率的方法。

[0036] 在本发明中提出了一种提高大规格ACL匹配效率的方法，保证了ACL规格，流量只需做一次HASH匹配就可以得到匹配结果，极大提升了ACL匹配效率，预处理机制和表项压缩机制保证了可接受的内存消耗。【附图说明】

[0037] 为了更清楚地说明本发明实施例的技术方案，下面将对本发明实施例中所需要使用的附图作简单地介绍。显而易见地，下面所描述的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

[0038] 图1是本发明实施例提供的一种提高大规格ACL匹配效率的方法流程示意图；

[0039] 图2是本发明实施例提供的一种提高大规格ACL匹配效率的方法流程示意图；

[0040] 图3是本发明实施例提供的一种提高大规格ACL匹配效率的方法流程示意图；

[0041] 图4是本发明实施例提供的一种提高大规格ACL匹配效率的方法流程示意图；

[0042] 图5是本发明实施例提供的一种提高大规格ACL匹配效率的方法流程示意图；

[0043] 图6是本发明实施例提供的一种提高大规格ACL匹配效率的装置结构示意图。【具体实施方式】

[0044] 为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。

[0045] 本发明整个方案具体可以涉及ACL配置预处理流程、转发预处理流程、转发流表处理流程、流表老化维护等内容，在进行具体实施方式描述之前，先逐一的对上述内容进行阐述。

[0046] 1、ACL配置预处理流程

[0047] 在ACL配置下发、删除、更新时，设置用于预处理的流表加速标志位、加速匹配项标志位、合并项、比特位，以及更新流表匹配结果，各预处理项的具体作用如下：

[0048] 流表加速标志位：HASH流表按照ACL常用加速匹配项，一般可针对源目的IP地址、源目的L4端口号、虚拟路由转发(Virtual Routing Forwarding，简写为：VRF)VRF等内容进行加速处理(即对内容计算得到HASH KEY值)，也可按照使用场景定制加速匹配项，针对不常用的匹配项，ACL资源使用比较少，可不对其进行加速处理，流表加速标志位表示该条ACL内的所有规则中是否含有不在加速匹配项中的内容，如果含有该内容，则该条ACL不做HASH流表加速处理。

[0049] 加速匹配项标志位：针对加速匹配项(上述HASH KEY值)，表示该条ACL内是否含有该加速匹配项，若不含有该加速匹配项，在生成流表时可将该HASH KEY值置为0，这样其他HASH KEY值相同而该加速匹配项不同的报文可应用于同一条HASH流表，起到流表表项压缩的目的。例如，ACL的匹配规则为匹配四层端口号时，此时IP对于匹配结果不起任何作用，这样IP地址为1.1.1.1，源目的L4端口号为1024的报文和IP地址为2.1.1.1，源目的L4端口号为1024的报文匹配结果是一致的，所以可以将IP字段的HASH KEY值置0处理，表示该ACL内的规则不匹配IP字段。

[0050] 合并项：可用于源目的IP地址等加速匹配项的预处理与流表压缩，记录匹配项中的最小地址、最大地址以及匹配项最大掩码，报文源目的IP地址小于最小地址或大于最大地址表示该IP地址无法命中(该ACL内全部规则均匹配源目的IP地址)或不需匹配(该ACL内部分规则匹配源目的IP地址)，处于最大最小地址之间的使用最大掩码对地址进行位与处理，可用于流程加速或表项压缩。例如：ACL内有两条规则，分别匹配IP网段1.1.1.0/255和2.1.1.0/255，那么处于极小值1.1.1.0以前的IP网段以及极大值2.1.1.255以后的IP网段不会在ACL匹配规则内命中，此时便可通过判断报文IP与极小极大值的关系来跳过ACL匹配流程，减少不必要的匹配过程，提高ACL的匹配效率。1.1.1.0/24表示24位掩码，即ip 
1.1.1.0mask 255.255.255.0的简写形式，表示1.1.1.1～1.1.1.255内的所有IP，那么这个IP网段的极小值就是1.1.1.0，极大值是1.1.1.255。

[0051] 比特位：专门用于源目的L4端口号以及VRF等加速匹配项的预处理与流表压缩，记录匹配项中的L4端口号与VRF，将bitmap中的相应比特位置1，报文L4端口号或VRF不在相应的bitmap中时表示该匹配项无法命中(该ACL内全部规则均匹配源目的L4端口号或VRF)或不需匹配(该ACL内部分规则匹配L4端口号或VRF)，可用于流程加速或表项压缩。例如：ACL内两条规则分别为匹配L4端口号为1024和2048的报文，在匹配端口号的bitmap内将1024与2048的位置置为1，bitmap内为0位置的端口号肯定是不会在ACL匹配规则内命中，此时将报文携带的端口号与bitmap进行比对就可以跳过ACL匹配流程，减少不必要的匹配过程，提高ACL的匹配效率。

[0052] 更新流表结果：ACL规则下发、删除、更新时，流表的匹配结果需要同步进行更新，在此处需要将该ACL对应的流表匹配结果清空，待转发流表处理流程更新其匹配结果。若以上标志位发生变化，在转发过程中会生成新的流表，而旧的流表会因为超时而老化掉，相应的匹配结果会在流表中进行更新。

[0053] 2、转发预处理流程

[0054] 根据配置预处理流程中设置的信息，判断是否进行HASH流表加速处理，若进行处理，则根据加速匹配项标志位的内容对相应的HASH KEY值进行记录或置0处理，如果ACL匹配规则中不包含HASH KEY值内的某个成员(IP地址、源目的L4端口等)，即加速匹配项标志位为0，则可以相应的将该成员的HASH KEY值置为0，表示该成员不会影响ACL匹配结果，所以将该成员HASH KEY值全部聚合为0。再检查比特位以及合并项内容，对于IP地址极小极大值或bitmap中未置位为1的报文，肯定是不会命中ACL规则的，所以会做出提前结束ACL流程的动作。对于混合配置情况下(部分规则匹配IP，部分规则匹配L4端口号等)，会将上述不会命中ACL规则的报文相应的成员HASH KEY值置0，代表该成员对匹配结果不会造成影响，因为该报文的其他成员可能命中ACL规则，所以不会直接结束流程。对于在IP极大极小地址之间的报文，会按照设置的合并项规则对报文该成员的HASH KEY值进行按位与操作，比如匹配规则为1.1.1.0/24，IP地址为1.1.1.1的报文和IP地址为1.1.1.255的报文的HASH KEY值均可以合并为1.1.1.0。例如，HASH的使用过程如下：HASH KEY1+KEY2+KEY3+…+KEYn→HASH INDEX→索引得到HASH DATA，所以对HASH KEY值做合并操作是很有必要的，例如此处针对IP的HASH_KEY_IP不做合并，就会产生1.1.1.1～1.1.1.255这255个HASH KEY即255个HASH INDEX即255个HASH DATA，而如果将1.1.1.1～1.1.1.255合并为1.1.1.0即可以使用一个HASH_KEY_IP就可以索引得到同样的结果，合并操作本身就是一个计算的过程。

[0055] 3、转发流表处理流程

[0056] 流表处理流程用于查找ACL匹配结果，根据上述流程中HASH KEY值记录结果，对需要进行流表处理的报文进行HASH流表查找处理，根据HASH流表的查找结果选择生成HASH流表并记录匹配结果(没有查找到流表需要新建流表并保存)或直接读取匹配结果(查找到流表直接读取结果)，更新流表的时间戳，以便防止相应流表被老化。

[0057] 在流表新建的过程中，如果发现流表表项已满，则后续报文无法得到加速处理，直到有部分流表表项因超时老化节省出部分流表空间。但有可能在老化周期内，部分流表只产生少量命中从而占有流表空间，而部分报文会产生大量命中，却因为流表空间不足而无法得到加速处理的情况下，此处提出一种动态处理流表表项以及预处理标志位的方法，具体操作以及原理如下。

[0058] 在本流程中，如果发现流表表项已满，会将流表溢出标志位置位为1，待流表老化维护单元使用。并且，在流表更新时间戳的同时，需要对该条流表的命中次数进行计数，每命中一次(包含首次生成该流表)，计数进行加一处理。

[0059] 4、流表老化维护

[0060] 流表老化维护使用定时器实现，定时对流表进行维护。

[0061] 一是对于超时未更新时间戳的流表进行老化处理并清空其匹配结果，节约流表空间。

[0062] 二是检查上节中设置的流表溢出标志位，如果标志位为1，则需要将表项中命中次数小于设置阈值的表项进行老化处理并清空其匹配结果，节约流表空间，并且针对该条流表对应的预处理标志位(源目的L4端口号对应bitmap或IP对应合并项)采取惩罚措施，在接下来一定的老化周期内，该预处理标志位对应的报文不参与加速处理，不生成流表表项。具体方法为使用惩罚标志位(表示是否有流表被惩罚)、惩罚bitmap和惩罚IP(设立一定的倒计次数)，举例说明，例如该小于阈值的流表匹配源目的L4端口号为1000，则将其加入惩罚bitmap中，则在下次转发预处理流程中发现源目的L4端口号的HASH KEY值在惩罚bitmap中，则不参与加速处理，避免因小于阈值而老化的流表因再次命中而反复增删。

[0063] 在本流程中，每次老化周期内会对惩罚bitmap以及惩罚IP进行计数减一，直到计数清零，此时会将其删除，表示该流表可以正常参与流表的生成与刷新。

[0064] 每次老化周期结束以后，因为会有流表老化，所以需将流表溢出标志位清0，待转发处理流程再次出发置位。

[0065] 此外，下面所描述的本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可以相互组合。

[0066] 实施例1:

[0067] 本发明实施例1提供了一种提高大规格ACL匹配效率的方法，如图1所示包括：

[0068] 在步骤201中，根据匹配规则中设置的流表加速标志位信息，判断是否进行HASH流表加速处理。

[0069] 其中，设置的流表加速标志位信息的方法可以是，根据ACL内所有匹配规则的匹配项信息更新流表加速标志位，如果有一条匹配规则的匹配项含有加速匹配项以外的内容，则将流表加速标志位置为无效，等待下次ACL中有匹配规则更新、匹配规则添加、匹配规则删除时更新所述流表加速标志位。

[0070] 在步骤202中，若不进行HASH流表加速处理，则按普通ACL流程进行处理。

[0071] 在步骤203中，若进行HASH流表加速处理，检查加速匹配项标志位中包含的各个比特位，将加速匹配项标志位为0的，且对应于所述加速匹配项标志位的HASH KEY字段置为预设值；其中，每一个加速匹配项标志位对应于一个HASH KEY字段。

[0072] 其中，预设值可以是指定的一条字符串，或者单一某个字符。

[0073] 在步骤204中，在进行HASH流表加速处理时，若所述匹配项的HASH KEY字段为预设值，则跳过相应的特征项的匹配；若所述匹配项记录有HASH KEY值，则对数据报中相应特征项进行HASH计算，并与相应HASH KEY值进行匹配，以便完成相应数据包的ACL流程。

[0074] 在本发明各实施例中，HASH KEY值为计算出的参数值，其表示明确的实际参数含义，与HASH KEY字段中的预设值形成对比，可以理解为是非预设值的一种明确表示。

[0075] 在本发明实施例中，提出了一种提高大规格ACL匹配效率的方法，保证了ACL规格，流量只需做一次HASH匹配就可以得到匹配结果，极大提升了ACL匹配效率，预处理机制和表项压缩机制保证了可接受的内存消耗。

[0076] 结合本发明实施例，检查加速匹配项标志位中包含的各个比特位，若加速匹配项标志位中对应端口号和/或VRF的比特位为1，则所述方法还包括：

[0077] 若所有匹配规则均包含相应比特位所对应的匹配项，且数据报文中相应匹配项信息与bitmap中记录的不匹配，则返回匹配未命中结果；

[0078] 若部分匹配规则包含相应比特位所对应的匹配项，且数据报文中相应匹配项信息与bitmap中记录的不匹配，相应比特位所对应匹配项的HASH KEY字段置预设值；

[0079] 若数据报文中相应比特位所对应的匹配项信息在bitmap中存在，则记录相应比特位所对应匹配项的HASH KEY值。

[0080] 因此，在相应的匹配规则中包含端口号和/或VRF匹配项时，在检查加速匹配项标志位中包含的各个比特位之前，所述方法还包括：根据匹配项中的端口号和/或VRF，将bitmap中的相应比特位置1；其中，bitmap中相应比特位在转换为十进制时，直接与所述端口号和/或VRF值相一致。

[0081] 结合本发明实施例，检查加速匹配项标志位中包含的各个比特位，如果源目的IP地址的加速匹配项标志位的比特位为1，方法还包括：

[0082] 若所有匹配规则均包含该加速匹配项，且数据报文中源目的IP地址小于IP地址区间的极小值或大于IP地址区间的极大值，则返回未命中的匹配结果；

[0083] 若部分匹配规则包含该加速匹配项，且数据报文中源目的IP地址小于IP地址区间的极小值或大于IP地址区间的极大值，则加速匹配项的HASH KEY值置预设值；

[0084] 若数据报文中源目的IP地址在源目的IP地址的极大值和源目的IP地址的极小值之间，则加速匹配项的HASH KEY值按照记录的最大掩码位数，进行HASH KEY值结果中摘取与最大掩码位数对应的简化处理。用掩码合并可以压缩HASH KEY的表项，例如匹配1.1.1.0/24网段的IP，最大掩码位数为24，这样整个网段都可以使用1.1.1.0的HASH KEY值进行匹配，而不需要使用1.1.1.1～1.1.1.255这样255个具体IP的HASH KEY进行匹配。

[0085] 在相应的匹配规则中包含有源目的IP地址匹配项时，对于如何得到上述的源目的IP地址的极大值和源目的IP地址的极小值，所述方法还包括：

[0086] 根据ACL内各匹配规则中对应的源目的IP地址匹配项，得到对应各匹配规则的源目的IP地址的最小值和源目的IP地址的最大值；

[0087] 并在所有匹配规则的源目的IP地址的最小值和源目的IP地址的最大值中取得源目的IP地址的极小值和源目的IP地址的极大值。

[0088] 结合本发明实施例，所述方法还包括：

[0089] 根据所述HASH KEY值记录结果，对需要进行流表处理的报文进行HASH流表查找处理，根据HASH流表的查找结果选择生成HASH流表并记录匹配结果(没有查找到流表需要新建流表并保存)或直接读取匹配结果(查找到流表直接读取结果)，更新流表的时间戳，以便防止相应流表被老化。

[0090] 在本发明实施例中，所述进行HASH流表加速处理，具体包括：

[0091] 按照记录的HASH KEY值进行HASH流表查找，如果找到HASH KEY值则读取已经记录的ACL的匹配结果，并跳过普通ACL中提取报文信息并进行算法匹配的过程；

[0092] 如果没有找到HASH KEY值(在本发明实施例中也被表述为HASH KEY值为预设值，例如为0或者1等简单的表征参数)，则进行HASH流表写表处理生成该报文对应的HASH流表，再进行普通ACL处理得到ACL匹配结果并记录在HASH流表中。

[0093] 结合本发明实施例，还存在一种优选的实现方案，启动流表老化定时器，定时轮询HASH流表，方法具体包括：

[0094] 读取已存在的HASH流表的时间戳，若时间戳与当前时间的差值超过设置的老化时间，则将该HASH流表老化删除，并清空对应的HASH流表匹配结果。

[0095] 采用HASH流表、报文匹配预处理的方式提高ACL匹配处理速度，通过合并项、bitmap、加速项标志位、老化机制压缩表项使更多的报文得到加速。

[0096] 经过设备实际测试，路由转发+ACL动作PASS+64字节包长条件下，采用HASH流表与采用DPDK ACL算法相比整体吞吐量提升了21.19％，采用bitmap预处理后，整体吞吐量继续提升6％左右。

[0097] 与现有ACL流表相比，有如下优点：

[0098] 1、流表由设备根据报文特征自动生成，无需控制器下发；

[0099] 2、使用了预处理流程，将明显不会命中的报文提前筛选出来，缩短处理流程，减少表项空间的占用；

[0100] 3、使用了合并项策略，将IP字段多个合并范围段内的HASH KEY值合并为一个相同的HASH KEY，大量减少表项空间的占用；

[0101] 4、使用原有ACL算法得到创建对应流表时的ACL结果，后续报文命中流表后可直接得到命中结果，而非现有ACL流表的优先级高到低的多级查找流程，相比效率更高。

[0102] 本文提出一种流表加速、表项压缩以及表项动态调整的方案提升ACL以及QoS流策略报文匹配效率并压缩流表表项减少流表的内存使用，使多核软转发设备在测试和现网中得到更高性能。

[0103] 同样的，基于流表加速的方案不只能应用于ACL领域，在其他需要提升效率的产品/模块/方案均可以参考借鉴其做法，并且各模块间可以共用一套流表，进一步提升效率。

[0104] 接下来，本发明将通过实施例2‑实施例5针对ACL配置预处理流程、转发预处理流程、转发流表处理流程和流表老化维护，配合相应的流程图和场景做详尽的阐述，需要指出的是，所述实施例2‑实施例5的内容源是从本发明实施例1方案中提炼而出，并结合实际情况进行了更为丰富的组合实现，因此，其同样可以作为修改本发明实施例的依据，但不应该作为限定本发明实施例其他可能组合实现方式的限缩依据。

[0105] 实施例2：

[0106] 如图2所示，为ACL配置预处理流程，包括：

[0107] 在步骤301中，根据ACL内所有规则的匹配项信息更新流表加速标志位，如果有一条规则的匹配项含有加速匹配项以外的内容，则将流表加速标志位置为0并不再改变，待下次ACL更新、添加、删除时更新该标志位。

[0108] 在步骤302中，根据ACL内所有规则的匹配项信息更新加速匹配项标志位，例如ACL规则匹配源IP地址则将其比特位置1，表示规则中需要匹配源IP地址信息。

[0109] 在步骤303中，根据ACL内所有源目的IP地址匹配项记录合并项信息，根据ACL规则源目的IP地址和ACL匹配掩码得到该匹配项的最小值和最大值，并在所有规则的最小值和最大值中取得极小值和极大值并记录，可以过滤掉明显无法命中的在极小值与极大值外的报文。

[0110] 用掩码合并可以压缩HASH KEY的表项，例如匹配1.1.1.0/24网段的IP，最大掩码位数为24，这样整个网段都可以使用1.1.1.0的HASH KEY值进行匹配，而不需要使用1.1.1.1～1.1.1.255这样255个具体IP的HASH KEY进行匹配。

[0111] 在步骤304中，根据ACL内所有源目的L4端口号、VRF匹配项记录比特位信息，根据ACL规则源目的L4端口号、VRF将bitmap内相应的比特位置1，并且记录ACL规则是全部规则包含该匹配项或部分规则包含该匹配项。

[0112] 在步骤305中，清空该ACL对应的流表匹配结果。

[0113] 实施例3：

[0114] 如图3所示，转发预处理流程包括：

[0115] 在步骤401中，检查惩罚标志位，分为两种情况：

[0116] i.如果惩罚标志位为0，表示没有流表被惩罚，流程正常进行；

[0117] ii.如果惩罚标志位为1，表示有部分报文被惩罚无法生成流表。此时在进行惩罚bitmap和惩罚IP的检查，以此比对HASH KEY值和惩罚值，如果HASH KEY值在惩罚范围内，则跳过加速处理流程，使用普通ACL进行报文匹配。

[0118] 在步骤402中，根据301中设置的流表加速标志位信息，判断是否进行HASH流表加速处理，若不进行HASH流表加速处理，则按普通ACL流程进行处理。

[0119] 在步骤403中，对于加速处理的报文，检查步骤302中设置的加速匹配项标志位，将标志位为0即不含有该加速匹配项的报文匹配HASH KEY值置0，此处的标志位是实时生效的，若后续ACL更新后该标志位更新为1，则会根据新的标志位记录新的HASH KEY值产生一条新的流表，而旧流表如果超时未命中则会被老化。

[0120] 在步骤404中，检查合并项，如果402中源目的IP地址的加速匹配项标志位不为0，则进行合并项检查，分为三种情况：

[0121] i.所有规则均包含该匹配项且报文该匹配项信息(即源目的IP地址等)小于步骤303中极小值或大于极大值，提前结束ACL流程，返回未命中结果；

[0122] ii.部分规则包含该匹配项且报文该匹配项信息小于303中极小值或大于极大值，该匹配项HASH KEY值置0；

[0123] iii.报文该匹配项信息在极大极小值之间，HASH KEY值按照303中记录的最大掩码位数，进行HASH KEY值结果中摘取与最大掩码位数对应的简化处理；

[0124] 在步骤405中，检查比特位，如果402中源目的L4端口号和VRF的加速匹配项标志位不为0，则进行比特位检查，分为三种情况：

[0125] i.所有规则均包含该匹配项且报文该匹配项信息(即源目的L4端口号、VRF等)不在bitmap中，提前结束ACL流程，返回未命中结果；

[0126] ii.部分规则包含该匹配项且报文该匹配项信息不在bitmap中，该匹配项HASH KEY值置0；

[0127] iii.报文该匹配项信息在bitmap中，记录匹配项HASH KEY值，继续流程。

[0128] 实施例3：

[0129] 如图4所示，为本发明实施例所提供的转发流表处理流程，具体包括：

[0130] 在步骤501中，按照实施例3中记录的HASH KEY值进行HASH流表查找，如果找到则继续读取在步骤502中已经记录的该ACL的匹配结果，并跳过普通ACL算法中提取报文信息并进行算法匹配的过程；

[0131] 在步骤502中，如果没有找到，则进行HASH流表写表处理生成该报文对应的HASH流表，再进行普通ACL处理得到ACL匹配结果并记录在HASH流表中。例如报文IP为1.1.1.1，合并项位宽为24，则需查找HASH KEY值为1.1.1.0的HASH流表，发现没有命中流表，则需要新生成一条该HASH KEY值的流表，而HASH流表对应的匹配结果暂时是没有的，此时会将该报文信息送到普通ACL算法中得到匹配结果，而该匹配结果会记录在该条新生成的HASH流表中供501节中后续命中该流表的报文使用。

[0132] 如果502节中HASH流表因为表满而生成失败，则将流表溢出标志位置位为1，并且进行普通ACL处理得到匹配结果而不进行HASH流表结果的记录。

[0133] 在步骤503中，如果501和502均成功执行，则更新该HASH流表的时间戳，并将该HASH流表的命中计数加一。

[0134] 实施例4：

[0135] 如图5所示，为本发明实施例所提供的流表老化维护过程，具体包括：

[0136] 在步骤601中，启动流表老化定时器，定时轮询HASH流表。

[0137] 在步骤602中，读取已存在的HASH流表的时间戳，若时间戳与当前时间的差值超过设置的老化时间，则需要将该HASH流表老化删除，并清空对应的HASH流表匹配结果。

[0138] 在步骤603中，读取流表溢出标志位：

[0139] i.如果该标志位为0，则不进行任何处理。

[0140] ii.如果该标志位为1，则进行流表命中计数(其相应的操作在实施例4中涉及)检查，若该流表命中计数小于设置阈值，则将该HASH流表老化删除，并清空对应的HASH流表匹配结果，并记录该流表非零的源目的L4端口以及IP的HASH KEY值，作为惩罚bitmap置位与惩罚IP，并将其倒计次数置为设定值。

[0141] 在步骤604中，读取非零惩罚bitmap以及惩罚IP的倒计次数，并对其进行计数减一处理，若计数清零，则同时将惩罚效果清零。

[0142] 在步骤605中，将流表溢出标志位置位为0。

[0143] 实施例5：

[0144] 如图6所示，是本发明实施例的提高大规格ACL匹配效率的装置的架构示意图。本实施例的提高大规格ACL匹配效率的装置包括一个或多个处理器21以及存储器22。其中，图6中以一个处理器21为例。

[0145] 处理器21和存储器22可以通过总线或者其他方式连接，图6中以通过总线连接为例。

[0146] 存储器22作为一种非易失性计算机可读存储介质，可用于存储非易失性软件程序和非易失性计算机可执行程序，如实施例1中的提高大规格ACL匹配效率的方法。处理器21通过运行存储在存储器22中的非易失性软件程序和指令，从而执行提高大规格ACL匹配效率的方法。

[0147] 存储器22可以包括高速随机存取存储器，还可以包括非易失性存储器，例如至少一个磁盘存储器件、闪存器件、或其他非易失性固态存储器件。在一些实施例中，存储器22可选包括相对于处理器21远程设置的存储器，这些远程存储器可以通过网络连接至处理器21。上述网络的实例包括但不限于互联网、企业内部网、局域网、移动通信网及其组合。

[0148] 所述程序指令/模块存储在所述存储器22中，当被所述一个或者多个处理器21执行时，执行上述实施例1中的提高大规格ACL匹配效率的方法，例如，执行以上描述的图1‑图5所示的各个步骤。

[0149] 值得说明的是，上述装置和系统内的模块、单元之间的信息交互、执行过程等内容，由于与本发明的处理方法实施例基于同一构思，具体内容可参见本发明方法实施例中的叙述，此处不再赘述。

[0150] 本领域普通技术人员可以理解实施例的各种方法中的全部或部分步骤是可以通过程序来指令相关的硬件来完成，该程序可以存储于一计算机可读存储介质中，存储介质可以包括：只读存储器(ROM，Read Only Memory)、随机存取存储器(RAM，Random Access Memory)、磁盘或光盘等。

[0151] 以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。