CN117336216A - 一种基于滑动窗口的流基数测量方法及系统 - Google Patents

Abstract

本发明涉及一种基于滑动窗口的流基数测量方法及系统，所述方法包括：获取高速网络数据包流；所述高速网络数据包流包括数据包；根据所述数据包生成流元素，且将所述数据包解析生成流标签和流元素标签；将所述流元素标签进行哈希运算生成运算结果；根据所述运算结果将所述流元素存储至虚拟寄存器组；将所述虚拟寄存器组合并生成合并结果；对所述合并结果进行流基数估计生成估计结果。通过引入虚拟寄存器技术，降低了片上空间资源开销，解决了目前无法同时测量多条流基数的问题。通过分别对虚拟寄存器的第一部分和第二部分进行基数估计并相减的方法消除噪声，降低了每次基数估计的寄存器访问次数，进而提高了基数查询的效率。

Description

一种基于滑动窗口的流基数测量方法及系统

技术领域

本发明涉及网络测量技术领域，尤其是指一种基于滑动窗口的流基数测量方法及系统。

背景技术

近年来的高速网络中，对流量进行准确估计为实现攻击检测、负载均衡等应用的重要基础数据。随着大数据时代的发展，网络规模和流速不断增长和扩大。根据Ericsson提供的统计数据，2022年第三季度每月的移动网络流量达到108EB，相比于2020年同期的55EB增长了近乎一倍。 在高速网络环境下，流量测量方法需要耗费大量的高速存储资源，然而这种资源十分稀缺且昂贵，这对在有限高速处理资源条件下进行精确的流量测量提出了严峻的挑战。因此有必要改进在高速网络中流量测量的方法。

当前业界有多种流量测量模型，我们所关注的是滑动时间窗口模型下的流基数测量。滑动时间窗口模型下的流基数测量的主要难点在于如何在保证测量精度的同时动态更新存储的流信息。现有的流基数测量算法由于元素在sketch中的插入操作具有随机化的特点且上述算法为了节省片上的空间消耗丢失了流元素的时间信息，无法适用于滑动时间窗口模型。

为了解决滑动时间窗口模型下流基数测量算法问题，我们要在保证一定准确性的前提下降低检测系统所需要的计算和存储开销，同时最大程度的减少该系统对网络的影响。其中需要解决关键技术问题如下：降低存储所有流信息的空间开销，保证采样流量的实时性，有效性；保证流元素信息的完整性；提高算法的准确性，鲁棒性。

需要说明的是，在上述背景技术部分公开的信息仅用于加强对本公开的背景的理解，因此可以包括不构成对本领域普通技术人员已知的现有技术的信息。

发明内容

为此，本发明所要解决的技术问题在于克服现有技术中基于紧凑数据摘要的流基数估计算法为了减小片上空间开销，需要进行位级别或者寄存器级别的内存共享，导致流信息混杂在一起，估计每条流的基数时需要考虑到其他流带来的噪声。并且每次进行流基数估计需要扫描整个sketch，因此无法支持实时查询。同时由于存储空间的限制，无法记录流元素的时间信息，因此不能适用于滑动时间窗口模型。

为解决上述技术问题，本发明的第一方面提供了一种基于滑动窗口的流基数测量方法，所述方法包括：

获取高速网络数据包流；所述高速网络数据包流包括数据包；

根据所述数据包生成流元素，且将所述数据包解析生成流标签和流元素标签

将所述流元素标签进行哈希运算生成运算结果；

根据所述运算结果将所述流元素存储至虚拟寄存器组；

将所述虚拟寄存器组合并生成合并结果；

对所述合并结果进行流基数估计生成估计结果。

在本发明的一个实施例中，根据所述运算结果将所述流元素存储至虚拟寄存器组的步骤还包括：

若所述运算结果小于预设阈值，则所述流元素存储至所述虚拟寄存器的第一部分；

若所述运算结果大于或等于所述预设阈值，则所述流元素存储至所述虚拟寄存器的第二部分。

在本发明的一个实施例中，所述流元素根据预设比例存储至所述虚拟寄存器组的所述第一部分和所述第二部分。

在本发明的一个实施例中，将所述虚拟寄存器组合并生成合并结果的步骤还包括：

所述合并结果为所述虚拟寄存器中的最大值。

