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

超立方体网络容错模型及其路由算法研究

作　者: 张玫
导　师: 刘希玉
学　校: 山东师范大学
专　业: 计算机软件与理论
关键词: 互连网络超立方体容错路由算法
分类号: TP393.01
类　型: 硕士论文
年　份: 2009年
下　载: 60次
引　用: 0次
阅　读: 论文下载

内容摘要

随着计算机网络技术与计算科学的发展,并行计算机及其互连网络作为一个跨数学、计算科学与信息科学等多门学科的领域,逐渐成为计算机科学研究的热点之一,各种拓扑结构的互连网络,如环、Mesh、超立方体、星型网络等得到迅速发展。在一个多处理器互连网络中,处理器之间的有效通信是衡量系统性能的一个重要标准。当处理器数目逐渐增多时,其发生故障的可能性也随之增加,不同处理器之间信息传递过程中的容错性便成为一个非常关键的问题。因此,如何设计新的网络容错模型以便容纳更多的错误结点,以及如何设计高效的容错路由算法以便保证无故障处理器间正确可靠的信息传递是至关重要的。超立方体网络是多处理机系统中常见的一种互连网络,这种网络拓扑结构由于具有直径小、可扩展性强、结构对称、网络寻路算法简单等优点,且多种拓扑结构的互连网络都可以很容易的嵌入其中,因而成为最重要和最具吸引力的网络模型之一。本文基于LIP容错模型和局部连通性,对超立方体网络的容错性和路由算法进行研究,主要研究内容如下:1.给出了超立方体网络及其k维子立方体的概念,同时结合LIP的相关概念和性质,给出了对求解LIP长度的程序的改进,并根据程序的运行结果进行了分析。2.结合第二章最长导出路LIP的概念,提出了超立方体中基于LIP的广播容错路由算法。该算法是基于“超立方体中至少存在一条无故障结点的LIP”的前提条件的,在此条件满足的情况下,超立方体是全局连通的,且该算法能容许大量的错误结点(2^n-1甚至更多),在容错性上有了很大提高。3.基于LIP容错模型和超立方体中的4维子立方体,提出超立方体网络中的一种单播容错路由算法。该算法在必要的搜索时间内,在具有大量错误结点的超立方体网络中找出连接两个正确结点的路径,并且该算法是基于局部信息的,因而具有很好的实际意义。本文在超立方体网络容错模型及路由算法方面作了一些探索工作,取得了一定的结果,但还有大量工作需要研究。首先,进一步研究超立方体网络中的LIP容错模型,给出LIP长度的近似或精确计算公式,以便更好的进行容错分析;其次,深入研究并行计算机互连网络尤其是超立方体网络中的各种容错路由算法,以便结合LIP容错模型,提出更加优越的容错路由算法;再次,对各种容错路由算法进行网络模拟,比如用NS2进行模拟,通过模拟结果对路由算法进行更加深入的分析。

全文目录

摘要  6-8
ABSTRACT  8-10
第一章绪论  10-14
  1.1 课题的研究背景  10-11
  1.2 课题的研究意义  11
  1.3 国内外相关研究现状  11-13
  1.4 本文的主要工作  13-14
第二章超立方体网络及LIP导出嵌入模型  14-23
  2.1 超立方体网络简介  14-17
  2.2 LIP导出嵌入模型  17-20
    2.2.1 相关的定义和记号  17-18
    2.2.2 超立方体网络LIP导出嵌入模型  18-19
    2.2.3 LIP的性质  19-20
  2.3 对求解LIP程序的改进  20-23
    2.3.1 求解LIP的算法及原程序  20-21
    2.3.2 改进程序  21-22
    2.3.3 程序的运行结果及分析  22-23
第三章基于LIP的广播容错路由算法  23-28
  3.1 引言  23-24
  3.2 算法的前提条件  24
  3.3 算法思想  24
  3.4 算法描述  24-25
  3.5 算法分析与评价  25-28
    3.5.1 算法的可行性分析  25-26
    3.5.2 算法的容错性分析  26-28
第四章基于LIP和4维子立方体的单播容错路由算法  28-36
  4.1 概述  28
  4.2 局部连通性  28-31
    4.2.1 局部连通性定义  29-30
    4.2.2 局部连通性隐含的全局连通性  30-31
  4.3 单播容错路由算法  31-36
    4.3.1 算法的前提条件  31-32
    4.3.2 算法思想  32
    4.3.3 算法描述  32-34
    4.3.4 算法分析  34-36
      4.3.4.1 算法的可行性分析  34
      4.3.4.2 算法的容错性分析  34-35
      4.3.4.3 算法的复杂性分析  35
      4.3.4.4 为何选择4维子立方体  35-36
第五章结束语  36-37
  5.1 本文的主要内容  36
  5.2 进一步的研究工作  36-37
参考文献  37-42
附录一求Hypercube中LIP的改进程序  42-45
附录二当n=7时的两条LIP  45-46
攻读硕士学位期间发表的论文  46
攻读硕士学位期间参与的科研项目  46-47
致谢  47

超立方体网络容错模型及其路由算法研究

内容摘要

全文目录

相似论文