包分类是下一代因特网网络设备(如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流标签的定义和相关规定；接着讨论了基于流标签的包分类算法与传统包分类算法的区别及其优势。然后重点描述排序二叉树的排序和建树规则及其搜索步骤,并在此基础上介绍降维排序二叉树算法的原理、实现及性能分析,为报文分类的进一步研究和算法设计提供一定根据和思路。