随着Internet规模的日益扩大,各种网络应用的数据流迅猛增长,传统路由器单一的“尽力”服务方式已不能满足要求。这一切都对作为Internet核心设备的主干路由器提出了新的要求,需要如资源预留服务、QoS(Quality of Service)服务、虚拟专用网、基于策略的路由等新的“差别”服务机制。而所有这些“差别”服务机制都需要路由器对IP包进行分类,根据数据包头部的内容把数据包归类为某个流的过程称为数据包分类。在路由器等网络设备中,所有属于同一个流的数据包遵循一套预先定义好的规则,并按照类似的方式进行处理。数据包分类系统要求对输入的任何网络信息包与数据库中的规则相匹配。根据匹配的结果,按照符合最高优先级的规则来处理输入的信息包。本文首先介绍了目前常用的数据包分类算法,分析了各个算法的优缺点。在此基础上,通过对现有算法分析,提出了一种在高端路由器上实现快速数据包分类的算法,即利用网络处理器的并行处理能力和RFC算法(Recursive Flow Classification,递归流分类)中等价类的思想,结合Hash水平查找和垂直查找,实现了支持动态更新的多维高速数据包分类算法。本文给出了该算法实现的关键技术,包括eqid映射,CBM值的改进,和Hash冲突的解决。通过对算法的功能和性能进行测试,本算法同现存的路由器上应用的RFC算法相比,在空间复杂度和时间复杂度上都有很大的提高,并且该算法的查找时间与规则库的规模无关。实验结果与理论分析相吻合,达到了预期的效果。