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