Identifying heavy hitters in high-speed network monitoring

作     者：ZHANG Yu1, FANG BinXing1,2 & ZHANG YongZheng2 1Research Center of Computer Network and Information Security Technology, Harbin Institute of Technology, Harbin 150001, China 2Research Center of Information Security, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China 

作者机构：Research Center of Computer Network and Information Security Technology Harbin Institute of Technology Harbin China Research Center of Information Security Institute of Computing Technology Chinese Academy of Sciences Beijing China 

出 版 物：《Science China(Information Sciences)》 (中国科学:信息科学(英文版))

年 卷 期：2010年第53卷第3期

页      面：659-676页

核心收录：

学科分类：11[军事学] 0810[工学-信息与通信工程] 1105[军事学-军队指挥学] 0808[工学-电气工程] 0839[工学-网络空间安全] 08[工学] 110505[军事学-密码学] 110503[军事学-军事通信学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：supported by the National Natural Science Foundation of China (Grant No. 60703021) the National High-Tech Research & Development Program of China (Grant Nos. 2007AA010501, 2007AA01Z444,2007AA01Z406, 2007AA01Z442, 2009AA01Z437) the National Basic Research Program of China (Grant No.2007CB311100) 

主　　题：network traffic monitoring heavy hitter weighted data streams 

摘      要：Identifying heavy hitters in a network traffic stream is important for a variety of network applications ranging from traffic engineering to anomaly detection such as detection of denial-of-service attacks. Existing methods generally examine newly arriving items in the stream, perform a small number of operations using a small amount of memory, and still provide guarantees on the identifying accuracy. In high-speed network monitoring, the update speed per item is extremely critical. However, so far as we know, there are no identifying algorithms which can provide constant update time (O(1)) in a weighted data stream. In this paper, we present an algorithm named Weighted Lossy Counting (WLC) which is able to identify heavy hitters in a high-speed weighted data stream with constant update time. WLC employs a novel efficient partially ordered data structure which is able to provide a fast per-item update speed while keeping the memory cost relatively low. We compare WLC with state-of-the-art algorithms for finding heavy hitters in real traffic traces. The experimental results show that WLC performs well in accuracy (recall, precision and average relative error) as other algorithms; moreover it has a much higher update speed at the cost of relatively larger memory space used. A theoretical worst-case memory bound of WLC is also derived in this paper; however, experiments with long real traffic traces show that WLC requires much less space than the theoretical bound in practice.