网络流量测量中的抽样算法研究

发布时间：2017-04-05 05:13

  本文关键词：网络流量测量中的抽样算法研究，由笔耕文化传播整理发布。

【摘要】：通过对流量的测量和运行状况的分析,网络测量为网络管理、性能提升和结构优化提供参考依据。然而,由于高速互联网技术的迅速发展和大数据时代的到来,网络中的数据呈现爆炸式增长,捕获每个报文信息或者流信息并进行存储和分析已变的不可能。将抽样技术引入流量测量中能有效的解决该瓶颈问题,并且能大大减少测量数据,因此抽样技术成为网络流量工程研究的重点内容之一。本文系统全面地总结了网络流量测量理论,分析了在当前高速网络环境中测量遇到的困难,指出抽样技术在网络测量中的重要作用。接着详细阐述了抽样技术的相关概念,讨论了随机抽样、系统抽样和分层抽样等几种基本的抽样方法,分析比较了抽样测量中哈希算法、概要数据结构等关键技术。最后,通过研究目前网络的特性,将抽样技术与结构简单、查找匹配迅速的Bloom filter(布鲁姆过滤器)相结合,提出了基于LRU_CBF的大流检测算法和基于树形布鲁姆过滤器的流抽样算法。经性能分析和仿真实验证明,本文提出的算法能够在提高测量准确性的同时,提高系统的资源利用率。具体研究内容如下:(1)本文在系统研究了标准型、计数型、拆分型等Bloom filter特点的基础上,将性能优越的计数型Bloom Filter与操作系统中经典的页面置换算法LRU(最近最久未使用)策略相结合设计出一种大流检测算法。该算法使用两层结构,LRU先将大流过滤出来,CBF进一步对大流进行判断,使“大流过滤”与“大流判断”两个过程分离开。这样可以简化数据的存储结构,降低空间复杂度,精确检测大流,提高准确性。通过仿真实验,将本文提出的基于LRU_CBF的大流检测算法与两层CBF算法进行准确性方面的对比得知,本文提出的算法具有更高的准确性和更好的资源利用率。(2)网络规模的不断扩张使得网络流量的特征变得异常复杂,单层次的数据结构不能满足网络测量的要求。本文针对目前标准BF算法在流量过大时会造成计数器溢出的缺陷,设计了一种多层次结构的树形布鲁姆过滤器。改进过滤器的每一层都是一个标准BF,将其中置1的比特位映射出叶子节点,逐层映射后形成树形的多层次过滤器。当流量较大时增加新的BF,防止BF溢出造成测量误差。将树形BF与基于报文的流抽样算法相结合,应用到实际的网络流量测量中,可以在减少测量个数的同时提高测量精度。通过仿真对该算法与基于其他Bloom filter的抽样算法进行了测量误差方面的比较,分析可知,本文提出的算法提高了抽样的准确性,降低了空间利用率。
【关键词】：流量测量 抽样 最近最久未使用 计数型布鲁姆过滤器 树形布鲁姆过滤器
【学位授予单位】：曲阜师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP393.06
【目录】：

• 摘要3-4
• Abstract4-8
• 第1章 绪论8-14
• 1.1 课题研究背景8-9
• 1.2 网络测量的意义9-11
• 1.3 高速网络给网络测量带来的困难11
• 1.4 国内外研究现状11-12
• 1.4.1 国外现状11-12
• 1.4.2 国内现状12
• 1.5 论文结构12-14
• 第2章 网络流量测量和抽样技术14-21
• 2.1 网络流量测量14-17
• 2.1.1 网络流量14-15
• 2.1.2 网络流量的特性15-16
• 2.1.3 网络流量的测量方法16-17
• 2.2 流量测量的体系结构17
• 2.3 抽样技术的基本理论17-20
• 2.3.1 相关概念17-18
• 2.3.2 基本的抽样方法18-19
• 2.3.3 抽样技术中新引入的关键技术19-20
• 2.4 本章小结20-21
• 第3章 基于LRU_CBF的大流检测算法21-29
• 3.1 引言21
• 3.2 关键技术21-24
• 3.2.1 LRU思想描述21-22
• 3.2.2 BF原理22-24
• 3.3 LRU_CBF算法流程24-25
• 3.4 算法的理论分析和实验仿真25-28
• 3.4.1 准确性25-27
• 3.4.2 空间复杂度27
• 3.4.3 时间复杂度27
• 3.4.4 实验仿真27-28
• 3.5 本章小结28-29
• 第4章 基于树形布鲁姆过滤器的流抽样测量算法29-38
• 4.1 引言29
• 4.2 多层次结构的Blooming Tree算法29-30
• 4.2.1 Blooming Tree的数据结构29
• 4.2.2 算法原理29-30
• 4.3 一种新型的树型布鲁姆过滤器30-33
• 4.3.1 新型树形布鲁姆过滤器算法的查询过程31-32
• 4.3.2 新型树形布鲁姆过滤器算法的更新过程32-33
• 4.4 基于树形布鲁姆过滤器的流抽样算法33-34
• 4.4.1 基本原理33
• 4.4.2 算法描述33-34
• 4.5 仿真结果比较34-36
• 4.5.1 实验数据的选择34-35
• 4.5.2 结果对比35-36
• 4.6 本章小结36-38
• 第5章 总结与展望38-40
• 5.1 总结38
• 5.2 展望38-40
• 参考文献40-43
• 在读期间发表的学术论文及研究成果43-44
• 致谢44

【参考文献】

中国期刊全文数据库 前4条

1 陈松;王珊;周明天;;基于实时分析的网络测量抽样统计模型[J];电子学报;2010年05期

2 刘卫江;白磊;景泉;;基于Sample-CBF技术的长流识别实现[J];计算机工程;2007年20期

3 谈杰;李星;;网络测量综述[J];计算机应用研究;2006年02期

4 吴桦;龚俭;杨望;;一种基于双重Counter Bloom Filter的长流识别算法[J];软件学报;2010年05期

  本文关键词：网络流量测量中的抽样算法研究，，由笔耕文化传播整理发布。

本文编号：286526