用于滑动窗口中网络流量高吞吐量熵估计的流式算法和硬件加速器

《Computer Communications》：Streaming algorithm and hardware accelerator for high-throughput entropy estimation of network flows in sliding windows

本文提出一种适用于滑动时间窗口的离散步熵估计算法及FPGA加速架构，通过合并10个非滑动频率sketch和优化数据结构，在有限内存下实现高精度（相对误差<0.45%）和高速处理（>160Gbps），显著优于传统方法。

　　

雅伊梅·费尔南德斯（Yaime Fernández）|哈维尔·E·索托（Javier E. Soto）|卡罗莱纳·加利亚多-帕维斯（Carolina Gallardo-Pavesi）|亚斯曼尼·普里托（Yasmany Prieto）|塞西莉亚·埃尔南德斯（Cecilia Hernández）|米格尔·菲格罗亚（Miguel Figueroa）

智利圣地亚哥天主教大学（Universidad Católica de la Santísima Concepción）计算机科学系

摘要

香农经验熵（Shannon’s empirical entropy）在网络监控中广泛用于异常检测和资源管理。由于近期流量对预测网络行为最为关键，因此通常在滑动时间窗口上进行熵估计。在现代网络链接中，这一任务涉及高速数据流，其中吞吐量和内存效率都至关重要。硬件加速器能够在网络内部提供低延迟、高能效的处理能力，但面临严格的片上内存限制。我们提出了一种适用于滑动时间窗口的流式算法，采用离散步骤来估计熵，以适应这些硬件约束。该算法结合了频率和基数 sketch（frequency and cardinality sketches）技术，存储最频繁的流量数据，并根据排序后的对数-对数缩放直方图（sorted log–log scaled histogram）来估计其余流量。对于一个大小为$W$的窗口，通过合并十个非滑动频率 sketch（non-sliding frequency sketches）来重建流量频率，每个 sketch 覆盖的时间间隔为$s=W/10$

引言

网络测量对于流量监控应用至关重要，例如异常检测[1]、流量分类[2]、拥塞控制[3]和负载均衡[4]。这些应用依赖于流量的统计特性，包括基数、流量大小和熵[5]。特别是香农熵可以量化概率分布的不确定性。在网络流量中，高熵反映了多样化的活动，例如当许多 IP 地址、端口或协议同时使用时。这种多样性可能对应于分布式通信或扫描攻击。低熵则表明流量集中，主要由少数流量主导，这是分布式拒绝服务（DDoS）攻击等异常行为的特征。因此，随时间监测熵是检测流量分布异常的有效工具[1]、[6]、[7]、[8]。经验香农熵直接从数据集中的元素频率计算得出，需要知道不同元素的数量及其相应的频率。在网络流量中，这些元素通常对应于流量，而流量通常由一组数据包属性（如源地址、目的地址、端口和协议）定义。因此，现代网络中的不同流量数量可能非常大。此外，数据包序列以连续的高速流形式生成，且每个流的数据包分布会随时间变化。

测量网络流量及其属性随时间演变的一种常见方法是将数据划分为窗口，并在每个窗口内应用测量算法。已经提出了多种机制来定义窗口大小和边界，包括基于时间的、基于数据包计数的和基于标志点的[9]。相应的窗口类型包括滑动窗口（sliding windows）、翻滚窗口（tumbling windows）和阻尼窗口（damped windows）。这些方法假设近期数据最为重要，从而减少了处理的数据量并实现了持续更新。其中，基于时间的滑动窗口特别有效，因为它们能够捕捉到最近的网络趋势，而不依赖于数据包的数量[9]。

提高流量测量吞吐量的一种方法是网络内计算[10]。与传统边缘或云架构不同，它利用网络节点的处理能力，使其更接近数据源。这有助于更高效地利用资源，减少流量负载，提高吞吐量并降低延迟[11]。这些进步依赖于硬件加速，例如可编程交换机、智能网络接口卡（NIC）和现场可编程门阵列（FPGA）[12]等技术。特别是 FPGA 通过大量可重构电路提供了高性能和低功耗[13]。这些设备的一个常见限制是片上内存容量较小，通常只有几百 MiB。虽然可以连接外部内存，但这样会显著降低带宽[11]。基于 sketch 的流式算法通过亚线性内存使用和高并行性解决了这一限制。Sketch 是紧凑的概率数据结构，使用不同的更新和估计策略在有限误差范围内估计统计数据[14]、[15]。它们已广泛应用于流量测量，如流量大小[14]、$k$流量检测[16]、[17]以及流量基数估计[18]、[19]，适用于各种窗口机制[5]、[20]。在滑动窗口中，由于需要维护时间戳和管理过期条目，Sketch 通常比非滑动设置需要更多的内存。Zeng 等人[5]提供了针对网络测量的滑动窗口 Sketch 设计的比较分析，涵盖了它们的数据结构、支持的操作、测量任务、实现平台和性能。

