学位论文 > 优秀研究生学位论文题录展示

基于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

相似论文

  1. 多邮件自动文摘的关键技术研究,TP391.1
  2. 软交换平台下电话号码分类方法研究,TN915.05
  3. 网络处理器及其处理单元相关技术的研究,TP393.05
  4. 一种基于哈希策略的路由查找算法,TP393.02
  5. 基于DHT的结构化P2P路由协议Chord的研究,TP393.02
  6. IP路由查找算法的研究,TP393.02
  7. 哈希表和多比特Trie树相结合的IPv6路由查找算法的研究,TP393.02
  8. IP转发和向量转发性能研究,TP393.05
  9. 名字路由协议的研究与实现,TP393.04
  10. 基于DHT的结构化P2P路由协议Chord的研究与改进,TP393.02
  11. 基于网络处理器的网络伪装技术研究,TP393.08
  12. 基于HASH路由转发表存储结构的研究,TN915.05
  13. 高速安全路由器中查找算法的研究,TP393.05
  14. 高性能路由器中高速转发查表算法研究与实现,TN915.05
  15. 基于策略的转发系统的设计与实现,TP311.52
  16. 基于trie的路由查找算法研究,TN915.05
  17. 高速路由查找算法研究,TP393.02
  18. 网络处理器原型系统路由查找算法的研究,TP393.05
  19. 大规模接入汇聚路由器ACR转发表管理软件关键技术研究,TP393.05
  20. 基于嵌入式的IPv6路由器研究,TN915.05

中图分类: > 工业技术 > 自动化技术、计算机技术 > 计算技术、计算机技术 > 计算机的应用 > 计算机网络 > 一般性问题 > 计算机网络结构与设计
© 2012 www.xueweilunwen.com