An adaptive method for identifying heavy hitters combining sampling and data streaming counting

Identifying heavy hitters is essential for network monitoring, management, charging and etc. Existing methods in the literature have some limitations. How to reduce the memory consumption effectively without compromising identification accuracy is still challenging. In this paper, an adaptive method combining sampling and data streaming counting is proposed, called FSPLC(feedback sampling probabilistic lossy counting). Based on the history information in the flow counter table, FSPLC can adjust the sampling frequency dynamically, and also adapt to the real-time traffic changes. Comparison with state-of-the-art algorithms based on real Internet traces suggests that FSPLC is remarkably efficient and accurate. Experiment results show that FSPLC has 1) 60% lower memory consumption, 2) 15% smaller false-positive ratio. ? 2010 IEEE.EI