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

可扩展高性能分布式报文分类算法研究

作 者: 周粳迪
导 师: 程东年
学 校: 解放军信息工程大学
专 业: 通信与信息系统
关键词: 报文分类 可扩展性 分布式算法 元组空间 域冲突空间 性能评测
分类号: TP393.06
类 型: 硕士论文
年 份: 2009年
下 载: 20次
引 用: 0次
阅 读: 论文下载
 

内容摘要


随着Internet规模的日益扩大,各种网络应用迅速发展、网络流量迅猛增长,要求网络设备提供更高的带宽和更强的数据分类处理能力。报文分类作为防火墙、入侵检测、QoS、虚拟专用网、流量计费等应用领域的关键技术,正面临前所未有的挑战。高速多维报文分类算法的不足,已成为制约网络发展的瓶颈。分布式报文分类算法以其速度快、维数可扩展性强等优势成为学术研究的热点。本文结合国家863项目新一代高可信网络的要求,对报文分类领域的成果进行了较全面的总结,着重研究可扩展高性能分布式报文分类算法,主要研究内容和创新点如下:针对影响和限制分布式报文分类算法性能的主要因素进行分析,提出一种易于硬件实现的算法基于counting Bloom filter的分布式元组空间叉积算法(DCTS-CBF)。该算法为解决分布式算法规模可扩展较差的问题,将元组空间的概念引入到分布式报文分类,提出带缓存的树状多级聚合网络结构以及基于counting Bloom filter变体的节点查询方法;然后,算法提出一种对counting Bloom filter变体的最大化剪枝方法,以实现用最小的开销避免false positive的发生,进而降低算法的访存次数。仿真结果表明,算法具有较高的存储效率,而且内存消耗的增长趋势明显低于规则库规模的增长趋势,进而提高了规模可扩展性;另一方面,只要选择合适的存储器件,算法的处理速度就能够达到OC-192的标准。针对DCTS-CBF算法在更新频繁时会出现性能下降的问题,提出一种旨在提高更新性能的改进算法基于域冲突空间的多标签树算法(MLT-FCS)。为避免聚合网络结构在算法执行过程中无法更改的问题,MLT-FCS将多级聚合网络改进为单级聚合,同时提出域冲突空间的概念以及对规则库的预处理方法;然后,算法针对聚合结果的特殊形式设计出多标签树查询结构及方法,以期快速、低耗地实现准确匹配;最后,算法设计出一种基于主备缓存切换的更新方案,使得整个更新过程不会对算法的执行产生任何影响。分析及仿真结果表明,该算法在增加适当内存消耗的情况下进一步提高了处理速度,并能够在执行过程中适应规则库特性的改变,从而能够应用到规则更新频繁的场景下。针对报文分类算法现有的性能评测方法在一致性、可继承性方面的缺陷,本文设计了一种报文分类算法性能评测系统CPCA-PES。该系统利用ClassBench工具集生成多种仿真场境,并实时监测算法的时间、空间性能,同时利用数理统计的方法确定仿真的运行次数以期得到尽可能贴近真实值的性能仿真数据,力图将报文分类算法的性能评价工作标准化、规格化,既为本课题的研究提供了实验验证支持,又为后续报文分类领域的技术研究和方案设计提供了基础。

全文目录


表目录  7-8
图目录  8-10
摘要  10-11
ABSTRACT  11-13
第一章 绪论  13-19
  1.1 问题的提出  13-14
  1.2 技术背景  14-16
  1.3 课题背景和目的  16-17
  1.4 论文主要工作  17-18
  1.5 论文结构安排  18-19
第二章 相关研究工作  19-27
  2.1 报文分类相关定义  19-20
    2.1.1 问题描述  19-20
    2.1.2 评价标准  20
  2.2 几种典型可扩展报文分类算法  20-25
    2.2.1 Crossproducting 算法  21
    2.2.2 RFC 算法  21-22
    2.2.3 BV 算法  22-23
    2.2.4 ABV 算法  23
    2.2.5 EGT-PC 算法  23-24
    2.2.6 DCFL 算法  24-25
    2.2.7 算法复杂度  25
  2.3 可扩展报文分类算法设计趋势展望  25-26
  2.4 本章小结  26-27
