Optimal Elephant Flow Detection

2017/01/15 by Ran Ben Basat, Basat, Ran Ben, Gil Einziger +5 · 1 citation
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Internet Traffic Analysis and Secure E-voting #Network Security and Intrusion Detection #Network Traffic and Congestion Control

paper · pdf · doi:10.48550/arxiv.1701.04021

openalex publication_date 2017/01/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Monitoring the traffic volumes of elephant flows, including the total byte count per flow, is a fundamental capability for online network measurements. We present an asymptotically optimal algorithm for solving this problem in terms of both space and time complexity. This improves on previous approaches, which can only count the number of packets in constant time. We evaluate our work on real packet traces, demonstrating an up to X2.5 speedup compared to the best alternative.

Cited by

• Improving Slow Transfer Predictions: Generative Methods Compared

Related

• High Speed Elephant Flow Detection Under Partial Information
• Detailed Network Measurements Using Sparse Graph Counters: The Theory
• Adaptive algorithms for identifying large flows in IP traffic
• Fast Flow Volume Estimation
• Cross-Domain Elephant Flow Detection: A Unified Machine Learning Approach with Application-Aware and Security Features