在本发明的一个实施例中，对所述合并结果进行流基数估计生成估计结果的步骤还包括：

对所述第一部分中的流元素进行流基数估计，生成第一结果；

对所述第二部分中的流元素进行流基数估计，生成第二结果；

根据所述第一结果和所述第二结果计算所述估计结果。

在本发明的一个实施例中，对所述第一部分中的流元素进行流基数估计，生成第一结果采用以下公式：

其中，α是偏差修正常量，s为数据包流所分配的虚拟寄存器的数量，v_f为流标签对应的所述虚拟寄存器的值。

在本发明的一个实施例中，对所述第二部分中的流元素进行流基数估计，生成第二结果采用以下公式：

其中，α是偏差修正常量，s为数据包流所分配的虚拟寄存器的数量，v_f为流标签对应的所述虚拟寄存器的值。

在本发明的一个实施例中，根据所述第一结果和所述第二结果计算所述估计结果采用以下公式：

其中，为第二结果，/>为第一结果。

在本发明的一个实施例中，根据所述第一结果和所述第二结果计算所述估计结果的步骤还包括：

若所述第二结果小于所述第一结果，则所述估计结果为所述第二结果。

本发明的第二方面提供了一种基于滑动窗口的流基数测量系统，所述系统包括：获取模块，解析模块，计算模块；

所述获取模块被配置为：获取高速网络数据包流；所述高速网络数据包流包括数据包；

所述解析模块被配置为：根据所述数据包生成流元素，且将所述数据包解析生成流标签和流元素标签；

所述计算模块被配置为：将所述流元素标签进行哈希运算生成运算结果；根据所述运算结果将所述流元素存储至虚拟寄存器组；将所述虚拟寄存器组合并生成合并结果；对所述合并结果进行流基数估计生成估计结果。

本发明的上述技术方案相比现有技术具有以下优点：

本发明所述的一种基于滑动窗口的流基数测量方法及系统，通过引入虚拟寄存器技术，降低了片上空间资源开销，解决了目前无法同时测量多条流基数的问题。通过分别对虚拟寄存器的第一部分和第二部分进行基数估计并相减的方法消除噪声，降低了每次基数估计的寄存器访问次数，进而提高了基数查询的效率。

附图说明

为了使本发明的内容更容易被清楚的理解，下面根据本发明的具体实施例并结合附图，对本发明作进一步详细的说明。

图1是本发明提供的一种基于滑动窗口的流基数测量方法及系统的流程图；

图2是本发明提供的一种基于滑动窗口的流基数测量方法及系统中滑动时间窗口为10秒且片上空间为2MB的统计图；

图3是本发明提供的一种基于滑动窗口的流基数测量方法及系统中滑动时间窗口为10秒且片上空间为4MB的统计图；

图4是本发明提供的一种基于滑动窗口的流基数测量方法及系统中滑动时间窗口为20秒且片上空间为2MB的统计图；

图5是本发明提供的一种基于滑动窗口的流基数测量方法及系统中滑动时间窗口为20秒且片上空间为4MB的统计图；

图6是本发明提供的一种基于滑动窗口的流基数测量方法及系统中滑动时间窗口为60秒且片上空间为2MB的统计图；

图7是本发明提供的一种基于滑动窗口的流基数测量方法及系统中滑动时间窗口为60秒且片上空间为4MB的统计图；

图8是本发明提供的一种基于滑动窗口的流基数测量方法及系统的系统架构图。

具体实施方式

下面结合附图和具体实施例对本发明作进一步说明，以使本领域的技术人员可以更好地理解本发明并能予以实施，但所举实施例不作为对本发明的限定。

参照图1所示，第一方面，本发明提供了一种基于滑动窗口的流基数测量方法，所述方法包括：

S100，获取高速网络数据包流；所述高速网络数据包流包括数据包；

在实际应用场景中，获取高速网络数据包流，其中，高速网络数据包流包括数据包，本申请在片上空间维护m个物理寄存器构成一个寄存器组M，每条高速网络数据包流分配s个虚拟寄存器，每个虚拟寄存器与一个物理寄存器相对应，不同的高速网络数据包流之间可能会共享相同的物理寄存器。在片下存储滑动时间窗口内的物理寄存器数据，每经过一个基本时间单位t(本申请将t设置为1秒)，片上空间内的寄存器组M会被下载到片下，在片下维护由w个寄存器组构成的队列，其中，w为滑动窗口大小。

