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

基于trie的路由查找算法研究

作　者: 赵永精
导　师: 宋健
学　校: 兰州理工大学
专　业: 通信与信息系统
关键词: IP路由查找最长前缀匹配 trie树
分类号: TN915.05
类　型: 硕士论文
年　份: 2007年
下　载: 229次
引　用: 0次
阅　读: 论文下载

内容摘要

由于Internet的飞速发展，网络用户数目的增长，多媒体网络应用日益广泛，网络流量呈爆炸式的增长趋势。Internet若要想继续提供较好的服务，要求核心路由器每秒能转发几百万个以上的分组，快速路由查找技术成为路由器报文转发的瓶颈。因此如何实现高速路由表的查找和更新是研究的难点。同时随着IPv6技术的逐步成熟和推广，也进一步要求提升路由查找的性能。文章在通过对近年来提出的各种路由查找方法进行详细阐述基础上，对各种算法的性能以及对IPv6的适应性进行了分析，结果发现trie数据结构是实现高速路由查找和报文转发的关键，且trie算法具有易于与硬件结合的特点，因此提出基于trie的最长前缀的查找算法。该算法中某些节点包含多条路由信息，减少了trie树的节点数目。这样大大减少了存储空间。考虑到当前路由表中前缀分布的特点，改进后的算法降低了树的高度。同时，该算法能够应用于IPv6网络。尤其适于当前快速变化的Internet更新要求。总之，该算法不仅保障了路由表的快速查找，同时在执行更新操作时，不需要重新构建路由表。这种算法用到IPv6同样收到很好大效果，因此，它可以兼顾IPv4／IPv6网络。最后，作者总结全文，综合了作者在该课题研究中的主要成果，并且提出了需要进一步研究和讨论的问题。

全文目录

摘要  7-8
Abstract  8-9
插图索引  9-10
附表索引  10-11
第1章绪论  11-23
  1.1 研究背景  11-14
  1.2 路由器的基本原理及体系结构  14-17
    1.2.1 路由器在IP网络中的位置  14
    1.2.2 路由器结构体系  14-15
    1.2.3 路由器的作用  15-16
    1.2.4 路由器工作原理  16
    1.2.5 路由器性能分析  16-17
    1.2.6 路由器性能小结  17
  1.3 路由查找现状  17-18
  1.4 路由查找算法的设计标准  18-21
  1.5 本文的意义  21
  1.6 本文的内容安排  21-23
第2章常用路由查找算法总结  23-43
  2.1 发展前由  23-26
  2.2 路由查找相关的几个定义  26-27
  2.3 常用路由查找算法分析  27-40
    2.3.1 基于硬件的查找算法分析  27-30
    2.3.2 基于trie结构的软件的查找算法分析  30-37
    2.3.3 基于表结构(包括线性表和散列表)的软件的查找算法分析  37-40
  2.4 小结  40-43
    2.4.1 算法复杂度的评价  41
    2.4.2 算法的硬件实现灵活性评价  41
    2.4.3 算法的可扩展性评价  41-43
第3章基于trie的最长前缀算法设计与实现  43-52
  3.1 算法概述  43
  3.2 算法涉及的主要操作  43-44
  3.3 算法逻辑结构的实现  44-49
    3.3.1 路由表的构建  45-47
    3.3.2 报文查找算法  47
    3.3.3 路由更新操作  47-49
  3.4 算法的改进  49-51
  3.5 分析与小结  51-52
第4章总结与展望  52-53
  4.1 全文总结  52
  4.2 对后续工作的展望  52-53
参考文献  53-56
致谢  56-57
附录A 攻读学位期间所发表的学术论文目录  57

基于trie的路由查找算法研究

内容摘要

全文目录

相似论文