学位论文 > 优秀研究生学位论文题录展示

基于布鲁姆过滤器的IP骨干网流量分析前端处理算法研究

作　者: 张进
导　师: 邬江兴
学　校: 解放军信息工程大学
专　业: 通信与信息系统
关键词: 网络流量分析流量测量数据包公平抽样布鲁姆过滤器业务流分类系统
分类号: TN915.06
类　型: 博士论文
年　份: 2008年
下　载: 65次
引　用: 3次
阅　读: 论文下载

内容摘要

本文结合国家863计划“十一五”重大项目“新一代高可信网络”总体技术相关课题的研究需求,重点研究高速骨干网流量分析的前端处理算法及其工程实现技术。以布鲁姆过滤器为切入点,本文的研究工作包括三个方面:第一,布鲁姆过滤器的研究与改进;第二,基于布鲁姆过滤器的前端处理算法的设计;第三,高速骨干网业务流实时分类前端系统的设计与实现技术。首先,本文对现有的三种低计算复杂度的计数型布鲁姆过滤器(Counting Bloom Filter, CBF)进行了分析比较,并提出了改进。对Na?ve Counting Bloom Filte(rNCBF)、Space-Code Bloom Filter(SCBF)和d-left Counting Bloom Filter(dlCBF)进行了深入分析,给出了其参数最优设置准则。采用计数误差、空间复杂度和负载适应性为性能指标,对上述三种CBF的性能进行了系统比较。发现虽然就计数误差和空间复杂度而言,dlCBF是三种CBF中最优的,但dlCBF在负载适应性方面却存在缺陷。对dlCBF进行了改进,提出了一种具有良好负载适应性的计数型布鲁姆过滤器BSdlCBF(Binary-Shrinking d-left Counting Bloom Filter)。通过仿真实验,将BSdlCBF和dlCBF、NCBF以及SCBF进行了比较,结果表明BSdlCBF的性能明显优于已有的三种计数型布鲁姆过滤器。其次,本文将BSdlCBF应用于前端处理算法的设计。基于BSdlCBF,提出了一种新的骨干网数据流流量测量算法MR-BSdlCBF(Multi-Resolution BSdlCBF),与已有的同类流量测量算法MRSCBF(Multi-Resolution SCBF)相比,MR-BSdlCBF算法的优势是负载适应性好,空间复杂度低,并可记录流标识。在MR-BSdlCBF算法基础上,本文最终提出了一种空间高效的数据包公平抽样算法SEFS(Space-Efficient Fair Sampling),SEFS算法不仅空间复杂度低,而且对于短流的抽样性能明显优于已有的公平抽样算法。SEFS算法较低的空间复杂度使之易于以IP核(Intellectual Property Core)的形式集成到网络设备中去。最后,本文实现了骨干网业务流实时分类前端系统。提出了骨干网业务流实时分类系统的前后端分离的系统结构。该系统结构的优点是消除了前后端的紧耦合,从而增强了系统实现的灵活性,提高了业务流分类的精度,降低了骨干网业务流实时分类的实现代价。基于这种系统结构,本文给出了骨干网业务流实时分类前端系统的硬件实现方法,并详细讨论了基于FPGA(Field Programmable Gate Array:现场可编程门阵列)的SEFS算法的实现技术。本文所实现的骨干网业务流实时分类前端系统已经在国家急需的“一种新型互联网内容监管系统”中得到了应用。

全文目录

摘要  10-11
ABSTRACT  11-13
第一章绪论  13-27
  1.1 课题研究的背景与目的  13-17
    1.1.1 网络流量分析的目的与意义  13
    1.1.2 骨干网流量分析的关键技术  13-16
    1.1.3 课题来源及研究目的  16-17
  1.2 前端处理算法的研究现状  17-25
    1.2.1 数据包抽样  17-19
    1.2.2 数据流测量  19-21
    1.2.3 布鲁姆过滤器  21-24
    1.2.4 前端处理模块的实现技术  24-25
  1.3 本文的研究工作及论文结构安排  25-27
第二章三种计数型布鲁姆过滤器的性能分析与比较研究  27-43
  2.1 引言  27-28
  2.2 性能指标  28-29
  2.3 计数误差分析  29-35
    2.3.1 NCBF 的计数误差分析  29-31
    2.3.2 SCBF 的计数误差分析  31-32
    2.3.3 dlCBF 的计数误差分析  32-35
  2.4 比较方法  35-36
  2.5 实验结果与分析  36-41
    2.5.1 计数误差比较  36-39
    2.5.2 空间复杂度比较  39
    2.5.3 负载适应性比较  39-41
  2.6 本章小结  41-43
第三章 BSdlCBF：一种具有良好负载适应性的计数型布鲁姆过滤器  43-55
  3.1 引言  43-44
  3.2 负载适应性的衡量指标  44
  3.3 BSdlCBF 结构描述  44-45
  3.4 性能分析  45-47
    3.4.1 错误概率分析  45-46
    3.4.2 复杂度分析  46-47
  3.5 仿真实验  47-53
    3.5.1 模拟流量数据仿真  48-51
    3.5.2 真实流量数据仿真  51-53
  3.6 本章小结  53-55
第四章基于多解析度BSdlCBF 的骨干网数据流流量测量算法  55-71
  4.1 引言  55-56
  4.2 问题描述与性能指标  56
  4.3 MR-BSdlCBF 算法结构  56-58
  4.4 性能分析  58-65
    4.4.1 估计误差分析  58-60
    4.4.2 空间复杂度分析  60-62
    4.4.3 计算复杂度分析  62-65
  4.5 仿真实验  65-69
    4.5.1 模拟流量仿真  66
    4.5.2 真实流量仿真  66-69
  4.6 本章小结  69-71
第五章一种空间高效的数据包公平抽样算法及应用  71-87
  5.1 引言  71-72
  5.2 数据包公平抽样  72-75
    5.2.1 公平抽样的抽样比分析  73-75
  5.3 MR1-BSdlCBF 流量估计算法  75-78
    5.3.1 估计误差分析  75-77
    5.3.2 空间复杂度分析  77-78
    5.3.3 计算复杂度分析  78
  5.4 算法应用  78-85
    5.4.1 数据流的流量测量  79-81
    5.4.2 长流检测  81-82
    5.4.3 业务流分类  82-85
  5.5 本章小结  85-87
第六章骨干网业务流实时分类前端系统的设计与实现  87-101
  6.1 骨干网业务流实时分类系统的结构概述  87-88
  6.2 前端系统的实现方法概述  88-89
  6.3 基于 FPGA 的 SEFS 算法实现  89-99
    6.3.1 BSdlCBF 的处理流程分析  89-91
    6.3.2 BSdlCBF 关键逻辑的设计  91-94
    6.3.3 MR1-BSdlCBF 算法实现  94-96
    6.3.4 测试结果  96-99
  6.4 本章小结  99-101
第七章结束语  101-104
  7.1 本文的研究成果  101-102
  7.2 本文的主要创新点  102-103
  7.3 需要进一步研究的问题  103-104
致谢  104-105
参考文献  105-110
作者在学期间取得的学术成果  110-112
附录  112-114
  附录 A d-left 哈希函数桶负载分布的计算方法  112-113
  附录 B PPLive 和 PPStream 的负载特征字段  113
  附录 C 本文所采用的流量数据的说明  113-114

基于布鲁姆过滤器的IP骨干网流量分析前端处理算法研究

内容摘要

全文目录

相似论文