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

作     者：尚凤军 潘英俊 潘雪增 毕斌 

作者机构：重庆邮电大学计算机科学与技术学院重庆400065 重庆大学光电工程学院光电技术及系统教育部重点实验室重庆400044 浙江大学计算机科学与技术学院浙江杭州310027 

出 版 物：《通信学报》 (Journal on Communications)

年 卷 期：2008年第29卷第7期

页      面：109-117页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：重庆市教委科技项目资助(KJ080526) 

主　　题：IP分类 查找算法 多比特Trie树 随机分布 

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