网络流量测量技术研究与分析 ——基于抽样和Bloom filters的流量测量

论文摘要

网络流量测量是网络监测、管理和控制的基础。随着互联网的发展,网络行为变得越来越复杂,网络流量也越来越大,使直接对流量进行全面测量变得极为困难,为解决这一问题,目前主要采用抽样技术和哈希技术。其中,Bloom filter是最近逐渐在网络领域受到关注的一种高效的哈希结构,它对数据集合采用一个位串表示并能有效支持集合元素的哈希查找操作,以允许一定的误称率(false positive error)为代价,获得很高的查找效率和很小的空间消耗。本文首先根据网络流量的自相似性和重尾分布特点,提出了自适应系统双抽样,每次抽取两个相邻的数据包,旨在保证获得充足的长流信息,不仅能正确估算出Hurst参数,保持了原流量的自相似结构,而且在链路负载测量、包到达时间间隔等方面,较传统抽样方法都有明显的改进。基于DCF(Dynamic Count filter)的资源可控流抽样则是基于网络流级别的抽样测量,DCF是Bloom filter的改进结构,支持多重集的元素频率查询。该方法对测量间隔内到达的报文进行固定数量的抽样,并采用DCF哈希算法维护流记录,从限制抽样流样本数和对抽样流的处理两方面来有效地控制资源消耗,抽样率自适应实际流量变化而变化,并具有简单性和准确性。对于很多应用,了解长流就已足够。长流是指报文数超过某个值的流,它占据了大部分网络流量但数量上相对较少。基于抽样和Bloom filters的长流检测,首先对报文进行抽样,然后经过Bloom filters哈希运算,Bloom filters维护多个哈希函数降低了哈希冲突,在内存中用临时表和流信息表来判断到达阈值的流并维护其信息,满足了高速网络环境下对长流检测的要求,在保证测量精度的同时有效得控制了资源消耗。最后,对本文的工作进行了总结,并指出了以后的研究方向。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题研究背景和意义
• 1.2 国内外的研究现状
• 1.3 本文主要工作
• 1.4 论文的组织结构
• 第二章 网络流量特性及测量技术研究
• 2.1 网络的流量特性
• 2.2 网络测量技术分类
• 2.2.1 按测量方式分类
• 2.2.2 按测量内容分类
• 2.2.3 按测量基准分类
• 2.2.4 按测量点分类
• 2.3 抽样技术基本知识
• 2.3.1 抽样技术的相关知识和概念
• 2.3.2 几种基本的抽样方法
• 2.4 流量抽样测量技术
• 2.4.1 流量抽样测量概述
• 2.4.2 流量抽样测量原理
• 2.4.3 流量抽样测量分类
• 2.4.4 流量抽样测量的发展趋势
• 2.5 网络测量测度
• 2.6 网络测量中的不确定性和误差处理
• 2.7 本章小结
• 第三章 Bloom filter 及其在网络中的应用
• 3.1 Bloom filter 概述
• 3.2 标准 Bloom filter
• 3.3 Bloom filter 的代数运算
• 3.4 Bloom filter 的改进结构
• 3.4.1 Counting Bloom filter
• 3.4.2 Spectral Bloom filter
• 3.5 Bloom filter 在网络中的应用
• 3.5.1 在分布式缓存中的应用
• 3.5.2 P2P/覆盖网络中的应用
• 3.5.3 数据包路由
• 3.5.4 在网络流量测量中的应用
• 3.5.5 网络安全中的应用
• 3.6 本章小结
• 第四章 基于自相似特性的自适应系统双抽样
• 4.1 传统抽样方法
• 4.2 网络流量的重尾分布特性
• 4.3 算法思想与设计
• 4.3.1 算法思想
• 4.3.2 算法设计及说明
• 4.4 对估算 Hurst 参数准确性的理论分析
• 4.5 实验分析
• 4.6 本章小结
• 第五章 基于DCF 的资源可控流抽样应用分析
• 5.1 流及测量参数
• 5.2 资源限制背景
• 5.3 Dynamic Count filter 原理
• 5.4 流抽样设计
• 5.4.1 整体设计
• 5.4.2 单个流处理
• 5.5 理论及实验分析
• 5.5.1 理论估值
• 5.5.2 实验分析
• 5.6 本章小结
• 第六章 基于抽样和 Bloom filters 的长流检测
• 6.1 长流的定义
• 6.2 算法设计
• 6.2.1 整体设计
• 6.2.2 单个流处理
• 6.3 理论分析
• 6.3.1 理论估值
• 6.3.2 误差分析
• 6.4 实验分析
• 6.5 本章小结
• 第七章 总结与展望
• 7.1 总结
• 7.2 下一步工作展望
• 致谢
• 参考文献
• 附录：作者在攻读硕士学位期间发表的论文