随着网络技术的飞速发展以及网络应用的层出不穷,互联网用户对网络服务的可靠性,安全性,多样性都提出了更深层次的诉求。路由器需要提供有差别的网络服务才能满足不同用户的需求,如包过滤防火墙,流量计费,区分服务,QoS等。为了支撑这些有差别的服务,路由器必须快速地对数据包进行分类处理。采用快速的包分类算法已经成为高速路由器的一项关键技术,也是避免路由器成为网络性能瓶颈的关键。本文在研究了众多不同类型的包分类算法基础上,对基于折半层次搜索的包分类算法和基于独立集合的包分类算法进行了优化和改进,提高了算法的运行速度,并给出了对比实验结果。折半层次搜索(BSOL,Binary Search On Levels)算法是一种时间上高效的包分类算法。但由于其核心思想是为特里树(Trie)每一层创建hash表,因此当hash装载因子较大或hash冲突较大时,会严重影响其效率。为了解决这一问题,本文通过引入布鲁姆过滤器,提出了一种新的改进算法。改进后的折半层次搜索算法将为Trie树的每一层建立了一个布鲁姆过滤器,在进行hash查找之前先进行一次布鲁姆查询运算,能够保障在hash装载因子较大的情况下依然具有良好的性能。仿真实验结果表明,在数据包的命中率低于90%并且hash装载因子较大的情况下改进后的算法在运行时间上要优于BSOL算法。基于独立集合(IS,Independent Sets)的算法是一种空间上高效的算法,该算法只需要对规则区间的起点进行处理。然而在构建独立集合的过程中,算法缺乏对规则优先级的特殊考虑,所以在数据包的线性匹配过程中会影响算法的执行效率,本文针对此缺点对IS算法进行了改进,提出了一种进行优先级排序的独立集合算法。改进后的独立集合算法能保证在线性匹配过程中,第一个与数据包匹配的规则就是最终采用的规则,不再需要遍历整个规则索引表。仿真实验结果表明,改进后的算法在运行时间上要优于IS算法。同时本文也指出了IS算法在动态更新中创建新独立集合过于频繁的缺点,提出了一种通过切分规则以提高存储效率的改进设想。