超立方体 组播 容错 可达性信息 局部k维子立方体.doc

超立方体论文：超立方体网络中容错组播的研究

【中文摘要】超立方体互连网络具有正规性、对称性、强容错性、直径短、可嵌入性等优点,是人们最早研究且仍是目前最重要的互连网络拓扑结构之一。高性能计算机系统规模的不断扩大,导致网络中结点出错的概率也大大增加。局部k维子立方体连通的超立方体容错模型是目前超立方体网络上容错能力最强的容错模型。在对国内外研究现状进行深入分析的基础上,本文对带有错误结点的超立方体网络上的容错组播算法以及相关问题进行了研究。首先,介绍了基于可达性模型的容错组播算法。在分析了原有算法的不足之处的基础上,本文改进基于可达性模型容错组播算法。该算法是一个混合式算法,采用了分治的思想解决组播问题。将每一个子立方体看作是一个正确的结点,在组播的源结点上对组播结点进行处理,将位于同一个子立方体的相邻结点链接,将相邻子立方体放在同一条路径上。在立方体之间的组播采用Sheu’s组播树算法的变体构造组播树主干,在子立方体内再次组播以完成一次组播过程。同时考虑结点的加入和离开对组播树的影响,提出组播树的维护机制。其次,针对网络中相邻结点需要交换路由信息来更新路由表以达到感知非相邻结点的状态的问题,介绍了基于可达性模型的路由表更新算法,并对它进行详细分析。.
【英文摘要】Hypercube interconnection network has the advantages of normality, great ability of fault tolerance, short diameter, embeddability and so on, it’s one of the most popular, versatile and efficient topological structures of inter- connection networks. With the increace of the network size, the possibility of node failture also increases. The locally k-subcube-connected hypercube is the fault tolerant model for hypercube, whose ability of fault tolerance is much greater than others. Based on the analysis of th...
【关键词】超立方体 组播 容错 可达性信息 局部k维子立方体
【英文关键词】Hypercube Multicast Fault-tolerance Reachability information Locally k-subcube-connected
【索购全文】联系Q1：138113721 Q2：139938848

【目录】超立方体网络中容错组播的研究

摘要

5-6

Abstract

6-7

第1章 绪论

11-19

1.1 研究背景

11-12

1.2 互连网络

12-13

1.2.1 互连网络的分类

12

1.2.2 通信模式

12-13

1.2.3 路由算法

13

1.3 容错通信的必要性

13-14

1.4 国内外研究现状

14-17

1.4.1 超立方体网络

14-15

1.4.2 容错模型

15-17

1.4.3 容错组播

17

1.5 本文研究的主要内容和结构安排

17-19

第2章 基础知识

19-29

2.1 超立方体网络

19-21

2.1.1 超立方体及相关定义

19-20

2.1.2 超立方体的构造方法

20-21

2.2 局部k 维子立方体连通模型

21-23

2.2.1 局部k 维子立方体概述

21-22

2.2.2 局部k 维子立方体连通模型及相关定义

22

2.2.3 有关局部k 维子立方体连通模型的定理和推论

22-23

2.3 局部k 维子立方连通超立方体的可达性模型

23-27

2.3.1 可达性模型的定义

23-24

2.3.2 路由表的结构

24-26

2.3.3 可达结点与外连结点的关系

26

2.3.4 可达性模型性质

26-27

2.4 超立方体网络中的经典组播算法

27-28

2.4.1 LEN’s 组播树算法

27

2.4.2 Sheu’s 组播树算法

27-28

2.5 本章小结

28-29

第3章 基于可达性模型的容错组播算法的改进

29-49

3.1 超立方体网络中容错组播的思路分析

29-31

3.2 基于可达性模型的容错组播算法

31-33

3.2.1 算法思想

31-32

3.2.2 算法描述

32-33

3.3 基于可达性模型的容错组播算法分析

33-34

3.4 改进的容错组播算法

34-46

3.4.1 算法思想

34-35

3.4.2 算法描述

35-39

3.4.3 算法及复杂度分析

39-40

3.4.4 实例分析

40-46

3.5 组播树的维护机制

46-48

3.5.1 结点的加入

46-47

3.5.2 结点的退出

47-48

3.6 本章小结

48-49

第4章 路由表优化更新算法

49-59

4.1 引言

49

4.2 基于可达性模型的路由表更新算法

49-51

4.2.1 路由表的初始化

49-50

4.2.2 本地结点向其邻结点发送消息

50

4.2.3 本地结点收到来自邻结点的消息

50-51

4.2.4 邻结点在阈值时间内无消息发送

51

4.3 现有的路由更新算法分析

51-52

4.4 路由表优化更新算法

52-57

4.4.1 路由表优化更新的思想

52-53

4.4.2 路由更新包

53-54

4.4.3 路由表的初始化

54

4.4.4 邻结点可达性测试

54-55

4.4.5 路由表信息交换：消息发送

55-56

4.4.6 路由表信息交换：消息到达

56-57

4.5 算法复杂度分析

57

4.6 错误结点的判定

57-58

4.7 本章小结

58-59

第5章 仿真实验与性能分析

59-69

5.1 OMNET++仿真平台

59-62

5.1.1 OMNET++的特点

59-60

5.1.2 OMNET++的原理

60-61

5.1.3 OMNET++的仿真流程

61-62

5.2 仿真场景与性能指标

62-63

5.2.1 实验设置

62-63

5.2.2 性能指标介绍

63

5.3 改进的容错组播算法性能测试与分析

63-66

5.4 路由表优化更新算法测试与分析

66-68

5.5 本章小结

68-69

结论

69-71

参考文献

71-75

攻读硕士学位期间承担的科研任务与主要成果

75-76

致谢

76-77

作者简介

77