IP包分类算法研究

论文摘要

网络新业务的不断出现,对网络传输速度提出了越来越高的要求。为适应这些新变化,ISP （Internet Service Provider）一方面必须升级因特网骨干网络的速度,一方面必须筹划新的有差别的网络服务,以满足不同用户的需要。由于光纤技术和DWDM（DenseWavelength-Division Multiplexing）技术的发展使得链路的速率不再成为瓶颈,而路由器作为连接链路的节点,其性能会成为主要瓶颈。高速路由器要求包分类装置具有线速度的吞吐能力,使得包分类的设计具有很高的难度,成为路由器处理流程中最大的瓶颈之一,并且随着IP网络应用领域的不断扩展,要求包分类算法对规则维数、规则数量和每维的宽度可扩展能力强,这也加剧了包分类算法设计的难度,成为扩宽IP （Internet Protocol）网络应用的障碍。IP包分类是路由器根据IP包的多个域,从分类器数据库中匹配每个输入包,确定包转发规则的技术。分类器为实现因特网新业务提供了统一的方式,包分类是因特网提供一切有差别服务和其他新业务的基础,高速包分类问题是具有重要现实意义和理论价值的研究课题。路由器不仅要完成按照IP包头目的地址转发IP包的任务,同时也要满足能区分不同的数据流的任务。一维IP包分类用于处理前一个任务,多维IP包分类用于处理后一个任务。IP包分类算法根据IP包头地源地址、IP目的地址、源端口号、目的端口和协议五个域进行分类,把不同的包归为不同的流,以便为不同的流提供有差别的服务。本文首先介绍了IP包分类算法的应用背景,然后给出了IP包分类问题的详尽数学描述。对现有的各种IP包分类算法进行了详细的分析,并对各种算法的查找性能和存储空间需求进行了分析比较。在此基础上,针对AQT （Area-based Quad Tree）算法提出了改进算法。为了使原有AQT算法能够应用于五维的IP包分类,使用无冲突哈希函数处理源端口号、目的端口和协议域,提出了一种新的IP包分类算法NCHAQT（Non-Collision Hash Area-based Quad Tree）。详细地给出了该算法的基本思想、预处理过程、包匹配过程,并对规则优先权给出了明确的定义。经理论分析与仿真实验证明,该算法是一个综合性能较高的算法。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 论文的内容和结构
• 1.2.1 论文内容
• 1.2.2 论文的组织结构
• 第二章 IP 包分类问题概述
• 2.1 IP 包分类的数学模型
• 2.1.1 IP 包分类的相关术语
• 2.1.2 IP 包分类问题的定义
• 2.2 IP 包分类的性能评价指标
• 2.3 IP 包分类算法的工作原理
• 2.4 一维IP 包分类算法
• 2.4.1 最长前缀匹配
• 2.4.2 范围匹配转化为前缀匹配
• 2.4.3 一维包分类算法分类
• 2.5 多维IP 包分类算法
• 第三章 IP 包分类问题的研究现状
• 3.1 一维IP 包分类算法研究现状
• 3.1.1 基本二叉键树
• 3.1.2 路径压缩键树
• 3.1.3 级压缩键树
• 3.1.4 受控前缀扩展算法
• 3.1.5 紧致压缩键树
• 3.1.6 地址前缀长度的二分查找
• 3.1.7 地址区间的二分查找
• 3.1.8 基于TCAM 的路由查找
• 3.1.9 一维IP 包分类算法的性能比较
• 3.2 多维IP 包分类算法的研究状况
• 3.2.1 分层查找树
• 3.2.2 Grid-of-tries 算法
• 3.2.3 RFC 算法
• 3.2.4 智能层次切割算法
• 3.2.5 AQT 算法
• 3.2.6 位并行算法
• 3.2.7 Cross-Product 算法
• 3.2.8 Tuple Space Search 算法
• 3.2.9 Modular 算法
• 3.2.10 基于TCAM 数据包分类
• 3.2.11 IP 包分类算法的性能比较
• 3.3 当前研究工作的不足
• 3.3.1 一维IP 包分类算法的不足
• 3.3.2 多维IP 包分类算法的不足
• 第四章 基于AQT 的多维IP 包分类算法
• 4.1 概述
• 4.2 AQT 算法
• 4.2.1 AQT 算法概述
• 4.2.2 构造四叉树
• 4.2.3 搜索四叉树
• 4.3 哈希函数
• 4.3.1 哈希表的概念
• 4.3.2 哈希函数的构造方法
• 4.3.3 处理冲突的方法
• 4.4 NCHAQT 算法
• 4.4.1 选择无冲突的哈希函数的依据
• 4.4.2 构造无冲突的哈希函数
• 4.4.3 算法性能分析及仿真
• 4.4.4 小结
• 第五章 结论及未来的工作
• 致谢
• 攻读硕士学位期间从事的科研工作
• 参考文献