一种海量流表中让新增流表规则快速生效的大小树算法的制作方法

本发明涉及规则树，具体为一种海量流表中让新增流表规则快速生效的大小树算法。

背景技术：

1、当前的网络设备用于网络访问控制的多元组规则流表功能，为了保证高性能数据包处理能力，主要采用字典树或其他树类算法实现的流表规则查找，树类算法在规则匹配时有着很高的查找速度。

2、树类算法在规则树的规则量较小时，重新编译建树时间短，能够在网络管理员无感知的情况下让规则生效，但是一棵规则树中的规则量超过几百万条或者几千万时，以当前cpu硬件主频速度，所需的建树时间，会让管理员能够明显感知到新增的规则迟迟无法生效，规则量越多时新增规则生效时间将会无限延长，所以面对海量流表时，通常会限制流表空间容量，逼迫网络管理员对相近网段的地址段进行合并，以压缩流表规则数量，用于减少规则生效时间。

3、但是通过限制流表空间容量，逼迫网络管理员对相近地址段进行合并，压缩流表规则数量的方法，治标不治本，不但会造成人员投入成本变高，同时在规则数量远远大于设备流表空间容量的场景中会变的无效。

技术实现思路

1、本发明的目的在于提供一种海量流表中让新增流表规则快速生效的大小树算法，解决以下技术问题：

2、如何保证在规则数量远远大于设备流表空间容量时，减少规则生效时间。

3、本发明的目的可以通过以下技术方案实现：

4、一种海量流表中让新增流表规则快速生效的大小树算法，所述算法包括：

5、s1：规则添加，根据大小规则树规则条目上限值确认重新建树时间是否超过规则生效最大容忍时间，并决定规则添加至哪一棵规则树中；

6、s2：规则合并，通过定时器循环检查小规则树当前规则条目数，当小规则树当前规则条目数超出规则合并下限值自动将小规则树中的规则条目合并至大规则树；

7、s3：规则匹配，根据输入的网络流量报文中的字段，通过树类查找算法在大小规则树中串行查找，让大小规则树中的规则都处于生效状态。

8、进一步的，所述s1中规则添加的过程包括：

9、s11：创建大树、小树两棵不同容量的规则树，其中小规则树的容量设置为规则满配时所需要建树时间小于或等于大树规则生效最大容忍时间，大规则树容量为对应硬件所能承载的最大容量；

10、s12：设置大规则树直接添加上限值，即超出上限值后建树时间将大于规则生效最大容忍时间；

11、s13：设置小规则树规则合并上限值和规则合并下限值，其中规则合并上限值表示超出后需要立即执行规则合并，规则合并下限值表示低于下限值将不执行规则合并；

12、s14：接收到新增的流表规则后，解析出规则树算法所需的五元字段，根据树类查找算法，在大、小规则树中查找新增的规则条目，若存在重复规则，返回添加规则重复，规则添加结束，否则，进行步骤s15；

13、s15：当不存在重复规则时，判断大规则树当前规则条目数是否超出直接添加上限值。

14、进一步的，所述s15中的判断过程包括：

15、通过公式计算获得当前所有规则条目的容量占用值δ；

16、其中，i为任意一条规则条目，n为当前大规则树中的总规则条目数量，dxi为第i条规则条目的数据包大小，dxb为dxi的标准值，jmi为第i条规则条目的加密等级，jmy为预设的加密等级，dsi为第i条规则条目的数据包丢失量影响系数，根据经验拟合设定，sl为当前大规则树中的节点数量，μ为规则复杂度影响系数，根据经验拟合设定。

17、进一步的，所述s15中的判断过程还包括：

18、通过将当前所有规则条目的容量占用值δ与预设的容量占用值δx进行比对，并将当前总规则条目数与直接添加上限值进行比对；

19、若当前总规则条目数大于直接添加上限值，将新增规则直接添加至小规则树配置中；

20、若当前总规则条目数小于直接添加上限值，且δ≥δx，判断当前所有规则条目的容量占用值高，将新增规则直接添加至小规则树配置中；

21、若当前总规则条目数小于直接添加上限值，且δ<δx，判断当前所有规则条目的容量占用值低，将新增规则加入大规则树配置中。

22、进一步的，所述s15中的判断过程还包括：

23、s151：当大规则树当前规则条目数未超出直接添加上限值，且当前所有规则条目的容量占用值小于预设的容量占用值时，将新增规则直接添加至大规则树配置中，更新大规则树计数器，并重新编译大规则树，使新增规则生效，规则添加完成；

24、s152：当大规则树当前规则条目数已超出直接添加上限值，或未超出直接添加上限值但是所有规则条目的容量占用值大于预设的容量占用值时，将新增规则加入小规则树配置中，更新小规则树计数器，并重新编译规则小树，使新增规则生效；

25、s153：判断小规则树规则条目数是否超出规则合并上限值，若超出规则合并上限值，触发规则合并流程，规则添加完成，若未超规则合并上限值，规则直接添加完成。

26、进一步的，所述s2中规则合并的过程包括：

27、s21：创建规则合并定时器，并对小规则树当前规则条目数是否超出规则合并下限值，若为否，进行循环判断，否则，进行步骤s22；

28、s22：将小树当前所有规则条目合并至大规则树规则配置中，形成新大规则树配置；

29、s23：根据新大规则树配置创建大规则树运行副本；

30、s24：大规则树运行副本编译完成后，将原有规则匹配流程中大规则树运行正本更换为大规则树运行副本，使大规则树运行副本变为运行正本，完成运行正副本替换；

31、s25：删除替换下的大规则树副本，释放内存空间，规则合并完成。

32、进一步的，所述s3中规则匹配的过程包括：

