论文摘要
随着Internet规模的日益扩大,各种网络应用的数据流迅猛增长,传统路由器单一的“尽力”服务方式已不能满足要求。这一切都对作为Internet核心设备的主干路由器提出了新的要求,需要如资源预留服务、QoS(Quality of Service)服务、虚拟专用网、基于策略的路由等新的“差别”服务机制。而所有这些“差别”服务机制都需要路由器对IP包进行分类,根据数据包头部的内容把数据包归类为某个流的过程称为数据包分类。在路由器等网络设备中,所有属于同一个流的数据包遵循一套预先定义好的规则,并按照类似的方式进行处理。数据包分类系统要求对输入的任何网络信息包与数据库中的规则相匹配。根据匹配的结果,按照符合最高优先级的规则来处理输入的信息包。本文首先介绍了目前常用的数据包分类算法,分析了各个算法的优缺点。在此基础上,通过对现有算法分析,提出了一种在高端路由器上实现快速数据包分类的算法,即利用网络处理器的并行处理能力和RFC算法(Recursive Flow Classification,递归流分类)中等价类的思想,结合Hash水平查找和垂直查找,实现了支持动态更新的多维高速数据包分类算法。本文给出了该算法实现的关键技术,包括eqid映射,CBM值的改进,和Hash冲突的解决。通过对算法的功能和性能进行测试,本算法同现存的路由器上应用的RFC算法相比,在空间复杂度和时间复杂度上都有很大的提高,并且该算法的查找时间与规则库的规模无关。实验结果与理论分析相吻合,达到了预期的效果。
论文目录
摘要Abstract第一章 绪论1.1 研究背景1.2 数据包分类问题的描述1.2.1 数据传输过程1.2.2 数据包分类的定义1.2.3 算法的评价标准1.2.4 算法的理论极限和难点1.3 本文主要工作和论文结构安排第二章 高端路由器的体系结构2.1 路由器的基本结构2.2 高端路由器的软硬件结构2.2.1 高端路由器的系统硬件结构2.2.2 高端路由器的系统软件结构2.3 网络处理器Vitesse IQ22002.3.1 网络处理器的概念2.3.2 Vitesse IQ2200 网络处理器性能特征2.3.3 Vitesse IQ2200 的数据流模块2.3.4 Vitesse IQ2200 的包处理模块2.3.5 Vitesse IQ2200 的系统模块2.3.6 Vitesse IQ2200 系统数据处理过程第三章 经典的数据包分类算法3.1 线性查找3.2 分级树查找3.3 Set-pruning Tries3.4 Grid of Tries3.5 启发式分类算法RFC3.6 基于硬件的分类算法3.7 各种算法的性能参数和比较第四章 数据包分类算法的设计与实现4.1 规则的分布规律4.1.1 IP 地址前缀分布4.1.2 协议字段分布4.1.3 端口分布4.2 路由器中的数据包分类模块4.3 RFC 算法分析4.4 算法的主要思想4.5 CBM 值的改进4.6 Hash 查找4.7 Hash 冲突解决4.8 规则更新4.9 Hash 查找的实现4.10 算法性能分析第五章 性能测试5.1 功能测试5.2 性能测试第六章 结束语致谢参考文献研究成果
相关论文文献
标签：路由器论文; 数据包分类算法论文; 网络处理器论文; 递归流分类论文;