S200，根据所述数据包生成流元素，且将所述数据包解析生成流标签和流元素标签；

在实际应用场景中，获取多个数据包以后，若设定好需要数据包中的目标IP地址，则将每个数据包中的目标IP地址划出作为流元素，对于获取的每一个数据包pkt，将数据包pkt进行解析，解析出该数据包pkt的流标签f和流元素标签e。

S300，将所述流元素标签进行哈希运算生成运算结果；

在实际应用场景中，对解析后生成的流元素标签e进行哈希运算得到运算结果h(e)，其中，h(e)的范围是[0，2³²-1]，因此我们可以将h(e)看作一个32位2进制串。我们将h(e)的前b位记为p，后(32-b)位记为q，其中b＝log₂s，s为数据包流所分配的虚拟寄存器的数量。

S400，根据所述运算结果将所述流元素存储至虚拟寄存器组；

在步骤S400中，根据所述运算结果将所述流元素存储至虚拟寄存器组的步骤还包括：若所述运算结果小于预设阈值，则所述流元素存储至所述虚拟寄存器的第一部分；若所述运算结果大于或等于所述预设阈值，则所述流元素存储至所述虚拟寄存器的第二部分。其中，所述流元素根据预设比例存储至所述虚拟寄存器组的所述第一部分和所述第二部分。

在实际应用场景中，在VHLL算法中，每次流基数估计的去噪过程中都需要扫描整个寄存器组，在滑动时间窗口模型进行流基数估计的频率显著增加，继续采用VHLL算法的去噪方法会带来巨大的时间开销。为解决上述问题，本申请采用一种新的去噪方式。我们让流标签f中的流元素按照不同比例分配在与该条网络数据包流所对应的虚拟寄存器组的前半部分和后半部分，其中，前半部分为第一部分，后半部分为第二部分。除流标签.f以外的网络数据包流带来的噪声在流标签f所对应的虚拟寄存器上可以看作是均匀分布的，因此本申请采用分别对虚拟寄存器的前半部分和后半部分进行流基数估计并相减的方法消除噪声。当流元素按照1∶5的预设比例分配在虚拟寄存器的两部分时去噪效果较好。

我们利用运算结果h(e)的值来判断流元素该分配在虚拟寄存器的哪个部分，运算结果h(e)的范围是[0，2³²-1]，如果运算结果h(e)的值小于预设阈值2³²/6，那么流元素应该分配在虚拟寄存器的前半部分，也就是虚拟寄存器的第一部分，下标为否则流元素应该分配在后半部分虚拟寄存器，下标为/>q中第一个1的位置是该元素的rank值，例如，若q＝0.001...，那么rank＝4。此外，为了将每一个虚拟寄存器对应到某一个实际的物理寄存器中，我们还需要一个哈希函数H和一个随机数数组R，假设更新的虚拟寄存器下标为index，那么需要更新的物理寄存器下标为/>以下简写为

S500，将所述虚拟寄存器组合并生成合并结果；

在步骤S500中，将所述虚拟寄存器组合并生成合并结果的步骤还包括：所述合并结果为所述虚拟寄存器中的最大值。

在实际应用场景中，在基数估计之前，我们首先对片下的w个寄存器组进行合并操作。由于每个寄存器组均有m个物理寄存器，因此每个物理寄存器会存在w个值，我们选择这w个值中的最大值作为物理寄存器合并后的值。将下标为i的寄存器合并后的值记为M′[i]，则M′[i]＝max(M₀[i]，M₁[i]，...，M_w-1[i])，其中M_k[i]是第k个寄存器组中下标为i的物理寄存器的值，0≤k＜w。其中，对于某一流标签f，我们构建出它所对应的一组虚拟寄存器的值v_f，其中，H为哈希数组，R[s]为随机数数组下标S处的数值。

S600，对所述合并结果进行流基数估计生成估计结果。

在步骤S600中，对所述合并结果进行流基数估计生成估计结果的步骤还包括：对所述第一部分中的流元素进行流基数估计，生成第一结果；对所述第二部分中的流元素进行流基数估计，生成第二结果；根据所述第一结果和所述第二结果计算所述估计结果。对所述第一部分中的流元素进行流基数估计，生成第一结果采用以下公式：

