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

高端路由器中数据包分类技术的研究与实现

作　者: 王华丽
导　师: 王泉
学　校: 西安电子科技大学
专　业: 计算机系统结构
关键词: 路由器数据包分类算法网络处理器递归流分类
分类号: TN915.05
类　型: 硕士论文
年　份: 2007年
下　载: 227次
引　用: 4次
阅　读: 论文下载

内容摘要

随着Internet规模的日益扩大,各种网络应用的数据流迅猛增长,传统路由器单一的“尽力”服务方式已不能满足要求。这一切都对作为Internet核心设备的主干路由器提出了新的要求,需要如资源预留服务、QoS(Quality of Service)服务、虚拟专用网、基于策略的路由等新的“差别”服务机制。而所有这些“差别”服务机制都需要路由器对IP包进行分类,根据数据包头部的内容把数据包归类为某个流的过程称为数据包分类。在路由器等网络设备中,所有属于同一个流的数据包遵循一套预先定义好的规则,并按照类似的方式进行处理。数据包分类系统要求对输入的任何网络信息包与数据库中的规则相匹配。根据匹配的结果,按照符合最高优先级的规则来处理输入的信息包。本文首先介绍了目前常用的数据包分类算法,分析了各个算法的优缺点。在此基础上,通过对现有算法分析,提出了一种在高端路由器上实现快速数据包分类的算法,即利用网络处理器的并行处理能力和RFC算法(Recursive Flow Classification,递归流分类)中等价类的思想,结合Hash水平查找和垂直查找,实现了支持动态更新的多维高速数据包分类算法。本文给出了该算法实现的关键技术,包括eqid映射,CBM值的改进,和Hash冲突的解决。通过对算法的功能和性能进行测试,本算法同现存的路由器上应用的RFC算法相比,在空间复杂度和时间复杂度上都有很大的提高,并且该算法的查找时间与规则库的规模无关。实验结果与理论分析相吻合,达到了预期的效果。

全文目录

摘要  3-4
Abstract  4-7
第一章绪论  7-15
  1.1 研究背景  7-9
  1.2 数据包分类问题的描述  9-13
    1.2.1 数据传输过程  9-11
    1.2.2 数据包分类的定义  11-12
    1.2.3 算法的评价标准  12-13
    1.2.4 算法的理论极限和难点  13
  1.3 本文主要工作和论文结构安排  13-15
第二章高端路由器的体系结构  15-25
  2.1 路由器的基本结构  15-16
  2.2 高端路由器的软硬件结构  16-18
    2.2.1 高端路由器的系统硬件结构  16-17
    2.2.2 高端路由器的系统软件结构  17-18
  2.3 网络处理器Vitesse IQ2200  18-25
    2.3.1 网络处理器的概念  18-19
    2.3.2 Vitesse IQ2200 网络处理器性能特征  19-21
    2.3.3 Vitesse IQ2200 的数据流模块  21-22
    2.3.4 Vitesse IQ2200 的包处理模块  22
    2.3.5 Vitesse IQ2200 的系统模块  22-23
    2.3.6 Vitesse IQ2200 系统数据处理过程  23-25
第三章经典的数据包分类算法  25-35
  3.1 线性查找  25
  3.2 分级树查找  25-27
  3.3 Set-pruning Tries  27-28
  3.4 Grid of Tries  28-30
  3.5 启发式分类算法RFC  30-31
  3.6 基于硬件的分类算法  31-32
  3.7 各种算法的性能参数和比较  32-35
第四章数据包分类算法的设计与实现  35-51
  4.1 规则的分布规律  35-36
    4.1.1 IP 地址前缀分布  35
    4.1.2 协议字段分布  35-36
    4.1.3 端口分布  36
  4.2 路由器中的数据包分类模块  36-38
  4.3 RFC 算法分析  38-39
  4.4 算法的主要思想  39-42
  4.5 CBM 值的改进  42-44
  4.6 Hash 查找  44-45
  4.7 Hash 冲突解决  45-46
  4.8 规则更新  46-47
  4.9 Hash 查找的实现  47-48
  4.10 算法性能分析  48-51
第五章性能测试  51-55
  5.1 功能测试  51
  5.2 性能测试  51-55
第六章结束语  55-57
致谢  57-59
参考文献  59-63
研究成果  63

高端路由器中数据包分类技术的研究与实现

内容摘要

全文目录

相似论文