浏览全部资源
扫码关注微信
1. 重庆邮电大学计算机科学与技术学院
2. 重庆大学光电工程学院光电技术及系统教育部重点实验室
3. 浙江大学计算机科学与技术学院
纸质出版日期:2008
移动端阅览
[1]尚凤军,潘英俊,潘雪增,毕斌.基于随机分布的多比特Trie树IP数据包分类算法研究[J].通信学报,2008(07):109-117.
[1]尚凤军,潘英俊,潘雪增,毕斌.基于随机分布的多比特Trie树IP数据包分类算法研究[J].通信学报,2008(07):109-117. DOI:
DOI:
在无冲突散列算法和多比特Trie树算法的基础上
提出了一种基于随机分布的IP分类算法
该算法的核心有3点:一是基于目的/源端口和协议域构造无冲突散列
由于该三域的组合数目非常少
避免了空间爆炸;二是将目的/源IP连成比特串后分为4块
每块16bit
并将其中一块映射到一随机空间
将随机数和其余3块进行异或
获得分类索引值
并用此值生成多比特Trie树
一般情况下减小了空间和时间复杂度;三是在Trie树终点存放最终分类规则的索引值
为了保证查找到的规则的正确性
对每一个索引值的源/目的IP地址均匹配一次。通过以上3点改进一般要降低算法的时间复杂度和空间复杂度
通过仿真
当对10000条分类规则进行包分类时
该算法的包分类速度可以达到2Mpacket/s
所消耗的最大内存为1MB。
0
浏览量
209
下载量
2
CSCD
关联资源
相关文章
相关作者
相关机构