其中，α是偏差修正常量，s为数据包流所分配的虚拟寄存器的数量，v_f为流标签对应的所述虚拟寄存器的值。对所述第二部分中的流元素进行流基数估计，生成第二结果采用以下公式：

其中，α是偏差修正常量，s为数据包流所分配的虚拟寄存器的数量，v_f为流标签对应的所述虚拟寄存器的值。根据所述第一结果和所述第二结果计算所述估计结果采用以下公式：

其中，为第二结果，/>为第一结果。根据所述第一结果和所述第二结果计算所述估计结果的步骤还包括：若所述第二结果小于所述第一结果，则所述估计结果为所述第二结果。

在实际应用场景中，基数估计在片下完成，我们设置一个计时器colck，每当colck经过一秒钟时，我们将片上维护的虚拟寄存器数组下载到片下，如果片下维护的物理寄存器组数量超过了w，则将最早的一个丢弃。之后分别对虚拟寄存器的前半部分和后半部分进行基数估计。其中，对虚拟寄存器第一部分的流元素进行流基数估计时如式(1)所示，α是偏差修正常量，常用数值为α₁₆＝0.673，α₃₂＝0.697，α₆₄＝0.709，由于式(1)对小流的估计偏差较大，当估计结果小于时，用式(4)对虚拟寄存器第一部分的流元素进行流基数估计。

其中，N₁是V_f第一部分中0所占的比例。对虚拟寄存器第二部分的流元素进行流基数估计时如式(2)所示，α是偏差修正常量，常用数值为α₁₆＝0.673，α₃₂＝0.697，α₆₄＝0.709，由于式(2)对小流的估计偏差较大，当估计结果小于时，用式(5)对虚拟寄存器第二部分的流元素进行流基数估计。

其中，N₂是V_f第二部分中0所占的比例。得到和/>后，可以用式(3)计算最终的估计结果，若出现/>小于/>的情况，由于第二部分虚拟寄存器中的流元素的第二结果应该远远大于第一结果，因此认为第一部分虚拟寄存器中的流元素绝大多数来自其他高速网络数据包流的噪声，因此直接返回/>作为估计结果。

参照图2至图7所示，由于目前没有研究实现滑动时间窗口模型下的每条流基数估计，因此本申请中对算法在不同片上存储空间和滑动时间窗口大小条件下的实验结果进行了对比。分别在片上空间为2MB和4MB以及滑动时间窗口大小为10秒，20秒，60秒的条件下对SVHLL算法进行了测试，设定算法的中的参数s＝128，图中每个点表示一条流的估计结果，基数区间按log级划分，横坐标代表流的实际基数，纵坐标代表流的估计基数。图2为片上空间2MB且滑动时间窗口大小为10秒的情况，图3为片上空间4MB且滑动时间窗口大小为10秒的情况，图4为片上空间2MB且滑动时间窗口大小为20秒的情况，图5为片上空间4MB且滑动时间窗口大小为20秒的情况，图6为片上空间2MB且滑动时间窗口大小为60秒的情况，图7为片上空间4MB且滑动时间窗口大小为60秒的情况，不同实验条件下的性能指标如表1和表2所示。

表1：

	10秒	20秒	60秒
				ARE	2.9279	4.4537	8.6334
MAE	4.0497	5.8557	10.5816

表2：

	10秒	20秒	60秒
				ARE	1.6549	2.4103	4.5682
MAE	2.5571	3.4524	5.9075

表1为片上空间2MB条件下不同滑动窗口大小的性能指标，表2为片上空间4MB条件下不同滑动窗口大小的性能指标。其中，ARE为平均相对误差，MAE为平均绝对误差。

由滑动时间窗口为10秒至滑动时间窗口为60秒看出，SVHLL算法在大流部分的估计效果较好，并且在2MB的片上存储空间条件下的ARE和MAE均小于11，在4MB的片上存储空间条件下的ARE和MAE均小于6，误差在允许范围内。

参照图8所示，第二方面，本申请提供了一种基于滑动窗口的流基数测量系统，所述系统包括：获取模块100，解析模块200，计算模块300；

所述获取模块100被配置为：获取高速网络数据包流；所述高速网络数据包流包括数据包；

所述解析模块200被配置为：根据所述数据包生成流元素，且将所述数据包解析生成流标签和流元素标签；

