摘要:随着网络的发展,客户终端要求网络服务提供商提供更有价值的服务,包括包过滤、流量计费和更好的服务质量(QoS)等等,所有这些都需要IP分类技术.本文在无冲突哈希算法和Lakshman and Stiliadis提出的二维分类算法(简记为LS算法)的基础上,提出了一种串行无冲突哈希(SNH,Serial and Non-collision Hash)的IP分类算法,该算法的核心有三点:一是基于目的端口和协议域构造无冲突哈希,完全避免了空间爆炸;二是在LS算法的基础上,将目的IP层中引入多比特Trie树,一般情况下减小了空间和时间复杂度;三是串行查找源端口.通过以上三点改进一般要降低算法的时间复杂度和增大空间复杂度,在本文中主要通过引入多比特Trie树和LS算法的方法进行解决.通过仿真,当对1万条分类规则进行包分类时,该算法的包分类速度可以达到1Mpps,所消耗的最大内存为10MB.