论文题目: 高性能并行计算机互联网络容错模型及其路由算法研究
论文类型: 博士论文
论文专业: 计算机应用技术
作者: 王雷
导师: 林亚平
关键词: 互联网络,超立方体,彼特森图,容错模型,容错路由算法
文献来源: 湖南大学
发表年度: 2005
论文摘要: 由于均具有正则性、对称性、可嵌入性、并行性、以及良好的容错性与网络通信能力的可扩展性等优良特性,超立方体(Hypercube)和彼特森图(Petersen Graph)互联网络受到了研究者们的广泛关注,是迄今为止最为重要和最具吸引力的并行计算机互联网络拓扑结构之一。随着现在的并行计算机互联网络规模越来越大,网络中出现处理机故障或处理机间的链路故障的可能性也越来越大;这就使得并行计算机互联网络的容错性及其研究也变得越来越重要,因此,设计具有较好容错性的路由算法对并行计算机互联网络有着重要意义。 到目前为止,人们已经对超立方体或彼特森图互联网络的拓扑特性及其容错模型与容错路由算法方面分别进行了深入的研究,并基于超立方体或彼特森图互联网络的拓扑特性分别建立了一些容错模型及其容错路由算法,但上述研究均是针对超立方体或彼特森图互联网络单独进行的,缺乏对这两种互联网络系统的综合研究。超立方体和彼特森图互联网络虽然在本质上各不相同,但由于它们均具有正则性、对称性、可嵌入性、并行性、以及良好的容错性与网络通信能力的可扩展性等优良特性,在拓扑特性上具有很大程度的相似性,而且还可以通过相互结合形成具有某些特殊性质的新型互联网络拓扑结构,因此,将超立方体和彼特森图互联网络综合起来进行系统深入的研究,将比对其中的单个网络进行孤立研究具有更好的效果,能更进一步地促进对这两种互联网络乃至整个高性能并行计算机互联网络的研究发展,特别地,取两个网络拓扑特性之长来弥补各自之短,研究如何利用超立方体互联网络的可扩展性和彼特森图互联网络的短直径特性来构造出具有更优特性的新型并行计算机互联网络,将具有重要的研究价值。综上所述,本文综合系统地研究超立方体和彼特森图这两种具有相似拓扑特性的高性能并行计算机互联网络的拓扑特性及其容错模型与容错路由算法。 在对超立方体互联网络的拓扑特性及其容错模型与容错路由算法方面,本文首先综述了目前国内、国际上在超立方体互联网络研究方面所做的主要研究工作,并基于已有的一些研究成果,提出了三种新的超立方体互联网络的容错模型及其容错路由算法:即基于极大安全通路向量的容错模型MSPV(Maximal Safety Path Vector)及其容错路由算法、基于极大安全通路矩阵的容错模型MSPM(Maximal Safety Path Matrix)及其容错路由算法,以及基于两类子连通性的超立方体互联网络容错模型及其容错路由算法;证明了上述超立方体互联网络的容错模型及其容错路由算法分别是基于安全向量的容错模型SV(Safety Vector)、基于扩展安全向量的容错模型ESV(Extended Safety Vector)、基于最优通路矩阵的容错模型OPM(Optimal Path Matrix)、基于扩展最优通路矩阵的容错模型EOPM(Extended
论文目录:
摘要
Abstract
插图索引
附表索引
第1章 绪论
1.1 超立方体与彼特森图互联网络简介
1.1.1 超立方体互联网络简介
1.1.2 彼特森图互联网络简介
1.1.3 超立方体与彼特森图互联网络的比较
1.2 课题的研究意义
1.3 国内外研究现状分析
1.3.1 超立方体与彼特森图网络拓扑特性研究
1.3.2 超立方体和彼特森图网络容错模型研究
1.3.3 超立方体和彼特森图网络容错路由研究
1.4 课题的主要研究内容
1.5 论文的组织结构
第2章 极大安全通路向量容错模型及路由
2.1 概述
2.2 基于极大安全通路向量的容错模型
2.2.1 容错模型的构造
2.2.2 容错模型的性质
2.3 基于极大安全通路向量容错模型的容错路由算法
2.4 算法性能分析及实验结果
2.5 本章小结
第3章 极大安全通路矩阵容错模型及路由
3.1 概述
3.2 基于极大安全通路矩阵的容错模型
3.2.1 容错模型的构造
3.2.2 容错模型的性质
3.3 基于极大安全通路矩阵容错模型的容错路由算法
3.4 算法性能分析及实验结果
3.5 本章小结
第4章 两类子连通性容错模型及路由算法研究
4.1 概述
4.2 基于两类子连通性的容错模型
4.2.1 容错模型的构造
4.2.2 容错模型的性质
4.3 基于两类子连通性容错模型的容错路由算法
4.4 算法性能分析及实验结果
4.5 本章小结
第5章 双环彼特森图互联网络及路由研究
5.1 概述
5.2 双环彼特森图互联网络
5.2.1 双环彼特森图互联网络的构造
5.2.2 双环彼特森图互联网络的性质
5.3 双环彼特森图互联网络的路由算法研究
5.3.1 双环彼特森图互联网络上的单播路由算法
5.3.2 双环彼特森图互联网络上的广播路由算法
5.3.3 双环彼特森图互联网络上的容错路由算法
5.4 算法性能分析及实验结果
5.4.1 单播路由算法的性能分析
5.4.2 广播路由算法的性能分析
5.4.3 容错路由算法的性能分析
5.5 本章小结
第6章 层次双环彼特森图互联网络及路由
6.1 概述
6.2 层次双环彼特森图互联网络
6.2.1 层次双环彼特森图互联网络的构造
6.2.2 层次双环彼特森图互联网络的性质
6.3 层次双环彼特森图互联网络的路由算法研究
6.3.1 层次双环彼特森图互联网络上的单播路由算法
6.3.2 层次双环彼特森图互联网络上的广播路由算法
6.3.3 层次双环彼特森图互联网络上的容错路由算法
6.4 算法性能分析及实验结果
6.4.1 单播路由算法的性能分析
6.4.2 广播路由算法的性能分析
6.4.3 容错路由算法的性能分析
6.5 本章小结
第7章 超立方体连接的彼特森图互联网络
7.1 概述
7.2 超立方体连接的彼特森图互联网络
7.2.1 超立方体连接的彼特森图互联网络的构造
7.2.2 超立方体连接的彼特森图互联网络的性质
7.3 超立方体连接的彼特森图网络路由研究
7.3.1 超立方体连接的彼特森图网络的单播路由算法
7.3.2 超立方体连接的彼特森图网络的广播路由算法
7.3.3 超立方体连接的彼特森图网络的容错路由算法
7.4 算法性能分析及实验结果
7.4.1 单播路由算法的性能分析
7.4.2 广播路由算法的性能分析
7.4.3 容错路由算法的性能分析
7.5 本章小结
结论
参考文献
致谢
附录A(攻读学位期间所发表的学术论文目录)
附录B(传感器网络中基于层次超立方体模型的对偶密钥建立算法)
发布时间: 2005-09-27
相关论文
- [1].计算机网络中的多播路由算法[D]. 刘莹.西安电子科技大学2000
- [2].高性能计算机互连系统研究[D]. 邓波.中国人民解放军国防科学技术大学2000
- [3].具有大量错误结点的超立方体网络容错模型和容错路由算法研究[D]. 王国军.中南大学2002
- [4].故障诊断与容错控制方法研究[D]. 王德军.吉林大学2004
- [5].移动环境下的容错和安全路由技术研究[D]. 蒋廷耀.华中科技大学2004
- [6].容错实时系统可调度性分析研究[D]. 王磊.浙江大学2005
- [7].规则网络容错路由算法及可靠组播的研究[D]. 张祖平.中南大学2005
- [8].Mesh网络容错性的概率分析研究[D]. 王高才.中南大学2004
- [9].基于寄生式故障检测的分布式并行服务器系统容错技术[D]. 左朝树.电子科技大学2005
- [10].高效并行计算系统中的计算模型与通信网络[D]. 刘方爱.中国科学院研究生院（计算技术研究所）2001