基于降维的IPv6包分类算法的设计与实现

论文摘要

包分类是下一代因特网网络设备(如MPLS路由器、防火墙、VoIP网关、VPN网关等)和新型网络服务(如QoS服务、包安全过滤、网络地址转换、流量记帐、流量限制服务等)实现的关键技术。研究有效地包分类算法及其实现技术是目前网络技术领域的热门课题。数据包分类就是根据IP数据包从包头中取出相关的域,对其进行分类,在规则集中进行查找,然后返回与该数据包相匹配的优先级最高的规则。之后依据这些规则将包归入不同的数据流中,最后根据不同的服务对不同数据流中的包进行相关联的操作,如转发包,丢弃包等。随着互联网的迅速发展,IPv6将成为下一代互联网体系结构的核心协议。现有的IP网络朝着IPv6的方向发展,各种网络服务也将转移到IPv6上运行。IPv6具有的很多新特性,如IPv6基本报头更简洁、扩展性更好,IPv6能够更好地支持即插即用、服务质量、移动性等。但是,IPv6并没有改变路由器数据平面的基本功能—路由查找和报文分类。IPv6也给报文分类问题提出了新的挑战。IPv6定义了流的概念,通过采用流标签提供了一种更加高效地处理数据分组流的机制,该机制对于实时应用尤其有用。根据RFC3697的定义,路由器可以使用源IP地址、目的IP地址和流标签的三元组来标识一个特定的流。因此,我们可以利用流标签字段简化IPv6报文分类问题。本文提出了一种基于流标签的IPv6包分类算法——降维排序二叉树算法。本算法使用三元组(源IP地址、目的IP地址、流标签)代替传统的五元组(源IP地址、目的IP地址、源端口、目的端口、协议)来实现IPv6报文分类,以达到简化报文分类的目的。核心思想是对源IP、目的IP进行降维处理后,再用排序二叉树组织复合IP,通过复合IP与流标签来进行分类。排序二叉树是一种利用类字典序方法组织数据的二叉树。与一般的二叉查找树不同,其不包含任何内部空节点,可以达到较好的空间性能。当前缀嵌套关系较少,回溯现象较少发生时也能保证较好的时间性能。本文首先介绍了包分类算法产生的背景和应用、经典的包分类算法的基本原理和特点以及IPv6流标签的定义和相关规定；接着讨论了基于流标签的包分类算法与传统包分类算法的区别及其优势。然后重点描述排序二叉树的排序和建树规则及其搜索步骤,并在此基础上介绍降维排序二叉树算法的原理、实现及性能分析,为报文分类的进一步研究和算法设计提供一定根据和思路。

论文目录

• 摘要
• ABSTRACT
• 第一章 引言
• 1.1 课题背景
• 1.2 课题任务
• 1.3 论文结构
• 第二章 包分类算法概述
• 2.1 INTERNET地址结构的演进
• 2.2 包分类算法的基本概念
• 2.2.1 包分类算法的定义
• 2.2.2 包分类的匹配方式和种类
• 2.2.3 包分类算法的评价标准
• 2.3 包分类算法的应用
• 2.4 经典包分类算法简介
• 2.4.1 采用基本数据结构（Basic Data Structure Algorithms,BS）算法
• 2.4.2 几何算法（Geometric Algorithms,GA）
• 2.4.3 启发式算法（Heuristics Algorithms,HA）
• 2.4.4 基于硬件的算法（Hardware-based Algorithms,HW）
• 第三章 流标签概述
• 3.1 流标签的提出
• 3.2 流标签的定义及使用
• 3.2.1 流标签的定义
• 3.2.2 流标签的基本特征与功能要求
• 3.2.3 流标签的使用
• 3.3 流标签对包分类的支持
• 3.4 应用于DIFFSERV的IPv6流标签技术
• 第四章 基于流标签的降维排序算法介绍及设计
• 4.1 FL-DRST算法综述
• 4.2 降维方法介绍
• 4.3 决策树的构建和查找
• 4.3.1 复合IP的排序规则（类字典序规则）
• 4.3.2 排序规则的改进
• 4.3.3 排序二叉树的建立
• 4.3.4 排序二叉树的查找
• 4.4 排序二叉树的优化
• 4.4.1 平衡化处理
• 4.4.2 消除存储冗余
• 4.5 排序二叉树的更新
• 4.5.1 添加路由规则
• 4.5.2 删除路由规则
• 4.5.3 修改路由规则
• 第五章 基于流标签的降维排序算法的实现
• 5.1 算法的实现环境
• 5.1.1 操作系统和编程语言
• 5.1.2 规则集和流量生成工具和过程
• 5.1.3 编译工具
• 5.2 FL-DRST算法的实现分析
• 5.3 FL-DRST算法的实现过程
• 第六章 基于流标签的降维排序算法的性能分析和测试
• 6.1 算法性能分析
• 6.2 算法性能测试
• 第七章 总结与展望
• 参考文献
• 致谢