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

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2024-10-14

- 基于随机分布的多比特Trie树IP数据包分类算法研究
- Issue 7, Pages: 109-117(2008)
- 作者机构：
  
  1. 重庆邮电大学计算机科学与技术学院
  2. 重庆大学光电工程学院光电技术及系统教育部重点实验室
  3. 浙江大学计算机科学与技术学院
- 作者简介：
- 基金信息：
- DOI：
  CLC： TN915
- Published：2008
- 稿件说明：
移动端阅览
[1]尚凤军,潘英俊,潘雪增,毕斌.基于随机分布的多比特Trie树IP数据包分类算法研究[J].通信学报,2008(07):109-117.

[J]. 2008, (7): 109-117.
[1]尚凤军,潘英俊,潘雪增,毕斌.基于随机分布的多比特Trie树IP数据包分类算法研究[J].通信学报,2008(07):109-117. DOI：

[J]. 2008, (7): 109-117. DOI：

摘要

在无冲突散列算法和多比特Trie树算法的基础上

提出了一种基于随机分布的IP分类算法

该算法的核心有3点:一是基于目的/源端口和协议域构造无冲突散列

由于该三域的组合数目非常少

避免了空间爆炸;二是将目的/源IP连成比特串后分为4块

每块16bit

并将其中一块映射到一随机空间

将随机数和其余3块进行异或

获得分类索引值

并用此值生成多比特Trie树

一般情况下减小了空间和时间复杂度;三是在Trie树终点存放最终分类规则的索引值

为了保证查找到的规则的正确性

对每一个索引值的源/目的IP地址均匹配一次。通过以上3点改进一般要降低算法的时间复杂度和空间复杂度

通过仿真

当对10000条分类规则进行包分类时

该算法的包分类速度可以达到2Mpacket/s

所消耗的最大内存为1MB。

Abstract

关键词

Keywords

references

Views

802

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

完全无冲突散列IP分类算法研究

完全无冲突散列IP分类算法研究附视频

Related Author

尚凤军

唐红

潘英俊

1.重庆大学光电工程学院光电技术及系统教育部重点实验室

2.重庆邮电学院计算机科学与技术学院

3.重庆大学光电工程学院光电技术及系统教育部重点实验室重庆400044重庆邮电学院计算机科学与技术学院

4.重庆400065

5.重庆400065

Related Institution

重庆大学光电工程学院光电技术及系统教育部重点实验室

重庆邮电学院计算机科学与技术学院

重庆大学光电工程学院光电技术及系统教育部重点实验室重庆400044重庆邮电学院计算机科学与技术学院

重庆400065

AI问答

⁰