Probabilistic Lossy Counting: An Efficient Algorithm for Finding Heavy-hitters

Knowledge of the largest traffic flows in a network is im-portant for many network management applications. The problem of finding these flows is known as the heavy-hitter problem and has been the subject of many studies in the past years. One of the most efficient and well-known algo-rithms for finding heavy hitters is lossy counting [29]. In this work we introduce probabilistic lossy counting (PLC), which enhances lossy counting in computing network traf-fic heavy hitters. PLC uses on a tighter error bound on the estimated sizes of traffic flows and provides probabilistic rather than deterministic guarantees on its accuracy. The probabilistic-based error bound substantially improves the memory consumption of the algorithm. In addition, PLC reduces the rate of false positives of lossy counting and achieves a low estimation error, although slightly higher than that of lossy counting. We compare PLC with state-of-the-art algorithms for find-ing heavy hitters. Our experiments using real traffic traces find that PLC has 1) between 34.4 % and 74 % lower memory consumption, 2) between 37.9 % and 40.5 % fewer false posi-tives than lossy counting, and 3) a small estimation error