Identifying heavy hitters in high-speed network monitoring

查看全文 作　　者：ZHANG [1]Yu;FANG [1,2]BinXing;ZHANG [2]YongZheng

机构地区：[1]Research Center of Computer Network and Information Security Technology, Harbin Institute of Technology, Harbin 150001, China;[2]Research Center of Information Security, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China

出　　处：《Science China(Information Sciences)》索引2010年第53卷第3期,共18页

基　　金：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) 摘　　要：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. 关键词：网络监控无线网路识别精度计算算法内存空间平均相对误差更新速度更新时间

相关文献

参考文献（30）
引证文献（9）
耦合文献（117）

参考文献(30)

引证文献(9)

耦合文献(117)

互联网出版许可证新出网证(渝)字10号全国400电话 - 免长途话费

Identifying heavy hitters in high-speed network monitoring

参考文献(30)

引证文献(9)

耦合文献(117)

用户提示