Sketch‐BF: A fast algorithm for finding top‐k flows

Finding top‐k flows plays an essential role for many network managements. Since the line rates keep increasing in networks, finding top‐k flows precisely and quickly becomes more challenging. Existing algorithms for top‐k finding can achieve high precision suffering from slow speed. In this paper, the authors propose Sketch‐BF, which is a novel top‐k finding solution that is much faster than existing algorithms while ensuring high precision. The core idea is to add a bloom filter variant between sketch and heap to accelerate by significantly reducing the min‐heap update. The authors’ experimental results show that, while maintaining precision, Sketch‐BF has about two to five times higher insertion speed compared with the state‐of‐the‐art.