33、s31：对输入的网络流量报文进行解析，从流量报文中解析出规则树类查找算法所需的五元字段；

34、s32：通过流量报文中解析出的树类算法查找字段，并采用树类查找算法在大规则树中进行规则匹配，确定规则是否命中，若为是，进行步骤s33，否则，进行步骤s34；

35、s33，根据规则对应的行为字段进行流量报文处置；

36、s34：查找小树规则，通过流量报文中解析出的树类算法查找字段，并采用树类查找算法在小规则树中进行规则匹配，确定规则是否命中，若为是，进行步骤s35，否则，进行步骤s36；

37、s35：根据规则对应的行为字段进行流量报文处置；

38、s36：根据系统默认规则行为字段进行流量报文处置。

39、进一步的，所述树类算法查找字段包括源地址、目的地址、协议号、源端口号、目的端口号，且大小规则树的树类算法查找字段不同。

40、本发明的有益效果：

41、(1)本发明通过将原有单棵规则树拆分成一棵不关心建树编译时间但规则容量超大的大规则树和一棵专注建树编译时间但规则容量有限的小规则树，并通过动态调整规则添加的位置，以及调整网络流量报文规则匹配模式对两棵规则树进行串联匹配，确保两棵规则树中的规则能同时有效，从而保证在规则数量远远大于设备流表空间容量时，通过使用高性能树类查找算法，解决海量流表规则影响新增规则生效时间过长问题。

42、(2)本发明通过将原有单棵规则树拆分成一棵不关心建树编译时间但规则容量超大的大规则树和一棵专注建树编译时间但规则容量有限的小规则树，可以有效的降低了在高性能、海量流表规则场景中的网络设备投入成本，并且通过设置小规则树规则合并上限值和规则合并下限值，不仅可以避免存在建树时间大于规则生效最大容忍时间风险，并且可以减少大规则树频繁建树造成的资源占用，提高了工作效率。

43、(3)本发明通过将当前所有规则条目的容量占用值δ与预设的上限值δx进行比对，并将当前总规则条目数与直接添加上限值进行比对，通过结合两组不同类别的数据进行分析，可以对当前规则条目数是否超出直接添加上限值做出准确的判断，并根据判断结果决策将后续新增的规则条目加入到哪组规则树中，从而保证后续新增的规则条目生效时长不会受到较大的影响，实现在规则数量远远大于设备流表空间容量时，加快规则生效速度的效果。

44、(4)本发明通过结合两组不同类别的数据进行分析，可以对当前规则条目数是否超出直接添加上限值做出准确的判断，通过如此设置，当网络设备中的规则量建树编译时间存在超过规则生效最大容忍时间风险时，通过判断大规则树当前规则条目数是否超出直接添加上限值，可以判断当前大规则树的生效速度是否正常，并在判断当前大规则树的生效速度较慢时，在后续每次新增的规则都落入小规则树中，使得新增规则能够快速生效，解决在使用高性能树类查找算法时，海量流表规则影响新增规则生效时间过长问题。

45、(5)本发明通过在判断小规则树当前规则条目数超出规则合并下限值时，将小树当前所有规则条目合并至大规则树规则配置中，并将原有规则匹配流程中大规则树运行正本更换为大规则树运行副本，最后将替换下的大规则树副本进行删除，通过如此设置，可以保证小规则树不会出现规则溢出影响新增规则生效时间的问题，从而保证在规则数量远远大于设备流表空间容量时，仍能使规则生效的时间处于较快的状态。

技术特征：

1.一种海量流表中让新增流表规则快速生效的大小树算法，其特征在于，所述算法包括：

2.根据权利要求1所述的一种海量流表中让新增流表规则快速生效的大小树算法，其特征在于，所述s1中规则添加的过程包括：

3.根据权利要求2所述的一种海量流表中让新增流表规则快速生效的大小树算法，其特征在于，所述s15中的判断过程包括：

4.根据权利要求3所述的一种海量流表中让新增流表规则快速生效的大小树算法，其特征在于，所述s15中的判断过程还包括：

5.根据权利要求4所述的一种海量流表中让新增流表规则快速生效的大小树算法，其特征在于，所述s15中的判断过程还包括：

6.根据权利要求5所述的一种海量流表中让新增流表规则快速生效的大小树算法，其特征在于，所述s2中规则合并的过程包括：

7.根据权利要求6所述的一种海量流表中让新增流表规则快速生效的大小树算法，其特征在于，所述s3中规则匹配的过程包括：

8.根据权利要求7所述的一种海量流表中让新增流表规则快速生效的大小树算法，其特征在于，所述树类算法查找字段包括源地址、目的地址、协议号、源端口号、目的端口号，且大小规则树的树类算法查找字段不同。

技术总结
本发明涉及规则树技术领域，具体公开了一种海量流表中让新增流表规则快速生效的大小树算法，所述算法包括：S1：规则添加，根据大小规则树规则条目上限值确认重新建树时间是否超过规则生效最大容忍时间，并决定规则添加至哪一棵规则树中，通过将原有单棵规则树拆分成一棵不关心建树编译时间但规则容量超大的大规则树和一棵专注建树编译时间但规则容量有限的小规则树，并通过动态调整规则添加的位置，以及调整网络流量报文规则匹配模式对两棵规则树进行串联匹配，确保两棵规则树中的规则能同时有效，从而保证在规则数量远远大于设备流表空间容量时，通过使用高性能树类查找算法，解决海量流表规则影响新增规则生效时间过长问题。

技术研发人员：汤忠泽,庞文俊,李小超
受保护的技术使用者：清创网御（合肥）科技有限公司
技术研发日：
技术公布日：2024/12/5