Hits和Holds:识别大象流的两种算法
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

Supported by the National Natural Science Foundation of China under Grant No.90604006 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2008AA01A325 (国家高技术研究发展计划(863)); the National Basic Research Program of China under Grant Nos.2003CB314802, 2009CB320503 (国家重点基础研究发展计划(973))


Hits and Holds: Two Algorithms for Identifying the Elephant Flows
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    随着网络规模的扩大和链路速度的提高,实时采集每条流的流量变得非常困难.Estan等人提出采集大象流的设想,并提出了识别大象流的算法:Sample and Hold算法和Multistage算法.但这两种算法在实现时存在: Sample and Hold算法随机丢弃报文,带来采集数据不准确的问题;Multistage算法需要同时进行5~6次访存,无法使用硬件实现的问题.针对上述问题,提出了两种大象流识别算法:Hits和Holds算法.理论和实验结果表明,Hits和Holds算法对网络大象流的误检率和漏检率均优于Sample and Hold及Multistage算法.

    Abstract:

    As networks expanded largely and link speeds grow rapidly, keeping a counter for each flow is too expensive. Estan et al. propose two algorithms: sample and hold and multistage filters, to identify large flows, which have obvious shortcomings: sample and hold discard packets randomly while multistage filters simultaneously calculate 5~6 hash functions that is unsuitable for hardware implementation. This paper proposes two algorithms, Hits and Holds, to identify large flows quickly and correctly, which overcome the shortcomings of Estan’s algorithms, while effectively reducing false positive and false negative errors.

    参考文献
    相似文献
    引证文献
引用本文

王 宏,龚正虎. Hits和Holds:识别大象流的两种算法.软件学报,2010,21(6):1391-1403

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2008-08-14
  • 最后修改日期:2008-10-27
  • 录用日期:
  • 在线发布日期:
  • 出版日期:
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号