Author Login Chief Editor Login Reviewer Login Editor Login Remote Office

Computer Engineering ›› 2026, Vol. 52 ›› Issue (10): 429-441. doi: 10.19678/j.issn.1000-3428.0252087

• Next-Generation Networks and Edge Computing • Previous Articles     Next Articles

IntervalSketch: A Multi-Dimensional Sketch Algorithm for Heavy Flow Detection Integrating Packet Intervals

LIN Shu, HUANG Jiawei*(), SHAO Jing, LI Sitan, LIANG Qi, WANG Qile, ZHAO Yilin   

  1. School of Computer Science and Engineering, Central South University, Changsha 410083, Hunan, China
  • Received:2025-01-24 Revised:2025-03-26 Online:2026-10-15 Published:2025-05-14
  • Contact: HUANG Jiawei

间隔值草图: 融合数据包间隔的多维度大流检测草图算法

林澍, 黄家玮*(), 邵婧, 李思覃, 梁琦, 王启乐, 赵艺琳   

  1. 中南大学计算机学院, 湖南 长沙 410083
  • 通讯作者: 黄家玮
  • 作者简介:

    林澍, 男, 硕士研究生, 主研方向为计算机网络、网络测量草图算法

    黄家玮(通信作者), 教授、博士

    邵婧, 硕士研究生

    李思覃, 硕士研究生

    梁琦, 硕士研究生

    王启乐, 硕士研究生

    赵艺琳, 硕士研究生

  • 基金资助:
    国家自然科学基金重点项目(62132022); 国家自然科学基金青年科学基金项目(62302524)

Abstract:

In the fields of network communication and traffic management, rapid and accurate identification of heavy flows is of great significance for tasks such as traffic congestion control and malicious traffic monitoring. However, extremely high data transmission rates in real-world network environments render heavy flow detection exceptionally complex and challenging. Most existing heavy flow detection methods rely primarily on single-dimensional statistical data; typically, these methods obtain traffic statistics and perform analyses based solely on estimated flow packet counts. The limitation of such an approach lies in its neglect of critical information from other potential dimensions, such as the distribution characteristics of packet inter-arrival times, which may be crucial in accurately identifying heavy flows. To address these issues, this paper proposes a heavy flow detection algorithm called IntervalSketch. By incorporating two-dimensional traffic features—the estimated flow size and packet interarrival time distribution—the algorithm optimizes the protection of heavy flows and the replacement strategy for mouse flows. Specifically, IntervalSketch effectively distinguishes heavy flows from mouse flows by leveraging packet inter-arrival time characteristics, thereby significantly improving the detection performance under low-memory conditions. To validate the accuracy and effectiveness of IntervalSketch, two real-world network traffic datasets, CAIDA and MAWI, are used. The experimental results demonstrate that IntervalSketch exhibits significant advantages across various memory configurations and traffic distributions. Compared with existing methods, it maintains a higher detection accuracy under memory-constrained conditions, achieving an F1 value up to 2.4 times that of state-of-the-art approaches.

Key words: sketch algorithm, heavy flow detection, network measurement, network communication, accuracy, packet interval

摘要:

在网络通信、网络流量管理等领域, 快速、准确地识别大流对流量拥塞控制、恶意流量监测等任务具有重要意义。然而, 现实网络环境中的数据流传输速率极高, 使得大流检测变得异常复杂和具有挑战性。现有大多数大流检测方法主要依赖单一维度的统计数据, 通常仅基于流中数据包的估计值进行流量统计与分析。这种方式的局限性在于其忽略了其他潜在维度的关键信息, 如数据包间隔的分布特性, 这些信息在准确识别大流时可能起到关键作用。针对上述问题, 提出一种名为间隔值草图的大流检测算法。该算法通过引入流的估计值大小和数据包间隔分布特性这2个维度的流量特征, 优化大流的保护与小流的替换策略。具体地, 间隔值草图通过结合数据包间隔特性, 有效区分大流与小流, 从而在低内存条件下显著提升检测性能。为验证间隔值草图的准确性和有效性, 采用CAIDA和MAWI两个真实网络流量数据集进行分析。实验结果表明, 间隔值草图在多种内存设置和流量分布下均表现出显著优势, 与现有方法相比, 间隔值草图能够在内存资源受限的情况下保持较高的检测精度, F1值最高可达到现有方法的2.4倍。

关键词: 草图算法, 大流检测, 网络测量, 网络通信, 准确性, 数据包间隔