Parallelizing weighted frequency counting in high-speed network monitoring

doi:10.1016/j.comcom.2010.04.026

	Parallelizing weighted frequency counting in high-speed network monitoring
	Zhang, Yu 1,2; Fang, Binxing 1,2; Zhang, Yongzheng 1
	2011-04-01
发表期刊	COMPUTER COMMUNICATIONS
ISSN	0140-3664
卷号	34 期号:4 页码:536-547
摘要	Identifying frequent items in high-speed network is important for a variety of network applications ranging from traffic engineering to anomaly detection such as detection of denial of service attacks. To deal with high packet arrival rate, it is desirable that such systems are able to support very high update throughput. The advent of multi-core processors calls for efficient parallel designs which can effectively utilize the parallelism of the multi-cores. In this paper, we address the problem of parallelizing weighted frequency counting in the context of multi-core processors. We discuss the challenges in designing an efficient parallel system. Our evaluation and analysis reveals that the naive fine-grained lock design results in excessive overhead and wait, which in turn leads to severe performance degradation in multi-core architectures. Based on our analysis, we propose a novel method: precision integrated method (PRIM). PRIM makes use of the temporal imprecision concept to significantly reduce the merge overhead at the cost of relatively large memory space used. Both the theoretical analysis and real traffic experiments demonstrate that PRIM delivers almost linear speedup. (C) 2010 Elsevier B.V. All rights reserved.
关键词	Traffic monitoring Parallel algorithms Data streams Weighted frequency counting Frequent items
DOI	10.1016/j.comcom.2010.04.026
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[60703021] ; National High-Tech Development 863 Program of China[2007AA010501] ; National High-Tech Development 863 Program of China[2007AA01Z444] ; National High-Tech Development 863 Program of China[2007AA01Z442] ; National High-Tech Development 863 Program of China[2009AA01Z437] ; National Basic Research Program of China[2007CB311100]
WOS研究方向	Computer Science ; Engineering ; Telecommunications
WOS类目	Computer Science, Information Systems ; Engineering, Electrical & Electronic ; Telecommunications
WOS记录号	WOS:000287633600003
出版者	ELSEVIER SCIENCE BV
引用统计	被引频次：5[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/12962
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Zhang, Yu
作者单位	1.Chinese Acad Sci, Inst Comp Technol, Beijing 100190, Peoples R China 2.Harbin Inst Technol, Sch Comp Sci & Technol, Harbin 150001, Peoples R China
推荐引用方式 GB/T 7714	Zhang, Yu,Fang, Binxing,Zhang, Yongzheng. Parallelizing weighted frequency counting in high-speed network monitoring[J]. COMPUTER COMMUNICATIONS,2011,34(4):536-547.
APA	Zhang, Yu,Fang, Binxing,&Zhang, Yongzheng.(2011).Parallelizing weighted frequency counting in high-speed network monitoring.COMPUTER COMMUNICATIONS,34(4),536-547.
MLA	Zhang, Yu,et al."Parallelizing weighted frequency counting in high-speed network monitoring".COMPUTER COMMUNICATIONS 34.4(2011):536-547.