中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
  4. 中国科学院计算技术研究所期刊论文
  5. 英文
Identifying heavy hitters in high-speed network monitoring

文献类型：期刊论文

作者Zhang Yu1; Fang BinXing1,2; Zhang YongZheng2
刊名SCIENCE CHINA-INFORMATION SCIENCES
出版日期2010-03-01
卷号53期号:3页码:659-676
关键词network traffic monitoring heavy hitter weighted data streams
ISSN号1674-733X
DOI10.1007/s11432-010-0053-5
英文摘要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.
资助项目National Natural Science Foundation of China[60703021] ; National High-Tech Research & Development Program of China[2007AA010501] ; National High-Tech Research & Development Program of China[2007AA01Z444] ; National High-Tech Research & Development Program of China[2007AA01Z406] ; National High-Tech Research & Development Program of China[2007AA01Z442] ; National High-Tech Research & Development Program of China[2009AA01Z437] ; National Basic Research Program of China[2007CB311100]
WOS研究方向Computer Science
语种英语
WOS记录号WOS:000276599800020
出版者SCIENCE PRESS
源URL[http://119.78.100.204/handle/2XEOYT63/12459]  
专题中国科学院计算技术研究所期刊论文_英文
通讯作者Zhang Yu
作者单位1.Harbin Inst Technol, Res Ctr Comp Network & Informat Secur Technol, Harbin 150001, Peoples R China
2.Chinese Acad Sci, Inst Comp Technol, Res Ctr Informat Secur, Beijing 100190, Peoples R China
推荐引用方式
GB/T 7714		 Zhang Yu,Fang BinXing,Zhang YongZheng. Identifying heavy hitters in high-speed network monitoring[J]. SCIENCE CHINA-INFORMATION SCIENCES,2010,53(3):659-676.
APA Zhang Yu,Fang BinXing,&Zhang YongZheng.(2010).Identifying heavy hitters in high-speed network monitoring.SCIENCE CHINA-INFORMATION SCIENCES,53(3),659-676.
MLA Zhang Yu,et al."Identifying heavy hitters in high-speed network monitoring".SCIENCE CHINA-INFORMATION SCIENCES 53.3(2010):659-676.

入库方式： OAI收割

来源：计算技术研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。