在之前的工作中[21]，我们提出了一种算法和基于 FPGA 的硬件加速器，用于估计网络流中数据包频率的经验香农熵。该方法使用 Sketch 来估计流量频率和基数，并结合优先队列数组（priority queue array）来存储前$K$个流量。其余流量的频率根据流量排序后的对数-对数缩放直方图中的观察结果进行拟合。存储的前$K$个流量和拟合后的频率结合起来估计熵。这种方法在一系列公共网络数据集上的平均误差低于 0.7%。然而，该算法仅在单个观察窗口内估计熵，等于数据集的持续时间，无法扩展到滑动窗口，因为数据结构不支持删除过时的流量。

在这项工作中，我们提出了一种新的滑动时间窗口熵估计算法及其对应的 FPGA 加速器，基于我们之前的工作[21]。窗口以离散间隔推进；熵在大小为$W$的窗口中计算，滑动步长为$s=W/10$$s$，外加一个额外的 sketch 以避免估计和擦除操作期间的数据丢失。流量基数通过 sketch 估计，优先队列数组存储每个窗口中的前$K$个流量。与在每个窗口中复制原始算法相比，所提出的方法仅使用一半的内存，同时实现了更低的估计误差。在八个真实流量数据集上测试时，窗口长度为 60 秒，滑动步长为 6 秒，平均相对熵误差低于 0.45%，标准差为 0.14%。该硬件加速器能够维持超过 160 Gbps 的数据包处理速率。

本文的其余部分组织如下：第 2 节回顾了滑动窗口熵估计算法的相关工作；第 3 节介绍了所提出的算法；第 4 节描述了加速器架构；第 5 节评估了算法和加速器的实现；最后，第 6 节总结了本文并展望了未来的工作。

相关研究

相关工作

Assaf 等人[22]提出了滑动窗口近似测量协议（Sliding Window Approximate Measurement Protocol, SWAMP），用于估计网络数据流中的每个流量的计数、基数和熵。SWAMP 使用哈希函数将流量 ID 转换为固定长度的哈希值（即指纹）。该方法将指纹存储在循环缓冲窗口中，并使用指针指示当前插入点的位置。当新数据到达时，窗口中最旧的指纹会被替换。

方法

在本节中，我们描述了滑动窗口模型，定义了标准化的经验香农熵，并介绍了基于我们之前方法[21]的改进版本。然后，我们描述了支持我们方法的算法和数据结构。

加速器架构

用于滑动时间窗口的 FPGA 基熵估计加速器的架构如图 3 所示。它包括两个模块：滑动窗口数据包处理（sliding window packet processing），实现算法 1 来估计前$K$个流量频率、流量基数和数据包计数；以及熵估计（entropy estimation），根据这些结果计算熵。本节的其余部分详细介绍了每个模块。

结果

在本节中，我们评估了所提出方法的性能以及第 3.3、3.4 和 4 节中描述的硬件加速器的实现。我们使用了 MawiLab 公开数据集[51]中的八个数据集，每个数据集的持续时间约为 900 秒。使用大小为$W=60$的滑动窗口和$s=6$的步长来估计所有数据集的熵。经验观察表明，在每个$s$秒的时间间隔内，流量的基数平均为

结论

本研究提出了一种算法和 FPGA 加速器，用于估计具有离散滑动步骤的滑动时间窗口中网络流的经验熵。与仅限于静态窗口或具有高内存开销的先前方法不同，我们的方法结合了循环 Sketch 和优先队列数组（PQAs），在较低的内存需求下实现了高精度。该算法直接估计前个流量频率，其余流量通过在对数-对数缩放直方图中的线性函数进行拟合。

CRediT 作者贡献声明

雅伊梅·费尔南德斯（Yaime Fernández）：撰写——原始草稿、可视化、验证、项目管理、方法论、调查、形式分析、概念化。哈维尔·E·索托（Javier E. Soto）：验证、监督、软件开发、调查、形式分析。卡罗莱纳·加利亚多-帕维斯（Carolina Gallardo-Pavesi）：可视化、验证、软件开发。亚斯曼尼·普里托（Yasmany Prieto）：概念化、形式分析、验证、撰写——审稿与编辑。塞西莉亚·埃尔南德斯（Cecilia Hernández）：撰写——审稿与编辑、监督、方法论、调查、资金支持

写作过程中生成式 AI 和 AI 辅助技术的声明

在准备本工作时，作者使用了 ChatGPT、Writefull 和 Grammarly 工具来检查语法一致性、优化句子格式以及用 LaTeX 格式化表格和算法。使用这些工具后，作者根据需要对内容进行了审查和编辑，并对发表文章的内容负全责。

利益冲突声明

作者声明没有已知的财务利益或个人关系可能影响本文所述的工作。

致谢

本研究由智利国家研究与发展机构（ANID）通过 Fondecyt 资助（项目编号 11240971 和 11240147）、应用研究中心（CIA250006）、特定主题研究团队项目（ATE250003）以及研究生奖学金（21191612 和 22231033）提供支持。