【作者】 王国军；

【导师】 陈松乔； 陈建二；

【作者基本信息】 中南大学 ， 计算机应用技术， 2002， 博士

【摘要】 超立方体网络是迄今为止最为重要和最具吸引力的网络拓扑结构之一。本文提出了两种全新的基于子立方体结构的超立方体网络中的局部连通性网络容错模型，基于局部连通性网络容错模型设计了高效的单播、广播和并行容错路由算法，提出了一种全新的、有效的和强有力的基于子立方体结构的超立方体网络容错模型和容错路由算法的概率分析方法和技术。 本文提出了两种基于子立方体结构的局部连通性网络容错模型：即局部K维子立方体连通性和局部子立方体连通性。证明了在结点错误比例任意接近50.0％时，局部连通的超立方体网络是全局连通的，即超立方体网络的局部连通性隐含了整个网络的全局连通性。所要求的局部连通性条件可以用基于局部管理的分布式方式进行检测和维护。 本文基于局部连通性网络容错模型设计了高效的单播、广播和并行容错路由算法。所设计的容错路由算法都是基于局部信息的，因而具有很好的实际意义。特别地，对于单播容错路由算法，不管所给定的超立方体网络是否满足局部连通性条件，算法都能适用：在满足要求的条件时，算法将成功地构造一条路由路径；在不满足要求的条件时，如果算法不能成功地构造一条路径，则算法将正确地报告出给定的超立方体网络不满足要求的条件。 本文还对局部连通性网络容错模型和网络容错路由算法进行了概率分析研究。大量的实验与经验表明超立方体网络具有很强的容错性。但是，当前国内外已经提出的超立方体网络容错模型只能表示一些极端的不大可能的情形，也就是说这些容错模型明显低估了超立方体网络的容错能力。本文使用概率分析的方法研究在给定结点错误概率的情况下，推导出局部连通性网络容错模型的容错性和网络容错路由算法的容错性概率。本文首次严格证明了一个具有1024个结点的10维超立方体网络能够容许多达10.0％的错误结点而具有99.0％的概率确保正确结点的连通性，而如果结点的错误概率不超过0.1％，则所有实际规模的超立方体网络能够具有99.9％的概率确保正确结点的连通性。这是当前国内外对超立方体网络进行概率分析的最好结果。该方法在确定网络容错模型和网络容错路由算法的容错性概率的下界时具有普遍意义。该方法也能够用于研究其它层次结构的网络和其它的网络通信问题。更多还原

【Abstract】 Hypercube network is one of the most important and attractive network topologies so far. In this thesis, we propose completely new hypercube fault tolerant models based on our new concept of subcube structures, design simple and efficient fault tolerant routing algorithms, and develop powerful and effective probabilistic techniques for analysis of fault tolerance of hypercube networks.We introduce two types of local-connectivity based on subcube structures. The first is the local k-subcube-connectivity, in which for each k-dimensional subcube, the number of non-faulty nodes is larger than that of faulty nodes, and the non-faulty nodes make a connected graph. The second is the local subcube-connectivity, in which for each k > 1, every k-dimensional subcube is contained in an h-dimensional subcube that is locally h-subcube connected. We show that a locally connected hypercube network may contain a constant fraction of faulty nodes, and prove that a locally connected hypercube network is also globally connected. The condition of local-connectivity can be detected and maintained in a distributed manner based on localized management.We develop efficient unicast, broadcast and parallel routing algorithms on locally connected hypercube networks. Our routing algorithms are distributed and local-information-based in the sense that each node in the network knows only its neighbors’ status and no global information of the network is required by the algorithms. In particular, our unicast routing algorithms are applicable no matter whether the given hypercube network is locally connected: in case the network is locally connected, the algorithms successfully construct the routing path, while in case our algorithms fail in finding a routing path, they report correctly that the network is not locally connected.We develop powerful and effective probabilistic analysis techniques to study fault tolerant models and the corresponding routing algorithms. Much experiments and experience have shown that hypercube networks are highly fault tolerant. On the other hand, most proposed fault tolerant models for hypercube networks are only able to characterize very rare extreme situations thus significantly underestimating the power of hypercube network fault tolerance. We develop a new scheme that enables us to derive lower bounds for the probability of hypercube network fault tolerance andfor the probability of fault tolerant routing algorithms in terms of node failure probability. Our results provide formal proofs that the hypercube networks can sustain an extremely large number of node failures. Two typical examples are that a 10-cube network of 1024 nodes can sustain up to 10.0% faulty nodes while still keep the non-faulty nodes connected with probability 99.0%, and that if the failure probability of each individual node is bounded by 0.1%, then all hypercube networks of practical size are able to keep their non-faulty nodes connected with probability 99.9%. Our results are best in the hypercube research area. Our results are both theoretically significant and practically important. Our scheme offers very general and powerful techniques for establishing lower bounds on the probability for network connectedness. Our scheme is also applicable to the study of other hierarchical network structures and other network communication problems.更多还原