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

基于HASH路由转发表存储结构的研究

作　者: 王薇
导　师: 梁凤梅
学　校: 太原理工大学
专　业: 电路系统
关键词: HASH 级数定制高速路由查找冲突前缀下一跳
分类号: TN915.05
类　型: 硕士论文
年　份: 2010年
下　载: 50次
引　用: 0次
阅　读: 论文下载

内容摘要

具有高转发能力的路由器是构建高速网络的核心设备,路由器能否实现高性能转发是现在网络发展的关键因素之一。由于路由查找是转发过程中的关键环节,因此路由查找算法的速度直接影响着路由器的报文转发性能,它也成为了制约网络性能提高的主要瓶颈。路由查找技术的研究受到广泛重视,主要归结在两个方面:一是查找速度,二是内存消耗。本文围绕这两个方面,先对路由器的基本工作原理进行了简要介绍,并对现有的路由查找算法进行了综述和分类比较,对它们的空间复杂度和时间复杂度做了分析,在此基础上,针对不同的应用背景和需求提出了两个高性能算法。本文第三章中简单介绍了传统的基于Hash转发表的路由查找算法,并在此基础上进行了改进,提出了一种新的算法——基于可变级数的多级Hash转发表的路由查找算法。该算法首先把多级Hash存储结构思想用在设计转发表结构中,这种存储结构能够明显的降低内存访问次数,通常情况下,两次到三次访存就足够了,从根本上提升了路由查找的速度。其次,实现了级数的可定制性,使得在一套软件系统下,产品用户(路由器开发人员)可以根据路由器形态(内存、性能)在路由查找速度与所耗内存容量二者之间根据自己的需求权衡主次,来选择定制Hash表的级数。另外,本算法提出一种基于“父子关系”的节点添加思想,大大缩短了传统的Hash表查找方式中遍历冲突链的时间,最大限度的提高了查找效率。实验数据表明,该算法在时间上与内存消耗上与传统的算法相比都有明显的提升。本文第四章从转发表的存储结构上对传统的算法进行了改进,提出了对转发结构中的“前缀”和“下一跳”分离的存储结构;然后,对分离后的“前缀”与“下一跳”之间建立关联关系,使它们之间能够彼此快速的定位查找。本算法在空间上大大节省了内存需求;时间上避免了在下一跳地址信息发生改变时重刷转发表项缓慢的问题。实验数据表明本算法达到了优化现有算法的目的。上述两种路由查找算法中,基于可变级数Hash表的方法,既可应用于骨干网中的路由器包括核心路由器的高端路由器中来提高处理频率,又可以用在中等负载能力的中端路由器中,使其在处理速度与内存消耗上达到自己特定的需求,例如H3C公司的SR88路由器。基于分离存储结构的方法,可应用于内存容量不大,或者对内存消耗有限制的中、低端路由器中,例如H3C公司的AR49/39/29系列路由器。

全文目录

摘要  3-5
ABSTRACT  5-9
第一章绪论  9-13
  1.1 Internet 网络的现状  9
  1.2 路由器在Internet 中的应用  9-10
  1.3 论文的研究背景  10-11
  1.4 论文研究内容  11-12
  1.5 论文的组织  12-13
第二章路由查找基础与算法现状分析  13-25
  2.1 报文转发过程中的路由查找  13-19
  2.2 路由查找算法的研究现状  19-24
    2.2.1 基于硬件的路由查找算法  20
    2.2.2 基于Cache 的路由查找算法  20-21
    2.2.3 基于软件的路由查找算法  21-23
    2.2.4 路由查找新算法的研究  23-24
  2.3 评价路由查找算法的标准  24-25
第三章基于可变级数Hash 表路由查找算法的研究  25-48
  3.1 Hash 结构与现有算法分析  25-28
    3.1.1 Hash 表的构造方法  25-26
    3.1.2 Hash 函数的冲突问题  26
    3.1.3 现有的基于Hash 表的路由查找算法  26-28
  3.2 可变级数Hash 表路由查找算法  28-45
    3.2.1 算法的主要思想与所用公式  28-30
    3.2.2 转发表存储结构的定制  30-32
    3.2.3 可变级数Hash 表定制流程  32-33
    3.2.4 算法的路由查找过程  33-41
    3.2.5 算法的路由添加流程  41-45
  3.3 算法实验结果分析及应用  45-47
  3.4 本章小结  47-48
第四章前缀与下一跳分离型存储结构的路由查找算法研究  48-66
  4.1 报文转发过程  48-49
  4.2 转发表存储结构现状分析  49-51
  4.3 算法的思想  51
  4.4 算法的存储结构  51-54
    4.4.1 前缀的存储结构  52
    4.4.2 下一跳地址的存储结构  52-54
    4.4.3 分离型存储结构中前缀与下一跳的关联关系  54
  4.5 基于前缀与下一跳分离型存储结构路由查找算法  54-64
    4.5.1 下一跳存储结构中Key 值的计算公式  54-55
    4.5.2 算法的路由查找过程  55-58
    4.5.3 算法的路由更新过程  58-60
    4.5.4 算法的路由切换过程  60-62
    4.5.5 下一跳的创建、删除、查找主要程序  62-64
  4.6 算法实验结果分析及算法的应用  64-65
  4.7 本章小结  65-66
第五章总结与展望  66-68
  5.1 总结  66-67
  5.2 展望  67-68
参考文献  68-71
致谢  71

基于HASH路由转发表存储结构的研究

内容摘要

全文目录

相似论文