基于TRIE的软转发路由查找模块的设计实现

论文摘要

随着Internet的迅猛发展,其规模、链路速度、带宽、流量等都呈指数级增长,这对路由器的转发性能提出了更高的要求,而转发的重要一步就是查找路由表,故快速的路由查找算法是实现高速数据转发的关键。在常用的路由查找算法中,基于Trie树的算法不仅具有较好的查找速度、空间复杂度和时间复杂度,而且能适应不断提高的路由器性能要求,新颖的现代快速路由查找算法均是在Trie树的基础上通过优化算法实现的。Trie树是实现高速路由查找的关键,是实现各种路由查找优化策略的基础,故基于Trie树的路由查找算法的实现成为软转发路由表查找的一种趋势。本文将围绕如何设计实现高效实用的基于Trie的软转发路由表查找算法这一核心,结合实际路由器的自身配置,在已有算法的基础上提出综合改进的方案,提高路由查找速度,实现对报文高速转发。本文的主要内容如下:1)研究了路由器的基本功能和IP路由选择的流程,分析了Trie结构在IP路由查找算法中的应用,介绍了路由与转发的相关概念,路由表的生成与路由选择的基本原理。2)详细分析了转发模块的框架与流程,研究了转发查询表项的基本结构,详细介绍了转发模块中上下行子模块的设计方案原理和具体流程。3)研究了软转发路由表查找模块对数据转发的重要性,分析了路由表查找算法的研究现状,结合新颖的算法思想设计高效实用的基于TRIE的路由表查找算法。4)根据设计的路由查找算法的实现方法,整合源码实现符合规范要求的路由表查找算法。确定整个路由器软转发模块的解决方案,优化整个模块,最后编译版本上机调试。5)在路由器上实现基于TRIE的软转发路由表查找算法,用测试仪配合路由器来验证软转发功能的实现。根据实验测试结果来分析是否满足用户需求,总结现有方案的利弊,提出改进的方法和后期的展望。

论文目录

• 摘要
• ABSTRACT
• 缩略语
• 第一章 绪论
• 1.1 论文选题意义
• 1.2 路由查找算法的研究现状
• 1.2.1 传统的路由查找算法
• 1.2.2 新颖的路由查找算法
• 1.2.3 路由查找目前存在的问题
• 1.3 本文的研究工作和章节安排
• 第二章 TRIE结构和路由简介
• 2.1 TRIE树概述
• 2.1.1 数据结构Trie
• 2.1.2 Trie结构的应用
• 2.1.3 多分支Trie树
• 2.2 路由
• 2.2.1 路由分类
• 2.2.2 路由优先级
• 2.2.3 路由度量值
• 2.2.4 路由
• 2.3 路由表
• 2.3.1 路由表的内容
• 2.3.2 路由表的生成和维护
• 2.4 路由选择
• 2.4.1 路由表查找
• 2.4.2 最长掩码匹配
• 2.5 转发
• 第三章 路由转发模块的设计说明
• 3.1 路由表的生成和维护
• 3.2 IP数据包转发路径
• 3.3 转发需要查询的表项结构
• 3.3.1 转发表
• 3.3.2 源MAC表
• 3.3.3 ARP表
• 3.4 普通IPV4 包的转发过程
• 3.4.1 上行模块介绍
• 3.4.2 下行模块介绍
• 3.4.3 普通IPv4 包转发数据流图
• 3.5 本章小结
• 第四章 基于TRIE的软转发路由表的实现方法
• 4.1 软转发路由表实现原理
• 4.1.1 IPv4 路由表的索引方式
• 4.1.2 VRF路由表的索引方式
• 4.2 关键结构设计
• 4.3 关键算法设计
• 4.3.1 最长匹配算法的实现
• 4.3.2 路由查找算法处理流程
• 4.4 数据结构描述
• 4.4.1 关键数据说明
• 4.4.2 数据结构说明
• 4.4.3 全局变量说明
• 4.5 函数调用关系
• 4.6 本章小结
• 第五章 实验环境与结果分析
• 5.1 实验环境
• 5.1.1 软硬件环境
• 5.1.2 路由器配置
• 5.2 实验验证
• 5.2.1 添加与删除的实现
• 5.2.2 静态路由查找
• 5.2.3 动态路由查找
• 5.3 结果分析
• 第六章 总结与展望
• 6.1 研究工作总结
• 6.2 下一步研究计划
• 致谢
• 参考文献