所述计算模块300被配置为：将所述流元素标签进行哈希运算生成运算结果；根据所述运算结果将所述流元素存储至虚拟寄存器组；将所述虚拟寄存器组合并生成合并结果；对所述合并结果进行流基数估计生成估计结果。

上述系统中在应用前述方法时的作用效果可参见前述方法实施例中的说明，在此不再赘述。

本领域内的技术人员应明白，本申请的实施例可提供为方法、系统、或计算机程序产品。因此，本申请可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本申请可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。

本申请是参照根据本申请实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。

这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

显然，上述实施例仅仅是为清楚地说明所作的举例，并非对实施方式的限定。对于所属领域的普通技术人员来说，在上述说明的基础上还可以做出其它不同形式变化或变动。这里无需也无法对所有的实施方式予以穷举。而由此所引申出的显而易见的变化或变动仍处于本发明创造的保护范围之中。

Claims (10)

1.一种基于滑动窗口的流基数测量方法，其特征在于，所述方法包括：

获取高速网络数据包流；所述高速网络数据包流包括数据包；

根据所述数据包生成流元素，且将所述数据包解析生成流标签和流元素标签；

将所述流元素标签进行哈希运算生成运算结果；

根据所述运算结果将所述流元素存储至虚拟寄存器组；

将所述虚拟寄存器组合并生成合并结果；

对所述合并结果进行流基数估计生成估计结果。

2.根据权利要求1所述的一种基于滑动窗口的流基数测量方法，其特征在于，根据所述运算结果将所述流元素存储至虚拟寄存器组的步骤还包括：

若所述运算结果小于预设阈值，则所述流元素存储至所述虚拟寄存器的第一部分；

若所述运算结果大于或等于所述预设阈值，则所述流元素存储至所述虚拟寄存器的第二部分。

3.根据权利要求2所述的一种基于滑动窗口的流基数测量方法系统，其特征在于：所述流元素根据预设比例存储至所述虚拟寄存器组的所述第一部分和所述第二部分。

4.根据权利要求1所述的一种基于滑动窗口的流基数测量方法，其特征在于，将所述虚拟寄存器组合并生成合并结果的步骤还包括：

所述合并结果为所述虚拟寄存器中的最大值。

5.根据权利要求1所述的一种基于滑动窗口的流基数测量方法，其特征在于，对所述合并结果进行流基数估计生成估计结果的步骤还包括：

对所述第一部分中的流元素进行流基数估计，生成第一结果；

对所述第二部分中的流元素进行流基数估计，生成第二结果；

根据所述第一结果和所述第二结果计算所述估计结果。

6.根据权利要求5所述的一种基于滑动窗口的流基数测量方法，其特征在于，对所述第一部分中的流元素进行流基数估计，生成第一结果采用以下公式：

其中，α是偏差修正常量，s为数据包流所分配的虚拟寄存器的数量，v_f为流标签对应的所述虚拟寄存器的值。

7.根据权利要求5所述的一种基于滑动窗口的流基数测量方法，其特征在于，对所述第二部分中的流元素进行流基数估计，生成第二结果采用以下公式：

其中，α是偏差修正常量，s为数据包流所分配的虚拟寄存器的数量，v_f为流标签对应的所述虚拟寄存器的值。

8.根据权利要求5所述的一种基于滑动窗口的流基数测量方法，其特征在于，根据所述第一结果和所述第二结果计算所述估计结果采用以下公式：

其中，为第二结果，/>为第一结果。

9.根据权利要求5所述的一种基于滑动窗口的流基数测量方法，其特征在于，根据所述第一结果和所述第二结果计算所述估计结果的步骤还包括：

若所述第二结果小于所述第一结果，则所述估计结果为所述第二结果。

10.一种基于滑动窗口的流基数测量系统，其特征在于，所述系统包括：获取模块，解析模块，计算模块；

所述获取模块被配置为：获取高速网络数据包流；所述高速网络数据包流包括数据包；

所述解析模块被配置为：根据所述数据包生成流元素，且将所述数据包解析生成流标签和流元素标签；

所述计算模块被配置为：将所述流元素标签进行哈希运算生成运算结果；根据所述运算结果将所述流元素存储至虚拟寄存器组；将所述虚拟寄存器组合并生成合并结果；对所述合并结果进行流基数估计生成估计结果。