Sketch-Based Heavy-Hitter Detection for High-Rate Network Telemetry with Adaptive Precision Allocation

• Andi Saputra

  Universitas Negeri Makassar, Jalan Daeng Tata Raya, Makassar 90222, Indonesia

  Author

• Fajar Santoso

  Universitas Jenderal Achmad Yani Yogyakarta, Jalan Ringroad Barat, Sleman 55292, Indonesia

  Author

High-rate network telemetry increasingly relies on streaming analytics that must operate under tight memory, latency, and power constraints while observing traffic whose statistical structure can shift rapidly. Heavy-hitter detection is a canonical task in this setting because it supports congestion localization, anomaly detection, capacity planning, and security monitoring, yet it is difficult to perform exactly when per-packet processing budgets are measured in a handful of nanoseconds and per-device memory is limited. Sketch-based algorithms provide an attractive alternative by offering approximate frequency estimates with probabilistic error guarantees and mergeability across devices, but practical deployments face an additional challenge: a fixed-precision sketch over-allocates resources to low-impact traffic while under-allocating to the few flows that dominate volume. This paper studies sketch-based heavy-hitter detection for high-rate telemetry with adaptive precision allocation, where memory, counter resolution, and update effort are redistributed online toward likely heavy contributors. The approach combines a coarse, fast path that maintains candidate evidence with a refinement path that selectively increases measurement precision for uncertain or high-value flows. A principled optimization model is developed to trade accuracy against resource budgets under heavy-tailed traffic, including multi-objective formulations for latency, energy, and memory. Error analyses link adaptive decisions to false positive and false negative rates, and system design considerations address pipeline constraints, hash design, merge protocols, and reproducibility. The resulting framework aims to maintain stable heavy-hitter recall under rapid workload shifts without requiring static overprovisioning.

• PDF