Identifying heavy hitters in high-speed network monitoring

doi:10.1007/s11432-010-0053-5

	Identifying heavy hitters in high-speed network monitoring
	Zhang Yu 1; Fang BinXing 1,2; Zhang YongZheng 2
	2010-03-01
发表期刊	SCIENCE CHINA-INFORMATION SCIENCES
ISSN	1674-733X
卷号	53 期号:3 页码:659-676
摘要	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.
关键词	network traffic monitoring heavy hitter weighted data streams
DOI	10.1007/s11432-010-0053-5
收录类别	SCI
语种	英语
资助项目	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类目	Computer Science, Information Systems
WOS记录号	WOS:000276599800020
出版者	SCIENCE PRESS
引用统计	被引频次：10[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/12460
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	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.