用于层次化关键节点检测的节省内存且对硬件要求较低的算法

《IEEE Transactions on Network and Service Management》：Memory-Efficient and Hardware-Friendly Sketches for Hierarchical Heavy Hitter Detection

检测网络流高频项的新方法HHD和CHHD在内存效率与硬件兼容性上取得突破。摘要：提出HHD和CHHD两种层次高频项检测方案，通过共享桶数组与紧凑单元结构提升内存效率，采用抽样更新策略平衡处理速度与检测精度，在可编程交换机上实现56%精度提升和2.6倍吞吐量增益。

　　

摘要：

识别层次化重要流量（HHHs），即基于常见IP前缀的频繁聚合流量，是网络流量测量和安全领域中的关键任务。现有方法通常采用动态 trie 结构来跟踪大量前缀，或为每个层次级别使用多个独立的检测实例来捕捉不同层次级别的 HHHs，但这两种方法都存在内存效率低和与可编程交换机兼容性有限的缺点。在本文中，我们提出了两种新颖的 HHH 检测方案：层次化重要流量检测器（HHD）和压缩层次化重要流量检测器（CHHD），以实现更高的内存效率和更好的硬件兼容性。HHD 的核心思想是设计一个共享的桶数组结构，用于识别和记录所有层次级别的 HHHs，从而避免了维护独立检测实例所带来的内存浪费，提高了内存效率，并使得在可编程交换机上实现字节层次和位层次 HHH 检测成为可能，且所需处理资源极少。此外，HHD 运用了基于采样的更新策略，有效平衡了数据包处理速度和检测精度。我们还介绍了 CHHD，它通过更紧凑的单元结构增强了位层次中的 HHH 检测能力，允许在一个单元内压缩多个祖先和后代前缀，进一步提高了内存效率和检测精度。我们在资源有限的基于 P4 的可编程交换机上实现了 HHD 和 CHHD。基于真实互联网流量的实验结果表明，HHD 和 CHHD 的检测精度比现有技术高出多达 56%，吞吐量提高了 2.6 倍。