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

• 作者: 尚凤军 毕斌 潘英俊 潘雪增
• 来源期刊: 通信学报
• 学科: 工学
• 关键词: IP分类 查找算法 多比特Trie树 随机分布
• 年，卷（期）: 2008,（7）
• 所属期刊栏目: 技术报告
• 页码范围: 109-117
• 页数: 9页
• 分类号: TP393.07
• 字数: 7138字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	潘英俊	重庆大学光电工程学院光电技术及系统教育部重点实验室	125	927	14.0	21.0
2	潘雪增	浙江大学计算机科学与技术学院	89	1318	17.0	34.0
3	尚凤军	重庆邮电大学计算机科学与技术学院	39	290	8.0	15.0
4	毕斌	重庆邮电大学计算机科学与技术学院	1	9	1.0	1.0