某些网络容错性研究

发布时间：2018-06-07 19:45

本文选题：互连网络 + 并行计算　；参考：《中国科学技术大学》2013年博士论文

【摘要】：互连网络在并行计算和通信系统中发挥着重要作用.网络的容错性是评价互连网络性能的关键指标,它主要考虑在网络发生故障的时候网络中某些特有性质的保持能力.本文主要以图论作为工具研究故障出现时网络保持三种性质的能力：多对多不交长路存在性,连通分支最小度,连通分支子网络结构.在研究中,本文利用高对称网络在不同维度上分解的等价性,探索出一套分析网络容错性的有效方法,解决了几个悬而未决的问题. 本文第一章介绍所考虑问题的研究背景以及文章用到的图论主要概念. 本文第二章主要考虑出现顶点故障超立方体Qn中的k条多对多不交路问题.在考虑条件容错的前提下,证明故障点数.f不超过2n-2k-3时,对于Qn中在不同部的两个k-点集合S与T,存在至少含有2n-2f顶点的k条顶点不交的无故障路连接S与T.这个结果改进了很多已知的结论. 本文的第三、四章主要分析类超立方体和星图的容错性能.理论上讲,类超立方体和星图具备成为互连网络拓扑结构的很好潜质,是超立方体的强有力的竞争网络.本文在第三章中确定了类超立方的高阶限制边连通度和高阶嵌入限制边连通度,对于点的情形确定了超立方体、Mobius立方、交叉超立方体的高阶限制连通度和高阶嵌入限制连通度.本文在第四章确定了星图网络的高阶限制点(边)连通度和高阶嵌入限制点(边)连通度,其中对星图高阶限制点连通度的确定证实了同行学者提出的猜想. 本文的第五、六章主要分析广义星图网络和交换超立方体的高阶限制连通性.广义星图网络是星图的网络的推广,它的变化更加灵活,受到了很多学者的关注.交换超立方体是超立方体的另外一种变形,它由超立方体系统的删去一些边得到,具有一些很好的性质,同时降低了连接复杂性.本文在第五、六章分别确定广义星图网络和交换超立方体的高阶限制点连通度和高阶限制边连通度.
[Abstract]:Interconnection networks play an important role in parallel computing and communication systems. The fault tolerance of network is the key index to evaluate the performance of interconnection network. It mainly considers the maintenance ability of some special properties of the network when the network fails. In this paper, graph theory is used as a tool to study the ability of the network to maintain three properties when faults occur: the existence of many-to-many disjoint long paths, the minimum degree of connected branches, and the network structure of connected branches. In this paper, a set of effective methods to analyze the fault tolerance of high symmetric networks are explored by using the equivalence of decomposition in different dimensions. In the first chapter, we introduce the research background of the problem under consideration and the main concepts of graph theory used in this paper. In the second chapter, we mainly consider the problem of multi-to-many disjoint paths in the hypercube Qn with vertex fault. Considering the condition of fault tolerance, it is proved that when the number of fault points. F is not more than 2n-2k-3, for the set S and T of two k-points in different parts of Qn, there exists at least a disjoint of k vertices with 2n-2f vertices to join S and T. This result improves many known conclusions. In the third and fourth chapters, we analyze the fault-tolerant performance of hypercubes and star graphs. Theoretically, hypercubes and star maps have the potential to become topology of interconnection networks, and are powerful competitive networks of hypercubes. In chapter 3, we determine the high order restricted edge connectivity and high order embedded restricted edge connectivity of hypercubes. For the case of points, we determine the high order restricted connectivity and high order embedded restricted connectivity of cross hypercubes. In chapter 4, we determine the connectivity of high order restricted points (edges) and high order embedded restricted points (edges) of star graph networks. The determination of connectivity of high order restricted points of star graphs proves the conjecture put forward by some scholars. In chapter six, we analyze the high order restricted connectivity of generalized star graph networks and commutative hypercubes. Generalized star map network is a generalization of star map network. Commutative hypercube is another kind of deformation of hypercube. It is obtained by deleting some edges of hypercube system. It has some good properties and reduces the connection complexity. In the fifth and sixth chapters, we determine the connectivity of higher-order restricted points and higher-order restricted edge connectivity of generalized star graph networks and commutative hypercubes, respectively.
【学位授予单位】：中国科学技术大学
【学位级别】：博士
【学位授予年份】：2013
【分类号】：O157.5;TP302.8

【共引文献】