基于结构故障的k-元n-立方体网络的容错性研究

发布时间：2020-11-06 09:46

　　 在并行分布式系统中,多处理器之间连接的拓扑结构(互连网络)至关重要,它直接影响到并行分布式系统的性能和功能的实现。k-元n-立方体网络是最常用的互连网络之一,它具有许多好的性质,比如易运行、低延迟、高带宽等。许多并行分布式系统都是用k-元n-立方体网络(表示为Q_n~k)作为其连接模式,如IBM BlueGene/L超级计算机,J-machine,Cray T3D 和Cray T3E。互连网络可以表示为一个图,图的顶点表示系统中的处理器,边表示处理器之间的通信链路。在实际的应用系统中,设备或通信链路发生故障是在所难免的。当网络出现故障时,如何使得网络能够正常地工作,原网络的性能如何得到最大程度的保持,即容错性,是互连网络研究必须考虑的问题。网络中存在多少数量的故障元素,网络仍然是连通的(即连通度问题),任意两个无故障顶点之间是否存在无故障路径与如何构造(即容错路由问题),是否存在包含每一个无故障顶点一次且仅一次的路或者圈(即容错哈密顿性质问题)。这些都是互连网络容错性研究中需要首先解决的问题。本文从这三个方面研究k-元n-立方体网络的容错性。已有的容错性研究主要是针对故障元素是顶点或者边。在实际应用中,故障点和边的分布可能比较集中或局部化,即故障元素可以看成是图的子结构,这类故障称为结构故障。本文研究在存在结构故障的情况下,k-元n-立方体网络的容错性,包含以下内容:1.k-元n-立方体网络的结构连通度和子结构连通度(1)证明了当k = 3时,k-元n-立方体网络的K_(1,1)-结构连通度和K_(1,1)-子结构连通度都是n;当k= 4时,k-元n-立方体网络的K_(1,1)-结构连通度和K_(1,1)-子结构连通度都是2n-1;当k≥5时,k-元n-立方体网络的K_(1,1)-结构连通度和K_(1,1)-子结构连通度都是2n。(2)证明了k-元n-立方体网络的K1,2-结构连通度和K1,2-子结构连通度都是n。(3)证明了k-元n-立方体网络的K_(1,3)-结构连通度和K_(1,3)-子结构连通度都是n。2.在存在结构故障的情况下,k-元n-立方体网络(表示为Q_n~k)的容错哈密顿性(1)证明了在k-元n-立方体中,当至多存在n-2个故障元素并且每个故障元素在图Q_n~k中的导出子图都同构于K_(1,3)的一个连通子图的生成母图时,任意两个无故障顶点之间存在无故障的哈密顿路。(2)证明了当至多存在n-1个故障元素并且每个故障元素在图Q_n~k中的导出子图都同构于K_(1,3)的一个连通子图的生成母图时,在k-元n-立方体中存在无故障的哈密顿圈。3.给出了在存在结构故障的情况下k-元n-立方体网络中容错路由、容错哈密顿圈和容错哈密顿路的构造算法,并通过模拟实验给出了实验结果。综上所述,本文研究了在存在结构故障的情况下,k-元n-立方体网络的容错性,对于k-元n-立方体网络的应用提供了理论依据。
【学位单位】：苏州大学
【学位级别】：博士
【学位年份】：2018
【中图分类】：O157.5;TP393.0
【文章目录】：
摘要
Abstract
第一章 绪论
    1.1 引言
    1.2 互连网络研究概述
    1.3 研究内容
    1.4 本文组织结构
第二章 相关知识
    2.1 基本概念和符号表示
    2.2 k-元n-立方体
    2.3 本章小结
n
k的结构连通度和子结构连通度'>第三章 Q_{n
k的结构连通度和子结构连通度
1}-结构连通度和K₁-子结构连通度'>    3.1 K₁-结构连通度和K₁-子结构连通度
1.1-结构连通度和K_1.1-子结构连通度'>    3.2 K_1.1-结构连通度和K_1.1-子结构连通度
1.2-结构连通度和K_1.2-子结构连通度'>    3.3 K_1.2-结构连通度和K_1.2-子结构连通度
1.3-结构连通度和K_1.3-子结构连通度'>    3.4 K_1.3-结构连通度和K_1.3-子结构连通度
    3.5 本章小结
n
3中基于结构故障的容错哈密顿性质'>第四章 Qn
3中基于结构故障的容错哈密顿性质
    4.1 预备知识
n
3中基于K_1.1-结构故障的容错哈密顿性质'>    4.2 Qn
3中基于K_1.1-结构故障的容错哈密顿性质
n
3中基于K_1.2-结构故障的容错哈密顿性质'>    4.3 Qn
3中基于K_1.2-结构故障的容错哈密顿性质
n
3中基于K_1.3-结构故障的容错哈密顿性质'>    4.4 Qn
3中基于K_1.3-结构故障的容错哈密顿性质
    4.5 本章小结
