网络新业务的不断出现,对网络传输速度提出了越来越高的要求。为适应这些新变化,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)。详细地给出了该算法的基本思想、预处理过程、包匹配过程,并对规则优先权给出了明确的定义。经理论分析与仿真实验证明,该算法是一个综合性能较高的算法。