J4 ›› 2015, Vol. 42 ›› Issue (5): 125-132.doi: 10.3969/j.issn.1001-2400.2015.05.022

• 研究论文 • 上一篇    下一篇

网络数据流流量测量新方法

任高明;夏靖波;柏骏;陈珍   

  1. (空军工程大学 信息与导航学院，陕西 西安  710077)
  • 收稿日期:2014-05-07 出版日期:2015-10-20 发布日期:2015-12-03
  • 通讯作者: 任高明
  • 作者简介:任高明(1986-)，男，空军工程大学博士研究生，E-mail: gaomingren_928@126.com．
  • 基金资助:

    国家自然科学基金资助项目(61202489)；陕西省自然科学基础研究计划资助项目(2012JZ8005)

Novel per-flow traffic measurement algorithm

REN Gaoming;XIA Jingbo;BAI Jun;CHEN Zhen   

  1. (School of Information and Navigation, Air Force Engineering University, Xi'an  710077, China)
  • Received:2014-05-07 Online:2015-10-20 Published:2015-12-03
  • Contact: REN Gaoming
  • About author:［1］ Huici F, Di Pietro A, Trammell B, et al. Blockmon: a High-performance Composable Network Traffic Measurement System［J］. Computer Communication Review, 2012, 42(4): 79-80. ［2］ Kodialam M S, Lakshman T V. High-speed Traffic Measurement and Analysis Methodologies and Protocols: U.S. Patent 7,808,923［P］. 2010-10-05. ［3］ 孙昱, 蒋馥蔚, 夏靖波, 等. 一种改进的高速网络分布式流量抽样算法［J］. 西安电子科技大学学报, 2013, 40(3): 160-165. Sun Yu, Jiang Fuwei, Xia Jingbo,et al. Improved Distributed Traffic Sampling Algorithm for High Speed Network［J］. Journal of Xidian University, 2013, 40(3): 160-165. ［4］ Aghdai A, Zhang F, Dasanayake N, et al. Traffic Measurement and Analysis in an Organic Enterprise Data Center［C］//Proceedings of IEEE 14th International Conference on High Performance Switching and Routing. Piscataway: IEEE Computer Society, 2013: 49-55. ［5］ 张震, 汪斌强, 张风雨, 等. 基于LRU-BF策略的网络流量测量算法［J］. 通信学报, 2013, 34(1): 111-120. Zhang Zhen, Wang Binqiang, Zhang Fengyu, et al. Traffic Measurement Algorithm Based on Least Recent Used Bloom Filter［J］. Journal on Communications, 2013, 34(1): 111-120. ［6］ 周爱平, 程光, 郭晓军. 高速网络流量测量方法［J］. 软件学报, 2014, 25(1): 135-153. Zhou Aiping, Cheng Guang, Guo Xiaojun. High-speed Network Traffic Measurement Method［J］. Journal of Software, 2014, 25(1): 135-153. ［7］ Estan C, Varghese G. New Directions in Traffic Measurement and Accounting［J］. Computer Communication Review, 2002, 32(4): 323-336. ［8］ De Godoy S, Jeferson W, Ling L L. A New Binomial Conservative Multiplicative Cascade Approach for Network Traffic Modeling［C］//IEEE 27th International Conference on Advanced Information Networking and Applications. Piscataway: IEEE, 2013: 794-801. ［9］ Gebert S, Pries R, Schlosser D, et al. Internet Access Traffic Measurement and Analysis［C］//Lecture Notes in Computer Science: 7189. Berlin: Springer, 2012: 29-42. ［10］ Chang C W, Liu H, Huang G, et al. Distributed Measurement-aware Routing: Striking a Balance between Measurement and Traffic Engineering［C］//Proceedings of IEEE Conference on Computer Communications. Piscataway: IEEE, 2012: 2516-2520. ［11］ Marold A, Lieven P, Scheuermann B. Probabilistic Parallel Measurement of Network Traffic at Multiple Locations［J］. IEEE Network, 2012, 26(1): 6-12. ［12］ Lu Y, Montanari A, Prabhakar B, et al. Counter Braids: a Novel Counter Architecture for Per-flow Measurement［J］. Performance Evaluation Review, 2008, 36(1): 121-132. ［13］ Kumar A, Xu J, Wang J. Space-code Bloom Filter for Efficient Per-flow Traffic Measurement［J］. IEEE Journal on Selected Areas in Communications , 2006, 24(12): 2327-2339. ［14］ Lieven P, Scheuermann B. High-speed Per-flow Traffic Measurement with Probabilistic Multiplicity Counting［C］//Proceedings of IEEE Conference on Computer Communications. Piscataway: IEEE, 2010: 1-9. ［15］ Flajolet P, Nigel Martin G. Probabilistic Counting Algorithms for Data Base Applications［J］. Journal of Computer and System Sciences, 1985, 31(2): 182-209.

PDF (PC)

332

赞

被引次数

2

摘要：

针对现有的数据流流量测量概率多重计数方法空间复杂度高和空间利用率低的问题，提出了一种基于两层位域的数据流流量测量方法．该方法分为两个步骤:数据捕获阶段．将到达数据包采用两个独立的哈希函数分别映射至两层位域; 数据恢复阶段．对位域恢复得到的两个虚拟矩阵按位取交集，消除哈希碰撞引起的误差．实验结果表明，和概率多重计数方法相比，两层位域方法在存储空间降低75％的前提下，仍具有高的数据流估算精度．

关键词: 计算机网络, 流量测量, 数据流估算, 位域

Abstract:

It is extremely difficult to measure traffic information with a growing network link speed. In recent years, increasing focus has been put on probabilistic algorithms which are fast enough to examine all packets and can provide estimates of the sizes of all flows. However, the previously proposed flow estimating algorithm of PMC has the drawbacks of poor space efficiency and large estimation error. To address the problem, a double bit field (D-BF) algorithm is proposed. The method is divided into two steps: the newly arrived packet is mapped to two bit fields using different hash functions in the data capturing stage; two virtual matrixes recovered from the bit fields have been intersected to eliminate errors caused by the hash collision in the data recovering stage. Experimental results show that the proposed D-BF is more accurate than PMC in flow estimate, while a reduction of 75% in memory space can be achieved.

Key words: computer network, traffic measurement, flow estimate, bit field

中图分类号: 

  • TP393
　陕ICP备09011600号
版权所有 © 2018 《西安电子科技大学学报》编辑部
地址：西安市太白南路2号349信箱(710071) Tel: (029)88202853 Email:xuebao@mail.xidian.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发