基于多分支Trie的虚拟路由查找算法研究

摘要

近年来，网络服务日趋多样化，虚拟路由技术是解决此难题的一种有效方案。然而，路由器的有限的存储空间限制了其并发运行虚拟路由的数量，此外，多个虚拟路由的并发运行易导致其IP查找性能下降，给虚拟路由技术的各种应用带来了巨大困难。因此，如何合理设计虚拟路由转发表的结构，保证高性能的IP查找，成为虚拟路由技术中亟待解决的问题。本文围绕Trie结构的虚拟路由查找算法转开研究，主要工作如下：
　　首先，研究虚拟路由技术中基于Trie结构的各虚拟路由转发表合并的问题。针对单比特位的共享转发表易导致Trie结构臃肿，查找效率不高的问题，提出了一种基于多分支Trie的动态共享转发表结构，并在此结构上实现了相应的虚拟路由IP查找算法。该结构采用多比特位的IP查找，减少了转发表中结构性消耗及访存次数，并可动态调整Trie每层节点的步长值。实验表明，与已有的结构相比，动态共享转发表能够节省大量的存储空间。
　　其次，本文研究转发表的空间消耗与Trie步长值选取之间的关系。针对不同的规则集分布，如何构造最少空间消耗的动态共享转发表的问题，提出了一种基于动态规划思想的Trie自适应步长划分算法，算法通过统计转发规则集中转发规则长度的分布情况，自动地为每一层Trie节点选择合适的步长值，进一步节省动态共享转发表的空间开销。实验表明，算法能准确的计算出每层Trie节点合适的步长值，与固定步长方式构造转发表相比，能节省更多的存储空间。
　　最后，结合以上研究工作，设计并开发了基于动态共享转发表的仿真工具软件，评价所提出的转发表结构的空间消耗与IP查找性能。仿真工具主要针对动态共享转发表的空间消耗及IP查找性能指标进行统计和监控，具有易用性与可扩展性。

目录

文摘

英文文摘

插图索引

附表索引

第1章 绪论

1.1 研究背景及意义

1.2 研究内容

1.3 本文主要工作

1.4 本文结构

第2章 相关研究综述

2.1 前言

2.2 路由器概述

2.2.1 路由器的特点与结构

2.2.2 路由器的功能

2.2.3 路由器的工作原理

2.3 虚拟路由器的研究现状

2.3.1 转发表空间消耗问题

2.4 基于Trie转发表结构的研究现状

2.5 小结

第3章基 于多分支Trie的动态共享转发表的构造

3.1 前言

3.2 共享转发表结构分析

3.3 动态共享转发表

3.3.1 转发表结构

3.3.2 构造算法

3.3.3 更新算法

3.3.4 IP查找算法

3.3.5 结构分析

3.4 仿真实验结果分析

3.4.1 实验环境与参数设置

3.4.2 空间消耗对比

3.4.3 IP查找时间对比

3.5 小结

第4章 基于动态规划思想的自适应步长划分算法

4.1 前言

4.2 问题描述

4.3 自适应步长划分算法

4.3.1 算法思想

4.3.2 算法模型

4.3.3 算法实现

4.4 应用实例

4.5 仿真实验与结果分析

4.5.1 空间消耗对比

4.5.2 IP查找时间对比

4.6 小结

第5章 基于动态共享转发表的仿真工具的设计与实现

5.1 前言

5.2 功能描述

5.3 设计模式

5.4 模块设计与实现

5.4.1 转发规则采集模块

5.4.2 IP分组采集模块

5.4.3 Trie构造模块

5.4.4 自适应步长处理模块

5.4.5 IP查找模块

5.4.6 数据统计模块

5.4.7 数据监控模块

5.4.8 仿真数据显示模块

5.5 应用演示

5.6 小结

结 论

参考文献

致谢

附录A 攻读硕士期间发表的论文目录