基于随机分布的多比特Trie树IP数据包分类算法研究

摘要

在无冲突散列算法和多比特Trie树算法的基础上,提出了一种基于随机分布的IP分类算法,该算法的核心有3点:一是基于目的,源端口和协议域构造无冲突散列,由于该三域的组合数目非常少,避免了空间爆炸;二是将目的/源IP连成比特串后分为4块,每块16bit,并将其中一块映射到一随机空间,将随机数和其余3块进行异或,获得分类索引值,并用此值生成多比特Trie树,一般情况下减小了空间和时间复杂度;三是在Trie树终点存放最终分类规则的索引值,为了保证查找到的规则的正确性,对每一个索引值的源,目的IP地址均匹配一次.通过以上3点改进一般要降低算法的时间复杂度和空间复杂度,通过仿真,当对10 000条分类规则进行包分类时,该算法的包分类速度可以达到2Mpaekut/s,所消耗的最大内存为1MB.