近年来,网络技术的发展催生了很多新兴的网络应用,但是现有的网络性能不能很好地支持这些应用。性能良好的包分类算法对于网络性能的提升具有至关重要的作用。网络已经逐渐出现僵化的状态,很大程度上影响了其性能的提升空间。OpenFlow成为互联网创新理念的强大促成者。而OpenFlow网络中由于其灵活性和可扩展性,对包分类的要求更高更复杂,现有研究中很少有专门针对OpenFlow包分类的解决方案,并且在性能上存在一定的局限性。因此,设计一款针对OpenFlow的包分类方案成为当务之急。针对上述问题,本文主要做了以下工作:(1)根据数据挖掘中的聚类思想提出了一种基于无前缀关系聚类的高效层次Trie树结构,该方案依据的是不同前缀关系聚类的方式来消除回溯。算法首先会根据前缀关系来将规则划分为不同的聚类,然后再根据这些聚类来构建多棵层次特里树,在单棵层次特里树中就不存在前缀关系的节点,从而消除了回溯。并且由于算法结构采用了节点的路径压缩策略,该结构在很大程度上提高算法的存储性能。(2)针对OpenFlow的超五元组包分类,本文提出了另一种聚类方式,也就是基于前缀长度聚类的设计方案。该方案根据前缀长度对不同的前缀进行聚类,每个聚类中的前缀都具有相同的前缀长度。然后再选择性地对这些聚类进行合并,进行选择的原则除了满足聚类元素数目的要求,也需要满足合并之后的聚类内部元素之间不具有前缀关系的要求。最后将生成的聚类构建为层次特里树。(3)针对OpenFlow12元组匹配问题,本文设计了一个查找结构,该架构采用过滤方案对12元组中的字段组合依次进行匹配。根据OpenFlow包头解析过程,将所有的字段分为5个搜索引擎。而OpenFlow解析路径显示IP搜索引擎所占比重最多,所以本结构首先通过IP搜索引擎预过滤掉大部分的规则。然后在接下来的少数规则中再选取其他搜索引擎进行进一步查找,得到最终匹配的规则,很大程度上提高了 12元组包分类的效率。