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

  • Article
  • | |
  • Metrics
  • |
  • Reference [18]
  • |
  • Related [20]
  • | | |
  • Comments
    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.

    Reference
    [1] Liu YP, Gong ZH, Zhu PD. Research on the bottleneck area of optimal BGP route selection. Journal of Software, 2005,16(5): 946-959 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/16/946.htm
    [2] Wang H, Gong ZH, Guan Q, Wang BS. Detection network anomalies based on packet and flow analysis. In: Bi J, Gyires T, eds. Proc. of the 7th Int’l Conf. on Networking. Cancun: IEEE Computer Society, 2008. 497-502.
    [3] Agrawal S, Naidu KVM, Rastogi R. Diagnosing link-level anomalies using passive probes. In: Proc. of the IEEE INFOCOM. 2007. http://www.stanford.edu/~shipra/Publications/anomaly.pdf
    [4] Estan C, Varghese G, Fisk M. Bitmap algorithms for counting active flows on high speed links. In: Proc. of the 3rd ACM SIGCOMM Conf. on Internet. 2003. http://woozle.org/~mfisk/papers/countingdistinct.pdf
    [5] Yang LL, Michailidis G. Sampled based estimation of network traffic flow characteristics. In: Proc. of the IEEE INFOCOM 2007. http://www.stat.lsa.umich.edu/~gmichail/infocom_07.pdf
    [6] Krishnamurthy B, Sen S. Sketch-Based change detection: Methods, evaluation, and applications. In: Proc. of the ACM SIGCOMM. 2003. http://www.imconf.net/imc-2003/papers/p305-krishnamurthy11111.pdf
    [7] Duffield N, Lund C, Thorup M. Estimating flow distributions from sampled flow statistics. In: Proc. of the ACM SIGCOMM. 2003. http://www.research.att.com/~duffield/papers/DLT03-lengths.pdf
    [8] Fang W, Peterson L. Inter-As traffic patterns and their implications. In: Proc. of the IEEE GLOBECOM. 1999. http://www.nlanr. net/Papers/inter-AS.pdf
    [9] Estan C, Varghese G. New directions in traffic measurement and accounting. In: Proc. of the ACM SIGCOMM. 2002. http://conferences.sigcomm.org/sigcomm/2002/papers/traffmeas.pdf
    [10] Huang L, Nguyen XL, Garofalakis M, Hellerstein J. Communication-Efficient online detection of network-wide anomalies. In: Proc. of the IEEE INFOCOM. 2007. http://bnrg.cs.berkeley.edu/~adj/publications/paper-files/pca_infocom2007.pdf
    [11] Jin CQ, Qian WN, Zhou AY. Analysis and management of streaming data: A survey. Journal of Software, 2004,15(8):1172-1181 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/15/1172.htm
    [12] Baiocchi A, Vacirca F. TCP fluid modeling with a variable capacity bottleneck link. In: Proc. of the IEEE INFOCOM. 2007. http://infocom.uniroma1.it/~vacirca/papers/vacirca/infocom07.pdf
    [13] Chen AY, Cao J, Bu T. Network tomography: Identifiability and fourier domain estimation. In: Proc. of the IEEE INFOCOM. 2007. http://arxiv.org/pdf/0712.3618
    [14] Charikar M, Chen K, Farach-Colton M. Finding frequent items in data streams. In: Proc. of the Symp. on Principles of Database System. 2002. http://www.cs.rutgers.edu/~farach/pubs/FrequentStream.pdf
    [15] Cormode G, Muthukrishnan S. What’s new: Finding significant differences in network data streams. In: Proc. of the IEEE INFOCOM. 2004. http://www.cs.rutgers.edu/~muthu/676879419.pdf
    [16] National Laboratory for Applied Network Research. http://www.nlanr.net
    附中文参考文献: [1] 刘亚萍,龚正虎,朱培栋.BGP最优路径选择中的瓶颈区域的研究.软件学报,2004,15(8):946-959. http://www.jos.org.cn/1000- 9825/15/946.htm
    [11] 金澈清,钱卫宁,周傲英.流数据分析与管理综述.软件学报, 2004,15(8):1172-1181. http://www.jos.org.cn/1000-9825/15/1172.htm
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:5915
  • PDF: 9449
  • HTML: 0
  • Cited by: 0
History
  • Received:August 14,2008
  • Revised:October 27,2008
You are the first2051310Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063