包分类是根据数据包的头部字段将数据包按一定规则进行分类的过程,在路由器、防火墙和入侵检测等网络关键设备中均有广泛的应用。包分类技术是因特网提供一切有差别服务和其他新业务的基础。随着网络规模的日益扩大,各种应用以及网络流量迅猛增长,需要网络设备提供更高的带宽和数据分类处理能力。因此,研究高速包分类问题具有重要的现实意义和理论价值。本文首先给出了包分类问题的形式化描述,分析了现实规则库的特点以及包分类算法的衡量标准,最后对多维包分类算法进行了分类总结。在此基础上,分别从软件和硬件两个方面对现有的高速包分类算法进行了研究和改进。RFC算法是软件实现的包分类算法中分类速度较快的一种算法,适合快速多维包分类,但其预处理阶段需要大量的时间。对RFC预处理阶段算法进行了改进,重新设计了等价类的存储方式,采用栈存储等价类,并加入启发式信息提前确定等价类的编号。实验结果表明总的初始化时间比原来减少了90%以上,并且改进后的算法在包分类阶段与RFC算法保持相同的时间复杂度。在改进RFC算法的基础上,提出了一种两阶段索引RFC算法,为每个等价类生成一个索引表。包分类过程分两步完成,先根据预处理表查找与数据包的源IP地址和目的IP地址字段匹配的规则,然后再判断数据包的其他分类字段是否匹配。实验结果表明两阶段索引RFC算法极大地减少了初始化时间,但仍保持了较高的分类速度。TCAM是一种广泛应用于工业领域的硬件包分类设备,在一个时钟周期内就可以完成一次数据包的匹配过程,分类速度较快。但是它不支持范围匹配,必须将具有范围匹配域的规则转化为前缀规则的形式,因而引起了规则数目的膨胀。本文提出了一种TCAM多维分类规则的优化设计方法,在保持每个数据包的处理动作相同的条件下,重新组合规则,将范围类型的规则库转化为一个具有较少条目的前缀规则集合。最后举例说明了其实现过程。