第三章 基于Counting Bloom Filter 的分布式元组空间叉积算法  27-47
  3.1 引言  27-28
  3.2 元组空间的概念  28-29
  3.3 DCTS-CBF 算法的提出  29
  3.4 规则库的预处理  29-30
  3.5 聚合网络  30-32
    3.5.1 分域匹配  31
    3.5.2 逐级聚合  31-32
    3.5.3 聚合网络结构的确定  32
  3.6 聚合节点  32-36
    3.6.1 Bloom filter 及其变体  33-34
    3.6.2 最大化剪枝  34-36
    3.6.3 聚合节点查询结构  36
  3.7 域搜索引擎  36-37
  3.8 性能分析  37-42
    3.8.1 关键参数的取值方法  38-39
    3.8.2 时间性能分析  39-40
    3.8.3 空间性能分析  40-42
  3.9 仿真验证  42-46
    3.9.1 聚合网络仿真结构  42-43
    3.9.2 相关条件说明  43
    3.9.3 仿真结果及分析  43-46
  3.10 本章小结  46-47
第四章 基于域冲突空间的多标签树算法  47-59
  4.1 引言  47
  4.2 域冲突空间  47-49
  4.3 MLT-FCS 算法数据结构  49-51
    4.3.1 基于标签的数据结构  49-51
    4.3.2 多标签树结构  51
  4.4 MLT-FCS 算法查询过程  51-54
  4.5 优化更新  54-56
    4.5.1 基本更新过程  54-55
    4.5.2 基于主备缓存切换的更新方案  55-56
  4.6 仿真验证  56-58
    4.6.1 性能分析  56-57
    4.6.2 仿真实验  57-58
  4.7 本章小结  58-59
第五章 报文分类算法性能评测系统设计  59-69
  5.1 引言  59
  5.2 评测系统基本结构  59-60
  5.3 ClassBench 方法和原理  60-63
    5.3.1 基于benchmark 文件生成Trace  60-61
    5.3.2 参数控制原理  61-62
    5.3.3 Trace 生成器  62-63
  5.4 算法性能参数的提取  63-66
    5.4.1 分类模块  63-65
    5.4.2 监测模块  65-66
  5.5 典型算法评测及分析  66-68
    5.5.1 评测结果  66-67
    5.5.2 结果分析  67-68
  5.6 本章小结  68-69
结束语  69-71
参考文献  71-74
作者简历 攻读硕士学位期间完成的主要工作  74-75
致谢  75

相似论文

  1. 一种高性能可扩展公钥密码协处理器的研究与设计,TN918.1
  2. 构建分布式系统的关键技术研究与实现,TP338.8
  3. 微放电通道的径向扩展与放电均匀性的研究,TM83
  4. 无线传感器网络节点三维定位算法研究,TN929.5
  5. 配电网单相接地故障隔离方法的研究,TM862
  6. 基于OVM的SoC功能验证系统的设计与实现,TN47
  7. 高性能存储系统的关键技术研究,TP333
  8. 基于硬件计数器虚拟化的多虚拟机性能评测研究,TP302
  9. 分布式内存数据库存储研究,TP311.13
  10. 互联网文件存储服务系统研究,TP393.09
  11. 对等游戏平台的可扩展性与状状一致性的研究,TP393.09
  12. 异构(CPU-GPU)计算机系统性能评测与优化技术研究,TP306.2
  13. 基于分布式的频繁闭合模式挖掘算法研究,TP311.13
  14. 一种适用于井下超声波通信的FSK调制解调技术研究,TN914
  15. 分布式声源定位与跟踪算法研究,TN912.3
  16. 基于TCAM的报文分类算法研究,TP393.08
  17. 园区企业劳动人事管理系统的设计与实现,TP311.52
  18. 基于倒排索引的压缩算法性能研究,TP391.3
  19. 辅助计划系统的设计与实现,TP311.52
  20. 不同养护管理措施对多年生黑麦草扩展性的影响,S688.4

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机的应用 > 计算机网络 > 一般性问题 > 计算机网络测试、运行
© 2012 www.xueweilunwen.com