期刊文献+

一种高效率的大流提取方法 被引量:10

A Method of Extracting Heavy-Hitter Flows Efficiently
下载PDF
导出
摘要 随着网络带宽的不断提高,在线识别大流对于拥塞控制、异常检测等网络应用具有重要意义.提出了一种提取大流的算法FEFS(flow extracting with frequency & size),能够通过在线识别和淘汰小流,把大流信息保存在有限的高速存储空间中,从而快速提取大流.该算法利用LRU(least recently used)定位更新频率低的流,并进一步用流尺寸因子s和自适应调节因子M标记其中相对较小的流,最后用新到达的流将其替换.FEFS把LRU策略和尺寸因子s相结合,同时考虑了流的近期更新频率和累积报文数量,因此能够准确在线识别大流.LRU策略和尺寸因子都利用了流大小的重尾分布特征,因此FEFS能以很低的存储代价保存和更新大流信息.模拟实验表明,在限定存储条件下,FEFS的平均相对误差率明显低于经典的multi-stage filter算法,而平均报文处理时间也短于multi-stage filter算法. Along with the continuous improvement of network bandwidth, identifying heavy-hitter flows on-line is more significant for some network application, such as congestion controlling, anomaly detecting and so on. A novel algorithm FEFS (flow extracting by frequency & size) is proposed to extract heavy-hitter flows online. Through online identification and elimination of small flows, the information of heavy-hitter flows is stored and updated in the limited high-speed memory, so heavy-hitter flows can be extracted rapidly and accurately. FEFS locates the flows with low update frequency using LRU (least recently used) mechanism, and furthermore it labels the relatively small flows in storage space with a flow size factor s and an adaptive modulating factor M. Taking into account both the recent update frequency and the cumulative number of packets, FEFS can identify heavy-hitter flows precisely online. Both LRU policy and size factors have taken advantage of the heavy-tail distribution characteristics of flow size, and therefore heavy-hitter flows can be handled with very low computing and storage costs. The simulation results show that in the limited storage conditions, average relative error rate of FEFS is significantly lower than that of the classic multistage filter algorithm, while the average packet processing time is also shorter than that of the multistage filter algorithm.
出处 《计算机研究与发展》 EI CSCD 北大核心 2013年第4期731-740,共10页 Journal of Computer Research and Development
基金 国家自然科学基金项目(60803142) 山东省优秀中青年科学家科研奖励基金项目(BS2009DX018) 山东省自然科学基金项目(2009ZRB019ON)
关键词 网络测量 大流 替换机制 LRU 尺寸因子 network measurement heavy-hitter flow replacement mechanism LRU size factor
  • 相关文献

参考文献22

  • 1Sommer R, Feldmann A. NetFlow: Information loss or win? [C] //Proe of the 2nd ACM SIGCOMM Workshop on Internet Measurement. New York: ACM, 2002: 173-174.
  • 2Fred S, Bonald T, Proutiere A, et al. Statistical bandwidth sharing: A study of congestion at low level [J]. ACM SIGCOMM Computer Communication Review, 2001, 31(4) 111-122.
  • 3Mori T, Kawahara S, Naito S, et al. On the characteristics of Internet traffic variability: Spikes and elephants[C]//Proc of the 2004 Int Symp on Applications and the Internet. I.os Alamitos, CA: IEEE Computer Society, 2004:99-106.
  • 4Xu K, Zhang Z L, Bhattacharyya S. Profiling Internet backbone traffic: Behavior models and applications [J]. ACM SIGC()MM Computer Communication Review, 2005, 35(4): I69-180.
  • 5Fang W, Peterson L. Inter-as traffic patterns and their implications [C] //Proc of IEEE GL()BEC()M' 99. New York: IEEE Con'tmunications Society, 1999:1859-1868.
  • 6Estan C, Varghese G. New directions in traffic measurement and accounting: Focusing on elephants, ignoring the mice [J] ACM Transon Computer Systems, 2003, 21(3): 270- 313.
  • 7'Cisco. Cisco NetFlow [OL]. [2010-10-21]. http: //www. cisco, com/en/US/products/ps6601/products_ ios_ protocol_ group_home, html.
  • 8Estan C, Keys K. Moore D. et al. Building a better NetFIow[J]. ACM SIGCOMM Computer Communication Review, 2004, 34(4): 245-256.
  • 9Paxson V, Almes G, Mabdavi J, et al. Framework for IP performance metrics [S/OL]. RFU 2330. Fremont, CA: IETF, 1998[2010-11-02]. http: //www. rfc-editor, org/rfc/ rfc2330, txt.
  • 10Duffield N, l.und C, Thorup M, Flow sampling under hard resource constraints [J] ACM SIGMETRICS Performance Valualion Review, 2004, 32(1): 85-96.

二级参考文献35

  • 1龚俭,彭艳兵,杨望,刘卫江.基于BloomFilter的大规模异常TCP连接参数再现方法[J].软件学报,2006,17(3):434-444. 被引量:24
  • 2潘云鹤,王金龙,徐从富.数据流频繁模式挖掘研究进展[J].自动化学报,2006,32(4):594-602. 被引量:34
  • 3王洪波,韦安明,林宇,程时端.流测量中基于测量缓冲区的时间分层分组抽样[J].软件学报,2006,17(8):1775-1784. 被引量:14
  • 4王伟平,李建中,张冬冬,郭龙江.一种有效的挖掘数据流近似频繁项算法[J].软件学报,2007,18(4):884-892. 被引量:33
  • 5N Brownlee,C Mills,and G Ruth. Traffic Flow Measurement: Architecture[ S]. IETF RFC 2722,1999.
  • 6W Fang and L Peterson. Inter-AS traffic patterns and their implications[ A]. In Proceedings of IEEE GLOBECOM[ C ]. New York: IEEE, 1999. 1859 - 1868.
  • 7C Estan and G Varghese. New directions in traffic rneasurement and accounting[ A]. In Proceedings of ACM SIGCOMM[ C]. New York:ACM,2002.323- 336.
  • 8Sampled Netflow[ OL ]. http://www. cisco. com/en/US/ docs/ios/12 _ 0s/feature/guide/12s _ sanf. html.
  • 9A Feldmann, A Greenberg, C Lund, N Reingold, J Rexford, and F True. Deriving traffic demands for operational IP networks: methodology and experience[ J]. IEEE/ACM Transactions on Networking, 2001.9(3) :265 - 280.
  • 10Y Zhang,L Breslau,V Paxson, and S Shenker. On the characteristics and origins of intemet flow rates[ A]. In Proceedings of the 2002 conference on Applications, Technologies, Architectures,and Protocols for Computer Communications [ C ]. New York: ACM,2002.309 - 322.

共引文献88

同被引文献141

引证文献10

二级引证文献19

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部