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.

关键词： heavy hitters data streaming counting adaptive sampling

作者: Zhen Li Yahui Yang Guangxing Zhang Guangcheng Qin

作者单位: School of Software and Microelectronions, Peking University Institute of Computing Technology, Chine School of Software and Microelectronions, Peking University Institute of Computing Technology, Chinese Academy Sciences Communication Center, the 61 st Research Institute of General Staff

会议类型: 国际会议

会议名称: 2010 3rd International Conference on Advanced Computer Theory and Engineering(2010年第三届先进计算机理论与工程国际会议 ICACTE 2010)

会议地点: 成都

会议语种:英文

页码: 1-5

在线出版日期: 2010-08-20（万方平台首次上网日期，不代表论文的发表时间）