1.本发明涉及数据中心网络和流表查找加速技术领域，特别涉及一种软件数据包分类加速方法、装置、设备及存储介质。
背景技术：2.sdn的流行催生了很多部署在软件交换机上的网络应用在，比如负载均衡器、流调度器、软件网关等。这些应用程序需要在处理核心应用程序逻辑之前使用数据包分类算法对数据包进行分类。
3.但是，企业网络中需要服务的并发流数量很大(o(10m))。更多需要被服务的流通常意味着更大的流表，更大的流表导致更长的数据包分类时间。
4.在这种场景下，为企业网络中的大流表设计一种快速的数据包分类算法非常重要。以前的工作通常忽略规则集和流量的统计特性，直接优化流表的数据结构，或者利用规则集的统计特性来优化数据结构。但是，以前的工作忽略了流量模式，尤其是流量的偏斜性。
5.根据我们对真实流量和规则集的分析，流量的偏斜性导致规则命中的偏斜性，命中次数最多的规则的命中数占大部分的总命中数。因此，为了加快数据包分类的过程，我们应该重点加速命中频率高的规则查找速度。
6.但是在软件上通过加速命中频率高的规则的查找速度来优化整个数据包分类加速算法的查找速度很有挑战性。第一，如何在软件上优化命中数大的规则的查表时延。第二，如何确定优化规则的比例，如果优化的比例过大，会使得命中数大的规则的查表时延较大，影响整体的优化效率；如果优化的比例过小，则可能会导致查表时延下降不明显。因此，如何确定优化规则的比例也很重要。
技术实现要素：[0007][0008]
本发明旨在至少在一定程度上解决相关技术中的技术问题之一。
[0009]
为此，本发明的目的在于提出一种软件数据包分类加速方法、装置、设备及存储介质，本发明为了加速命中频繁规则的查表速度，从而加速数据包分类过程，本发明将流表划分为两级，命中频繁的规则被放到一级流表中，其余规则被放到二级流表中。每个流表都使用基本的流表查找算法。因此，本发明与其他数据包分类算法兼容。当数据包到达时，本发明会先查找一级流表中的规则，如果数据包匹配一级流表中的规则，则按照匹配到一级流表中的规则的动作域进行转发，如果数据包不匹配一级流表中的任何一条规则，本发明会查找二级流表，按照二级流表中的规则进行转发。由于本发明将少量命中数大的规则放到一级流表中，所以一级流表的大小较小，可以比较快地进行数据包分类过程。而命中二级流表的数据包需要经过一级流表和二级流表两次查找，查找速度较慢。而网络流量的偏斜性使得大多数的数据包被一级流表转发，因此能够加速软件数据包分类过程。
[0010]
为达上述目的，本发明一方面提出了一种软件数据包分类加速方法，包括：
[0011]
根据最优的流表分割比获取一级流表存储的第一命中规则和二级流表存储的第二命中规则；其中，第一命中规则为命中数目高于第一预设数值的规则，第二命中规则为命中数目低于第一预设数值的规则；
[0012]
当输入数据包时遍历一级流表，如果数据包匹配第一命中规则，则将第一命中规则作为目标命中规则，根据目标命中规则转发对应的数据包；
[0013]
如果数据包不匹配所述第一命中规则，则遍历二级流表，将与数据包匹配的第二命中规则作为目标命中规则，并根据目标命中规则转发所述数据包。
[0014]
根据本发明实施例的软件数据包分类加速方法还可以具有以下附加技术特征：
[0015]
进一步地，在本发明的一个实施例中，所述根据最优的流表分割比获取一级流表存储的第一命中规则和二级流表存储的第二命中规则，包括：获取一级流表的第一查表时延和二级流表的第二查表时延；通过所述第一查表时延和所述第二查表时延以及测量第一命中规则的命中数比，得到第三查表时延；以及，基于所述第三查表时延确定初始流表分割比的第四查表时延，从所述第四查表时延中选择时延小于第二预设数值的最优流表分割比，以根据最优的流表分割比获取一级流表存储的第一命中规则和二级流表存储的第二命中规则。
[0016]
进一步地，在本发明的一个实施例中，所述测量第一命中规则的命中数比，包括：为所述第一命中规则的每个规则对应设置一个计数器，当有数据包命中所述第一命中规则时，根据命中的规则数目增加相应的计数器；使用最小堆数据结构对计数器计数的规则命中数目进行排序，根据排序结果选择命中数目大于第三预设数值的规则以得到所述第一命中规则的命中数比。
[0017]
进一步地，在本发明的一个实施例中，所述在根据最优的流表分割比获取一级流表存储的第一命中规则和二级流表存储的第二命中规则之前，所述方法还包括：当第一规则放入所述一级流表时，从数据结构中查询优先级高于所述第一规则并重叠的第二规则；从所述第二规则中选取放入所述一级流表中命中数大于第四预设数值的第三规则；将所述第三规则和优先级高于所述第三规则的规则进行合并，将合并后的规则替换所述一级流表中的规则。
[0018]
为达到上述目的，本发明另一方面提出了一种软件数据包分类加速装置，包括：
[0019]
规则确定模块，用于根据最优的流表分割比获取一级流表存储的第一命中规则和二级流表存储的第二命中规则；其中，所述第一命中规则为命中数目高于第一预设数值的规则，所述第二命中规则为命中数目低于所述第一预设数值的规则；
[0020]
第一匹配转发模块，用于当输入数据包时遍历所述一级流表，如果数据包匹配所述第一命中规则，则将所述第一命中规则作为目标命中规则，根据所述目标命中规则转发对应的数据包；
[0021]
第二匹配转发模块，用于如果数据包不匹配所述第一命中规则，则遍历所述二级流表，将与所述数据包匹配的第二命中规则作为所述目标命中规则，并根据所述目标命中规则转发所述数据包。
[0022]
本发明第三方面提出了一种计算机设备，包括处理器和存储器；
[0023]
其中，所述处理器通过读取所述存储器中存储的可执行程序代码来运行与所述可
执行程序代码对应的程序，以用于实现软件数据包分类加速方法。
[0024]
本发明第四方面提出了一种非临时性计算机可读存储介质，其上存储有计算机程序，其特征在于，该程序被处理器执行时实现软件数据包分类加速方法。
[0025]
本发明实施例的软件数据包分类加速方法、装置、设备及存储介质，优化命中数大的规则的查表时延，确定了优化规则的比例提高整体的优化效率。
[0026]
本发明附加的方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本发明的实践了解到。
附图说明
[0027]
本发明上述的和/或附加的方面和优点从下面结合附图对实施例的描述中将变得明显和容易理解，其中：
[0028]
图1为根据本发明实施例的软件数据包分类加速方法的流程图；
[0029]
图2为根据本发明实施例的双流表加速软件数据包分类架构图；
[0030]
图3为根据本发明实施例的软件数据包分类加速算法架构图；
[0031]
图4为根据本发明实施例的规则交换和更新过程示意图；
[0032]
图5为根据本发明实施例的遗传算法探索流表分割比的过程示意图；
[0033]
图6为根据本发明实施例的不同优先级规则依赖问题解决举例示意图；
[0034]
图7为根据本发明实施例的实现架构示意图；
[0035]
图8为根据本发明实施例的软件数据包分类加速装置结构示意图；
[0036]
图9为根据本发明实施例的计算机设备。
具体实施方式
[0037]
需要说明的是，在不冲突的情况下，本技术中的实施例及实施例中的特征可以相互组合。下面将参考附图并结合实施例来详细说明本发明。
[0038]
为了使本技术领域的人员更好地理解本发明方案，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分的实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都应当属于本发明保护的范围。
[0039]
下面参照附图描述根据本发明实施例提出的软件数据包分类加速方法、装置、设备及存储介质。
[0040]
图1是本发明一个实施例的软件数据包分类加速方法的流程图。
[0041]
如图1所示，该方法包括但不限于以下步骤：
[0042]
s1，根据最优的流表分割比获取一级流表存储的第一命中规则和二级流表存储的第二命中规则；其中，第一命中规则为命中数目高于第一预设数值的规则，第二命中规则为命中数目低于第一预设数值的规则；
[0043]
s2，当输入数据包时遍历一级流表，如果数据包匹配第一命中规则，则将第一命中规则作为目标命中规则，根据目标命中规则转发对应的数据包；
[0044]
s3，如果数据包不匹配所述第一命中规则，则遍历二级流表，将与数据包匹配的第
二命中规则作为目标命中规则，并根据目标命中规则转发数据包。
[0045]
可以理解的是，为了利用流量的偏斜性优化数据包分类算法，本发明为了加速命中频繁规则的查表速度，从而加速数据包分类过程，本发明将流表划分为两级，命中频繁的规则被放到一级流表中，其余规则被放到二级流表中。每个流表都使用基本的流表查找算法 (本发明称为基本算法)。因此，本发明与其他数据包分类算法兼容。当数据包到达时，本发明会先查找一级流表中的规则，如果数据包匹配一级流表中的规则，则按照匹配到一级流表中的规则的动作域进行转发，如果数据包不匹配一级流表中的任何一条规则，本发明会查找二级流表，按照二级流表中的规则进行转发。由于本发明将少量命中数大的规则放到一级流表中，所以一级流表的大小较小，可以比较快地进行数据包分类过程。而命中二级流表的数据包需要经过一级流表和二级流表两次查找，查找速度较慢。而网络流量的偏斜性使得大多数的数据包被一级流表转发，因此能够加速软件数据包分类过程。
[0046]
作为一种示例，为确定加速流表中规则的比例，本发明将流表分割比k定义为一级流表大小和一级流表大小与二级流表大小总和的比值，也就是加速流表中规则的比例，流表分割比会影响软件数据包分类加速算法的性能和查表时延。根据分析发现，流表分割比的确定与流量偏斜性相关，当流量比较偏斜时，只要把小部分规则放入一级流表就能够得到比较快的流表查找速度和比较低的查表时延。而当流量分布比较均匀时，就需要将较多的规则放入一级流表中。本发明使用遗传算法来寻找能使查表时延最短的流表分割比。
[0047]
第一方面，本发明结合估算和测量方法来估计查表时延。本发明对查表时延的估计分为两个步骤。首先，本发明会估计一级流表和二级流表的查表时延。然后，本发明会实时测量一级流表的命中数比(命中数比为选取规则的命中数之和与规则的总命中数的比值)，然后根据一级流表命中数比和两个流表的查表时延估算算法整体的查表时延。为了测量一级流表命中数比，本发明为每个规则维护一个计数器，当有数据包命中规则时，增加计数器。此外，本发明使用最小堆数据结构对规则的命中数进行排序，选择命中数大的规则。
[0048]
第二方面，本发明采用遗传算法来对流表分割比进行探索。本发明首先会初始化一些流表分割比，然后会估计这些分割比对应的查表时延，选择查表时延较小的分割比。最后，使用查表时延较小的分割比生成下一次迭代的数据。经过几轮迭代，遗传算法可以得到合适的分割比。
[0049]
下面结合附图对本发明实施例的软件数据包分类加速方法进行详细阐述。
[0050]
本发明将流表分成两级，即一级流表和二级流表，每个流表使用现有的流表查找算法，如图2所示。本发明将命中频繁的规则放入一级流表中，而其他规则放入二级流表中。当数据包到达时，首先查找一级流表，如果数据包不匹配一级流表中的规则，再查找二级流表。由于流量具有偏斜性，而且一级流表中的规则命中频繁，大部分的数据包都在一级流表中被转发。此外，一级流表的流表规模较小，数据包分类速度较快，因此本发明加速了大部分数据包的查表速度，降低了整个流表查找算法的查表时延。此外，由于流量的偏斜性和规则命中数大小的排名在变化，两个表的规则会进行交换。
[0051]
进一步地，本发明可以降低查表时延的原因，将流表分割比定义为k，在双流表加速软件数据包分类架构下，平均查表时延由两部分产生，第一部分由命中一级流表的数据包产生，第二部分由没有命中一级流表但命中二级流表的数据包产生。数据包命中一级流表的概率为一级流表命中数比，数据包没有命中一级流表但命中二级流表的概率为二级流
表命中数比，因此平均查表时延t可以按照如下的方式计算。
[0052]
t＝f(k)t(k)+(1-f(k))(t(k)+t(1-k))
[0053]
＝t(k)+t(1-k)-f(k)t(1-k)
[0054]
＝t(k)+t(1-k)(1-f(k))
[0055]
其中f(k)表示命中数最大的占总规则数的比例为k的规则的命中数比。t(k)和t(1-k)分别表示一级流表的平均查表时延和二级流表的平均查表时延。
[0056]
根据流量特征，命中数排名靠前的规则的命中频率占比较大，因此1-f(k)较小，因为一级流表的流表规模较小，所以t(k)比较小，因此本发明通过流量的偏斜性降低了较大的二级流表较慢的查表速度对总体查表速度的影响。因此，本发明能利用流量偏斜性提高整个流表的查找速度。
[0057]
进一步地，本发明基于上述关键思想来加速数据包分类过程、降低流表查找时延。本发明的架构如图3所示。
[0058]
具体地，本发明使用较小的流表加速命中频繁的规则的查表速度。本发明按流表中规则频率的大小将流表分为两个部分，一级流表存储命中频繁的规则，二级流表存储命中不频繁的规则，每个流表使用现有的流表查找算法作为基本算法。当数据包到达时，首先查找一级流表，如果没有匹配到一级流表中的规则，再查找二级流表。一级流表的大小通常小于二级流表。大多数数据包在一级流表完成查找。因此，本发明加速了数据包分类过程。由于流大小和流量偏斜程度是动态变化的，两个流表中的规则也应该是动态变化的，gemini 设计了规则交换过程和规则更新过程来分别处理规则排名的变化和流表分割比的变化。
[0059]
具体地，本发明使用遗传算法估计流表分割比。为了找到合适的流表分割比，本发明需要估计查表时延和探索流表分割比。由于重新构造流表并测量查表时延的代价比较大，本发明通过估计基本算法的查表时延和测量一级流表规则的命中数比来获得算法总体的查表时延。本发明将查表时延的估计分为两个步骤。首先，本发明使用内存访问次数估计基本算法的查表时延。然后，本发明使用计数器和最小堆结构来测量命中数比。获得查表时延后，本发明使用遗传算法来探索合适的流表分割比。在使用遗传算法时，本发明首先会初始化流表分割比，然后获得这些流表分割比对应的查表时延。本发明在每轮迭代中剔除查表时延较大的分割比并使用剩下的流表分割比来生成新一轮迭代的流表分割比。
[0060]
具体地，由于本发明将流表分为两级，而不同流表规则有不同的优先级，如果没有适当地分割流表，分割后的流表和分割前的流表语义就会不一致。本发明使用有向无环图 (directed acyclic graph，dag)来存储规则的优先级并在更新两级流表时考虑优先级关系。
[0061]
进一步地，本发明按照规则命中数的大小将流表分为两级，命中频繁的规则被放入一级流表中，命中不频繁的规则被放入二级流表中。但是，规则的排名和流量的偏斜程度会发生变化。本发明使用规则交换过程来应对规则排名的变化，保证一级流表中的规则是当前命中频繁的规则。本发明使用规则更新过程来应对流量偏斜程度的变化，保证当前的流表分割比可以让查表时延较小。
[0062]
作为一种示例，规则交换和更新过程如图4所示。
[0063]
规则交换过程：
[0064]
本发明通过规则交换过程交换一级流表和二级流表中的规则，保证当前命中频繁的规则在一级流表中，如图4示。
[0065]
为了记录规则的命中数大小，本发明为每条流表中的规则分配一个计数器，当有一个数据包命中该规则时，本发明会增加该计数器。
[0066]
此外，本发明维护一个最小堆来对计数器进行排序，识别命中频繁的规则。最小堆中存储着当前命中频繁的规则和其对应的计数器。当排名发生变化时，本发明将这些规则交换到二级流表中。由于两个流表规则更新速度较快，可以在更新最小堆的同时同步更新流表中的规则，如表1所示。
[0067]
表1
[0068][0069]
算法1给出了识别和交换规则的伪代码。当数据包命中某条规则时，gemini会增加并查询规则计数器(算法1的第1-2行)，然后判断当前命中的规则是否在最小堆中，如果在最小堆中，则用查询到的规则计数器的值来更新最小堆中这条规则的计数器(算法1的第 3-4行)，否则判断堆是否已满，如果最小堆没满，则直接将这条规则插入到最小堆中，并将规则插入一级流表(算法1的第5-7行)，否则判断当前的规则计数器和最小堆的堆顶元素的相对大小，如果当前的规则计数器小于堆顶元素，说明不需要规则交换；如果当前的规则计数器大于堆顶元素，则说明这条规则应该替换一级流表中的规则。在一级流表中，用这条规则替换堆顶对应的规则。在最小堆中，删除堆顶规则，并插入这条规则(算法1 的第8-13行)。
[0070]
规则更新过程：
[0071]
本发明会根据命频率比来定期设定合适的流表分割比。每隔一段时间，本发明会会重新设置流表分割比，当流表查找算法接收到新设置的流表分割比时，会更新一级流表和二级流表的大小和规则并更新最小堆的大小。
[0072]
进一步地，本发明使用遗传算法来探索合适的流表分割比，优化目标为最小化算法的查表时延。具体来讲本发明通过估计内存访问次数来估计基本算法的查表时延，然后测量命中数排名靠前的规则的命中数比，通过基本算法的查表时延和命中数比来计算本发
明的查表时延，并且通过遗传算法来探索合适的流表分割比。
[0073]
估计查表时延：
[0074]
本发明根据公式t＝t(k)+t(1-k)(1-f(k))将查表时延的估计过程分解为两步。首先，本发明会测量使用特定流表分割比k时的命中数比(f(k))，然后估计基本算法的查表时延(t(k)和t(1-k))，本发明使用内存访问次数来估计查表时延。
[0075]
为了测量命中数比f(k)，本发明将流表中的每条规则与一个计数器相关联，并维护一个最小堆来存储命中数大的规则。每次数据包到达时，本发明更新流表计数器和最小堆。
[0076]
命中数比f(k)可以通过最小堆中的计数器的总和除以所有规则的计数器总和来获得。
[0077]
由于重新构造流表查找算法数据结构的时间较长，本发明算法选择通过内存访问次数估计两个流表的查表时延t(k)和t(1-k)。
[0078]
探索流表分割比：
[0079]
为了得到合适的流表分割比，本发明使用遗传算法来探索流表分割比，并找到能使查表时延较小的流表分割比。探索流表分割比的过程如图5和表2所示。
[0080]
给定初始化流表分割比的数量和迭代次数，本发明首先初始化流表分割比(算法2中的第1-3行)。然后，本发明执行多次迭代找到使查表时延较短的流表分割比(算法2中的第4-16行)。
[0081]
在每次迭代中，本发明计算查表时延(算法2中的第5-7行)。算法2中的第6行，get_time() 函数可以获得基本算法的分类时间，get_hit_ratio()函数计算最小堆中计数器的总和与所有计数器的总和之比。
[0082]
然后，gemini选择查表时延较小的流表分割比生成下一次迭代的一部分流表分割比(算法 2中的第8行)。生成的分割比及当前查表时延较小的分割比组成了下一次迭代的初始分割比(算法2中的第9-14行)。为了避免搜索过程陷入局部最优解，算法中加入了一些随机突变(算法2中的第15行)。
[0083]
表2
[0084][0085]
由于本发明将流表分为两级，而不同流表规则有不同的优先级，如果没有适当地分割流表，分割后的流表和分割前的流表语义就会不一致。比如规则a和规则b具有依赖关系，规则a的优先级小于规则b，存在数据包可以同时匹配规则a和规则b。如果将规则a放入了一级流表中，规则b放入二级流表中，数据包就被一级流表中的规则a错误地转发。因此本发明在进行规则的交换和流表的分割时，必须考虑规则的优先级。具体而言，如果一条规则被放入了一级流表，则比这条规则优先级高且和这条规则有依赖关系的规则也要放入一级流表。现有的工作对该问题已经有深入的研究，本发明使用dag(有向无环图， directed acyclic graph)数据结构来存储和查询规则的优先级。
[0086]
表3给出了解决优先级依赖问题算法的伪代码。当规则被放入一级流表时，本发明首先从dag数据结构中查询优先级更高且重叠的规则(算法3中的第1-2行)。 get_overlapped_higher_priority_rules(dag,large_rule)可以从dag数据结构获取优先级更高的重叠规则。然后本发明将要放入一级流表中命中数大的规则和比该规则优先级高的规则合并，替换一级流表中的规则(算法3中的第3-5行)。
[0087]
表3
[0088]
[0089]
比如，如图6所示，当规则a被放入一级流表，比规则a优先级更高且有重叠的规则b、 c、f也应该被放入一级流表中。
[0090]
优选地，本发明可以使用c++代码实现原型系统。本发明的原型系统主要由两部分组成，流表管理模块和流表分割比搜索模块。本发明的系统实现如图7所示。
[0091]
流表管理模块：
[0092]
作为一种示例，流表管理模块由一级流表、二级流表、流表计数器、最小堆数据结构和优先级管理算法实现。本发明采用cuttss、pstss和partitionsort作为基本算法实现两个流表的流表查找算法。计数器与最小堆可以识别命中数较大的规则。二级流表和一级流表实时交换规则，保证命中数较大的规则在一级流表中。流表分割比搜索模块将最近搜索到的流表分割比发送给流表管理模块，流表管理模块将收到的流表分割比应用到一级流表和二级流表上。而优先级管理算法处理一级流表和二级流表中的重叠规则之间的优先级冲突问题。
[0093]
流表分割比搜索模块：
[0094]
作为一种示例，流表分割比搜索模块搜索合适的流表分割比，并发送给流表管理模块。流表分割比搜索模块使用遗传算法搜索合适的流表分割比。本发明需要为遗传算法设置初始化流表分割比的数量和算法迭代的轮数。在具体实现中，gemini将初始化流表分割比的数量设置为4，算法迭代的轮数设置为5。遗传算法在执行过程中，首先初始化4个流表分割比，然后估计这4个流表分割比对应的查表时延，选择时延小的分割比，生成下一次迭代的分割比，并随机地改变一些分割比，防止落入局部最优解。
[0095]
根据本发明实施例的软件数据包分类加速方法，可以解决上述的问题，高效地进行数据包分类。
[0096]
为了实现上述实施例，如图8所示，本实施例中还提供了软件数据包分类加速装置10，该装置10包括：规则确定模块100、第一匹配转发模块200和第二匹配转发模块300。
[0097]
规则确定模块100，用于根据最优的流表分割比获取一级流表存储的第一命中规则和二级流表存储的第二命中规则；其中，第一命中规则为命中数目高于第一预设数值的规则，第二命中规则为命中数目低于第一预设数值的规则；
[0098]
第一匹配转发模块200，用于当输入数据包时遍历一级流表，如果数据包匹配第一命中规则，则将第一命中规则作为目标命中规则，根据目标命中规则转发对应的数据包；
[0099]
第二匹配转发模块300，用于如果数据包不匹配第一命中规则，则遍历二级流表，将与数据包匹配的第二命中规则作为目标命中规则，并根据目标命中规则转发数据包。
[0100]
进一步的，上述规则确定模块100，包括：
[0101]
第一时延子单元，用于获取一级流表的第一查表时延和二级流表的第二查表时延；
[0102]
第二时延子单元，用于通过第一查表时延和第二查表时延以及测量第一命中规则的命中数比，得到第三查表时延；以及，
[0103]
第三时延子单元，用于基于第三查表时延确定初始流表分割比的第四查表时延，从第四查表时延中选择时延小于第二预设数值的最优流表分割比，以根据最优的流表分割比获取一级流表存储的第一命中规则和二级流表存储的第二命中规则。
[0104]
进一步的，上述第二时延子单元，还用于：
[0105]
为第一命中规则的每个规则对应设置一个计数器，当有数据包命中第一命中规则时，根据命中的规则数目增加相应的计数器；
[0106]
使用最小堆数据结构对计数器计数的规则命中数目进行排序，根据排序结果选择命中数目大于第三预设数值的规则以得到第一命中规则的命中数比。
[0107]
进一步的，在上述规则确定模块100之前，还包括，优先级确定模块，具体用于：
[0108]
当第一规则放入所述一级流表时，从数据结构中查询优先级高于第一规则并重叠的第二规则；
[0109]
从第二规则中选取放入一级流表中命中数大于第四预设数值的第三规则；
[0110]
将第三规则和优先级高于第三规则的规则进行合并，将合并后的规则替换一级流表中的规则。
[0111]
根据本发明实施例的软件数据包分类加速装置，可以解决上述的问题，高效地进行数据包分类。
[0112]
为了实现上述实施例的方法，本发明还提供了一种计算机设备，如图9所示，该计算机设备600包括存储器601、处理器602；其中，所述处理器602通过读取所述存储器601 中存储的可执行程序代码来运行与所述可执行程序代码对应的程序，以用于实现上文所述软件数据包分类加速方法的各个步骤。
[0113]
为了实现上述实施例的方法，本发明还提供了一种非临时性计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现软件数据包分类加速方法。
[0114]
此外，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括至少一个该特征。在本发明的描述中，“多个”的含义是至少两个，例如两个，三个等，除非另有明确具体的限定。
[0115]
在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不必须针对的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任一个或多个实施例或示例中以合适的方式结合。此外，在不相互矛盾的情况下，本领域的技术人员可以将本说明书中描述的不同实施例或示例以及不同实施例或示例的特征进行结合和组合。
[0116]
尽管上面已经示出和描述了本发明的实施例，可以理解的是，上述实施例是示例性的，不能理解为对本发明的限制，本领域的普通技术人员在本发明的范围内可以对上述实施例进行变化、修改、替换和变型。
技术特征：1.一种软件数据包分类加速方法，其特征在于，包括以下步骤：根据最优的流表分割比获取一级流表存储的第一命中规则和二级流表存储的第二命中规则；其中，所述第一命中规则为命中数目高于第一预设数值的规则，所述第二命中规则为命中数目低于所述第一预设数值的规则；当输入数据包时遍历所述一级流表，如果数据包匹配所述第一命中规则，则将所述第一命中规则作为目标命中规则，根据所述目标命中规则转发对应的数据包；如果数据包不匹配所述第一命中规则，则遍历所述二级流表，将与所述数据包匹配的第二命中规则作为所述目标命中规则，并根据所述目标命中规则转发所述数据包。2.根据权利要求1所述的方法，其特征在于，所述根据最优的流表分割比获取一级流表存储的第一命中规则和二级流表存储的第二命中规则，包括：获取一级流表的第一查表时延和二级流表的第二查表时延；通过所述第一查表时延和所述第二查表时延以及测量第一命中规则的命中数比，得到第三查表时延；以及，基于所述第三查表时延确定初始流表分割比的第四查表时延，从所述第四查表时延中选择时延小于第二预设数值的最优流表分割比，以根据最优的流表分割比获取一级流表存储的第一命中规则和二级流表存储的第二命中规则。3.根据权利要求2所述的方法，其特征在于，所述测量第一命中规则的命中数比，包括：为所述第一命中规则的每个规则对应设置一个计数器，当有数据包命中所述第一命中规则时，根据命中的规则数目增加相应的计数器；使用最小堆数据结构对计数器计数的规则命中数目进行排序，根据排序结果选择命中数目大于第三预设数值的规则以得到所述第一命中规则的命中数比。4.根据权利要求1所述的方法，其特征在于，所述在根据最优的流表分割比获取一级流表存储的第一命中规则和二级流表存储的第二命中规则之前，所述方法还包括：当第一规则放入所述一级流表时，从数据结构中查询优先级高于所述第一规则并重叠的第二规则；从所述第二规则中选取放入所述一级流表中命中数大于第四预设数值的第三规则；将所述第三规则和优先级高于所述第三规则的规则进行合并，将合并后的规则替换所述一级流表中的规则。5.一种软件数据包分类加速装置，其特征在于，包括：规则确定模块，用于根据最优的流表分割比获取一级流表存储的第一命中规则和二级流表存储的第二命中规则；其中，所述第一命中规则为命中数目高于第一预设数值的规则，所述第二命中规则为命中数目低于所述第一预设数值的规则；第一匹配转发模块，用于当输入数据包时遍历所述一级流表，如果数据包匹配所述第一命中规则，则将所述第一命中规则作为目标命中规则，根据所述目标命中规则转发对应的数据包；第二匹配转发模块，用于如果数据包不匹配所述第一命中规则，则遍历所述二级流表，将与所述数据包匹配的第二命中规则作为所述目标命中规则，并根据所述目标命中规则转发所述数据包。6.根据权利要求5所述的装置，其特征在于，所述规则确定模块，包括：
第一时延子单元，用于获取一级流表的第一查表时延和二级流表的第二查表时延；第二时延子单元，用于通过所述第一查表时延和所述第二查表时延以及测量第一命中规则的命中数比，得到第三查表时延；以及，第三时延子单元，用于基于所述第三查表时延确定初始流表分割比的第四查表时延，从所述第四查表时延中选择时延小于第二预设数值的最优流表分割比，以根据最优的流表分割比获取一级流表存储的第一命中规则和二级流表存储的第二命中规则。7.根据权利要求6所述的装置，其特征在于，所述第二时延子单元，还用于：为所述第一命中规则的每个规则对应设置一个计数器，当有数据包命中所述第一命中规则时，根据命中的规则数目增加相应的计数器；使用最小堆数据结构对计数器计数的规则命中数目进行排序，根据排序结果选择命中数目大于第三预设数值的规则以得到所述第一命中规则的命中数比。8.根据权利要求6所述的装置，其特征在于，在所述规则确定模块之前，所述装置，还包括，优先级确定模块，具体用于：当第一规则放入所述一级流表时，从数据结构中查询优先级高于所述第一规则并重叠的第二规则；从所述第二规则中选取放入所述一级流表中命中数大于第四预设数值的第三规则；将所述第三规则和优先级高于所述第三规则的规则进行合并，将合并后的规则替换所述一级流表中的规则。9.一种计算机设备，其特征在于，包括处理器和存储器；其中，所述处理器通过读取所述存储器中存储的可执行程序代码来运行与所述可执行程序代码对应的程序，以用于实现如权利要求1-4中任一项所述的软件数据包分类加速方法。10.一种非临时性计算机可读存储介质，其上存储有计算机程序，其特征在于，该程序被处理器执行时实现如权利要求1-4中任一项所述的软件数据包分类加速方法。
技术总结本发明公开了一种软件数据包分类加速方法、装置、设备及存储介质，该方法包括：根据最优的流表分割比获取一级流表存储的第一命中规则和二级流表存储的第二命中规则；其中，第一命中规则为命中数目高于第一预设数值的规则，第二命中规则为命中数目低于第一预设数值的规则；当输入数据包时遍历一级流表，如果数据包匹配第一命中规则，则将第一命中规则作为目标命中规则，根据目标命中规则转发对应的数据包；如果数据包不匹配第一命中规则，则遍述二级流表，将与数据包匹配的第二命中规则作为目标命中规则，并根据目标命中规则转发所述数据包。该方法可以高效地进行数据包分类。该方法可以高效地进行数据包分类。该方法可以高效地进行数据包分类。
技术研发人员：李丹 王砚舒 吴建平
受保护的技术使用者：清华大学
技术研发日：2022.07.13
技术公布日：2022/11/1
