迅速发展的云计算技术与大数据技术使得互联网承载着越来越多的应用业务,数据规模大幅扩增,尽力而为的传统网络服务根本满足不了广大用户的需求。包分类技术是下一代互联网络设备提供多种应用服务的关键技术,所以快速地进行数据包分类对于网络发展具有重大意义。目前,研究人员开始将包分类的研究领域转向更广泛的范围,而数据挖掘中的聚类思想可以很好地解决包分类领域中遇到的问题。基于聚类的包分类算法通常引入聚类分析理论对包分类问题形式化分析,利用规则的聚集特征来设计高效、灵活的包分类结构、算法和机制,以提升包分类技术的综合性能。近年来,IPv4地址短缺,未来互联网的发展离不开对IPv6的支持和应用。因此设计一种简单且能支持IPv4和IPv6的包分类算法,是一个极富挑战的工作。针对上述问题,本文做了以下工作:(1)提出了基于地址前缀长度和聚类的包分类算法。通过分析及利用真实IPv4规则的聚集特征,该算法设计了一种高效的混合层次搜索结构:第一层结构根据规则的源/目的地址前缀长度和进行聚类,并依据所得聚类以及聚类中规则的最高优先级建立一棵基于优先级剪枝的搜索树,每个聚类为搜索树中的一个有效结点。针对传统的四向树算法搜索结构中存在大量的空白结点,极大浪费内存空间的问题,算法第二层结构为每个聚类建立一棵基于优先级的四向树,该优先级四向树将优先级高的规则放到四向树中较低层次的空结点,从而压缩了中间的空白结点,加快了数据包查找速度。(2)提出了基于优先级Trie树的IPv6包分类算法。通过对真实网络中的IPv6规则进行研究与分析发现:IPv6规则的源/目的地址前缀的前16位前缀值约有9种;大多数规则的源/目的地址前缀是以前缀值0x2001开头的,其余前缀值的规则是极少的;规则的源/目的地址前缀长度少于16也是极少的。根据这些特征,算法从规则的源/目的地址前缀的第17位开始进行降维,即对源/目的地址前缀进行按位异或运算,最后得一复合IP地址前缀,并根据这复合IP地址前缀构建优先级Trie树。优先级Trie树将优先级高的规则提前放置在Trie树中较低层次的空结点,节约了内存空间,减少了 Trie树的深度,解决了 Trie树搜索速度不佳的问题。