n
k（k≥5）中基于结构故障的容错哈密顿性质'>第五章 Qn
k（k≥5）中基于结构故障的容错哈密顿性质
    5.1 预备知识
n
k（k≥5）中基于K_1.1-结构故障的容错哈密顿性质'>    5.2 Qn
k（k≥5）中基于K_1.1-结构故障的容错哈密顿性质
n
k（k≥5）中基于K_1.2-结构故障的容错哈密顿性质'>    5.3 Qn
k（k≥5）中基于K_1.2-结构故障的容错哈密顿性质
n
k（k≥5）中基于K_1.3-结构故障的容错哈密顿性质'>    5.4 Qn
k（k≥5）中基于K_1.3-结构故障的容错哈密顿性质
    5.5 本章小结
第六章 模拟实验
n
k中基于结构故障的容错路由的构造'>    6.1 Qn
k中基于结构故障的容错路由的构造
        6.1.1 容错路由的构造算法
        6.1.2 实验结果
n
k中基于结构故障的容错哈密顿圈的构造'>    6.2 Qn
k中基于结构故障的容错哈密顿圈的构造
        6.2.1 容错哈密顿圈的构造算法
        6.2.2 实验结果
n
k中基于结构故障的容错哈密顿路的构造'>    6.3 Qn
k中基于结构故障的容错哈密顿路的构造
        6.3.1 容错哈密顿路的构造算法
        6.3.2 实验结果
    6.4 本章小结
第七章 总结与展望
    7.1 工作总结
    7.2 研究展望
参考文献
攻读博士学位期间发表的论文和参与的科研项目
致谢

【相似文献】

相关期刊论文 前10条

1 段满珍;米雪玉;董博;轧红颖;;基于建筑倾倒优势方向的疏散路网连通度模型[J];重庆交通大学学报(自然科学版);年期

2 蔡学鹏;艾尔肯·吾买尔;;交叉立方体的限制性连通度（英文）[J];曲阜师范大学学报(自然科学版);2018年03期

3 李建喜;郭继明;邵慰慈;;给定团数的连通图的最小代数连通度[J];应用数学学报;2016年06期

4 晋亚男;林上为;;有向笛卡尔积图的k-限制弧连通度[J];河南科学;2017年03期

5 谢春萍;梁家荣;;星型网络的额外连通度[J];广西科技大学学报;2015年03期

6 王万禹;孟吉翔;赵雪冰;;线图的限制性邻域连通度[J];山东大学学报(理学版);2012年02期

7 江净超;陈江平;余洁;;道路网的实况连通度指标[J];测绘与空间地理信息;2010年01期

8 赵雪冰;张昭;;线图的邻域连通度(英文)[J];新疆大学学报(自然科学版);2009年04期

9 潘登斌;关于二分图的线连通度的一个结论[J];广西科学院学报;2003年01期

10 潘登斌;关于二分图的线连通度的一个结论[J];广西师范学院学报(自然科学版);2002年03期

相关博士学位论文 前10条

1 胡晓敏;互联网络的容错性与故障诊断[D];新疆大学;2018年

2 吕雅丽;基于结构故障的k-元n-立方体网络的容错性研究[D];苏州大学;2018年

3 杨超;乘积图的连通度和容错直径的研究[D];中国科学技术大学;2007年

4 李玮;完全多部图的广义连通度[D];南开大学;2012年

5 田应智;图的超连通性和限制性连通度[D];新疆大学;2012年

6 袁炜罡;关于图的几种指数的研究[D];上海交通大学;2015年

7 熊玮;几类图参数的研究[D];新疆大学;2014年

8 洪艳梅;图连通度与非分离子图[D];上海大学;2012年

9 李莎莎;图的广义连通度若干问题的研究[D];南开大学;2012年

10 何利;高性能计算机中互连网络的可靠性研究[D];重庆大学;2014年

相关硕士学位论文 前10条

1 张倩华;类超立方体网络的广义连通度[D];山西大学;2017年

2 罗祖文;两类Cayley图的条件连通度和极大局部连通度[D];集美大学;2018年

3 赵树丽;超立方体与折叠立方体的分支连通性[D];太原理工大学;2017年

4 蔡学鹏;折叠交叉立方体的超连通度和交叉立方体的限制性连通度[D];新疆大学;2017年

5 周婵婵;有向图的条件弧连通度[D];山西大学;2017年

6 贾勇;基于图数据的Steiner分量发现方法研究[D];燕山大学;2017年

7 赵雪冰;（有向）图的邻域连通度的研究[D];新疆大学;2012年

8 白燕茹;边邻域连通度达到最大的极图的刻画[D];新疆大学;2012年

9 万敏;星图的一种条件连通度[D];新疆大学;2008年

10 张佳;互连网络的h-额外连通度和h-额外条件可诊断数研究[D];西安电子科技大学;2017年

本文编号：2872976

boshi