Probabilistic fading counting: An efficient identification method for finding heavy hitters

Identifying heavy hitter flows in the network is of tremendous importance for many network management activities. The problem of how to find these flows has been the concern of many studies in the past few years. Lossy counting [12] and probabilistic lossy counting [11] are among the most well-known algorithms for finding heavy hitters. But these methods have some limitations. The challenge is finding a way to reduce the memory consumption effectively while achieving better accuracy. In this work, we introduce a probabilistic fading method combined with data streaming counting, which is called probabilistic fading lossy counting (PFC). This method absorbs the advantages of data streaming counting, and it manages to find the heavy-hitter by analyzing the power-low characteristic in the network flow. Comparisons with lossy counting and probabilistic lossy counting base on real Internet traces suggest that PFC is remarkably efficient and more accurate. Particularly, experiment results show that PFC has 60% lower memory consumption without increasing the false negative ratio nor the false positive ratio. ? 2010 IEEE.EI