学位论文 > 优秀研究生学位论文题录展示
基于TRIE的软转发路由查找模块的设计实现
作 者: 郭文文
导 师: 曹雪虹
学 校: 南京邮电大学
专 业: 信号与信息处理
关键词: 路由查找 TRIE树 软转发 最长前缀匹配
分类号: TP393.02
类 型: 硕士论文
年 份: 2011年
下 载: 19次
引 用: 0次
阅 读: 论文下载
内容摘要
随着Internet的迅猛发展,其规模、链路速度、带宽、流量等都呈指数级增长,这对路由器的转发性能提出了更高的要求,而转发的重要一步就是查找路由表,故快速的路由查找算法是实现高速数据转发的关键。在常用的路由查找算法中,基于Trie树的算法不仅具有较好的查找速度、空间复杂度和时间复杂度,而且能适应不断提高的路由器性能要求,新颖的现代快速路由查找算法均是在Trie树的基础上通过优化算法实现的。Trie树是实现高速路由查找的关键,是实现各种路由查找优化策略的基础,故基于Trie树的路由查找算法的实现成为软转发路由表查找的一种趋势。本文将围绕如何设计实现高效实用的基于Trie的软转发路由表查找算法这一核心,结合实际路由器的自身配置,在已有算法的基础上提出综合改进的方案,提高路由查找速度,实现对报文高速转发。本文的主要内容如下:1)研究了路由器的基本功能和IP路由选择的流程,分析了Trie结构在IP路由查找算法中的应用,介绍了路由与转发的相关概念,路由表的生成与路由选择的基本原理。2)详细分析了转发模块的框架与流程,研究了转发查询表项的基本结构,详细介绍了转发模块中上下行子模块的设计方案原理和具体流程。3)研究了软转发路由表查找模块对数据转发的重要性,分析了路由表查找算法的研究现状,结合新颖的算法思想设计高效实用的基于TRIE的路由表查找算法。4)根据设计的路由查找算法的实现方法,整合源码实现符合规范要求的路由表查找算法。确定整个路由器软转发模块的解决方案,优化整个模块,最后编译版本上机调试。5)在路由器上实现基于TRIE的软转发路由表查找算法,用测试仪配合路由器来验证软转发功能的实现。根据实验测试结果来分析是否满足用户需求,总结现有方案的利弊,提出改进的方法和后期的展望。
|
全文目录
摘要 4-5 ABSTRACT 5-8 缩略语 8-9 第一章 绪论 9-14 1.1 论文选题意义 9-10 1.2 路由查找算法的研究现状 10-12 1.2.1 传统的路由查找算法 10-11 1.2.2 新颖的路由查找算法 11-12 1.2.3 路由查找目前存在的问题 12 1.3 本文的研究工作和章节安排 12-14 第二章 TRIE结构和路由简介 14-21 2.1 TRIE树概述 14-16 2.1.1 数据结构Trie 14-15 2.1.2 Trie结构的应用 15-16 2.1.3 多分支Trie树 16 2.2 路由 16-18 2.2.1 路由分类 16-17 2.2.2 路由优先级 17 2.2.3 路由度量值 17 2.2.4 路由 17-18 2.3 路由表 18-19 2.3.1 路由表的内容 18 2.3.2 路由表的生成和维护 18-19 2.4 路由选择 19-20 2.4.1 路由表查找 19 2.4.2 最长掩码匹配 19-20 2.5 转发 20-21 第三章 路由转发模块的设计说明 21-29 3.1 路由表的生成和维护 21-22 3.2 IP数据包转发路径 22 3.3 转发需要查询的表项结构 22-24 3.3.1 转发表 23 3.3.2 源MAC表 23-24 3.3.3 ARP表 24 3.4 普通IPV4 包的转发过程 24-28 3.4.1 上行模块介绍 25-26 3.4.2 下行模块介绍 26-28 3.4.3 普通IPv4 包转发数据流图 28 3.5 本章小结 28-29 第四章 基于TRIE的软转发路由表的实现方法 29-48 4.1 软转发路由表实现原理 29-31 4.1.1 IPv4 路由表的索引方式 29-30 4.1.2 VRF路由表的索引方式 30-31 4.2 关键结构设计 31-32 4.3 关键算法设计 32-40 4.3.1 最长匹配算法的实现 32-33 4.3.2 路由查找算法处理流程 33-40 4.4 数据结构描述 40-47 4.4.1 关键数据说明 41-43 4.4.2 数据结构说明 43-46 4.4.3 全局变量说明 46-47 4.5 函数调用关系 47 4.6 本章小结 47-48 第五章 实验环境与结果分析 48-62 5.1 实验环境 48-49 5.1.1 软硬件环境 48 5.1.2 路由器配置 48-49 5.2 实验验证 49-59 5.2.1 添加与删除的实现 49-55 5.2.2 静态路由查找 55-58 5.2.3 动态路由查找 58-59 5.3 结果分析 59-62 第六章 总结与展望 62-64 6.1 研究工作总结 62 6.2 下一步研究计划 62-64 致谢 64-65 参考文献 65-66
|
相似论文
- 多邮件自动文摘的关键技术研究,TP391.1
- 软交换平台下电话号码分类方法研究,TN915.05
- 网络处理器及其处理单元相关技术的研究,TP393.05
- 一种基于哈希策略的路由查找算法,TP393.02
- 基于DHT的结构化P2P路由协议Chord的研究,TP393.02
- IP路由查找算法的研究,TP393.02
- 哈希表和多比特Trie树相结合的IPv6路由查找算法的研究,TP393.02
- IP转发和向量转发性能研究,TP393.05
- 名字路由协议的研究与实现,TP393.04
- 基于DHT的结构化P2P路由协议Chord的研究与改进,TP393.02
- 基于网络处理器的网络伪装技术研究,TP393.08
- 基于HASH路由转发表存储结构的研究,TN915.05
- 高速安全路由器中查找算法的研究,TP393.05
- 高性能路由器中高速转发查表算法研究与实现,TN915.05
- 基于策略的转发系统的设计与实现,TP311.52
- 基于trie的路由查找算法研究,TN915.05
- 高速路由查找算法研究,TP393.02
- 网络处理器原型系统路由查找算法的研究,TP393.05
- 大规模接入汇聚路由器ACR转发表管理软件关键技术研究,TP393.05
- 基于嵌入式的IPv6路由器研究,TN915.05
中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机的应用 > 计算机网络 > 一般性问题 > 计算机网络结构与设计
© 2012 www.xueweilunwen.com
|