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

报文分类算法的研究

作　者: 张定心
导　师: 王振兴
学　校: 中国人民解放军信息工程大学
专　业: 军事情报学
关键词: 报文分类规则库递归流分类元空间算法分域查找算法
分类号: TP393.02
类　型: 硕士论文
年　份: 2003年
下　载: 188次
引　用: 3次
阅　读: 论文下载

内容摘要

为了满足下一代高速信息网提出的Qos、VPN、MPLS、接入控制等新特性，Internet必须提供对带宽，时延，丢包率等各方面网络状况的保证，即必须对各种有不同需求的报文进行分类。本文首先对现有的各种报文分类算法进行了系统、详细的研究，并对各种算法的查找性能和存储空间需求进行了分析比较，分析总结出当前报文分类领域面临的三个问题。接着本文介绍了应用于大规模规则库的快速分类算法的解决方案——递归流分类，该算法是一种利用线性存储区分块递归映射的算法。本文主要深入研究了该算法利用块等价部分类实现递归映射的过程，并针对该算法三阶段的优化流程结构进行了编程实现。接着本文在深入阐述Tuple Space概念的基础上介绍了元空间算法的原理和算法流程，该算法是目前适应于大规模规则库且支持快速更新的多域报文分类算法。在对加标记的改进方法的详细论述的基础上，本文介绍了一种二维分类算法——矩形算法，该算法是目前一种查找性能和空间需求经过优化的二维算法。然后本文针对TSS原始算法设计的缺陷，提出了基于规则长度的比特向量算法，仿真结果显示该算法的性能优于TSS的原始算法。最后考虑IPv6下的报文分类算法，本文引入了规则子集的概念，并利用该概念使多维报文分类可以利用现有的一维快速IP路由查找算法，提出了可适用于IPv6的分域查找算法，该算法在最坏情况下只需要7次访存。分析上述各种算法的基本思想、算法结构及流程，本文总结出设计多域报文分类算法的原则：针对当前链路速度不断提高和规则库规模不断扩大的现状，设计快速的多域报文分类算法已经成为一个技术难点，一般的原则是在分析实际规则库规则的分布规律地基础上对现有的经典算法进行组合或者优化改进。

全文目录

摘要  4-5
Abstract  5-6
第一章绪论  6-9
  1.1 报文分类的重要性  6-7
  1.2 报文分类的应用  7-8
  1.3 论文的主要内容和结构安排  8
  1.4 本文的主要贡献  8-9
第二章国内外研究现状  9-21
  2.1 问题描述  9-11
    2.1.1 报文分类的定义  9-10
    2.1.2 算法的性能要求  10-11
    2.1.3 算法的理论极限和难点  11
  2.2 各种经典算法介绍  11-18
    2.2.1 国内外相关学者及实验室  11-12
    2.2.2 现有算法简介  12
    2.2.3 线性查找(Linear Search)  12
    2.2.4 DAG算法  12-13
    2.2.5 Grid of Tries(GOT)  13-15
    2.2.6 交叉乘积(Crossproducting)算法  15-16
    2.2.7 基于比特向量的算法  16-17
    2.2.8 基于TCAM的硬件算法  17-18
  2.3 各种算法的性能分析比较  18-21
    2.3.1 报文分类算法的性能参数  18
    2.3.2 各种算法的性能参数  18-20
    2.3.3 本文需要完成的工作  20-21
第三章递归流分类算法  21-31
  3.1 规则的分布规律  21-22
    3.1.1 IP地址前缀分布  21
    3.1.2 协议字段分布  21
    3.1.3 端口分布  21-22
  3.2 RFC算法的来源和基本思想  22
  3.3 RFC算法的基本流程:  22-24
  3.4 RFC算法的预处理  24-26
  3.5 RFC算法的结构分析  26-27
  3.6 算法的性能分析和模拟仿真  27-31
    3.6.1 算法的性能分析  27-28
    3.6.2 模拟方式和仿真环境  28
    3.6.3 相应的数据结构和编程中的一些问题  28-31
第四章元空间算法  31-41
  4.1 元空间算法  31-33
    4.1.1 定义Tuple、Tuple Space  31-32
    4.1.2 原始的TSS算法-直接搜索  32-33
  4.2 加标记的TSS改进算法  33-35
  4.3 矩形分类算法-一种优化的二维报文分类算法  35-37
  4.4 基于规则长度的比特向量算法  37-39
    4.4.1 算法的预处理  38-39
    4.4.2 算法的性能分析  39
  4.5 Hash函数的选择标准  39-41
第五章 IPv6下的报文分类算法  41-47
  5.1 IPv6概述  41-43
    5.1.1 IPv6的报头格式  41-42
    5.1.2 IPv6的128位地址格式:  42
    5.1.3 IPv6的扩展首部:  42-43
  5.2 目前各种算法的可升级性  43-44
  5.3 分域查找算法  44-47
    5.3.1 算法的基本思想和预处理  44-45
    5.3.2 基于地址长度的二分查找算法  45
    5.3.3 端口和协议的匹配过程  45-46
    5.3.4 算法的性能分析  46-47
结束语  47-48
致谢  48-49
参考文献  49-51
附录: 硕士就读期间论文发表情况(含录用)  51

报文分类算法的研究

内容摘要

全文目录

相似论文