论文部分内容阅读
随着并行计算机互联网络规模的不断扩大,互联网络中处理器或处理器链路发生故障的情形是不可避免的。因此,故障网络中的路由问题和连通性以及容错性成为了计算机研究领域的热点。如何设计简单可行的路由算法从而保证网络能继续有效的工作迫在眉睫。本文主要讨论了结点故障条件下超立方体变形网络(折叠超立方体网络和交叉超立方体网络)的局部连通性、拓展局部连通性、在局部连通性和拓展局部连通性下的容错路由算法、结点故障条件下的圈嵌入加强超立方体网络以及增广超立方体网络的边泛圈和边哈密顿性。
论文主要分为四章,研究故障超立方体变形网络的容错性、连通性和路由算法。
第一章主要介绍图的相关基本概念及其性质,超立方体网络及其变形网络拓扑结构和性质简介；并阐述与网络中路由算法相关的容错性和连通性的研究意义。
第二章主要研究了折叠超立方体网络的局部连通性和拓展局部连通性以及基于局部连通性和拓展局部连通性下的高效容错路由算法,得到了以下五个定理和两个高效容错并行路由算法：
(1)若n-维折叠超立方体网络FQn是局部k-维子折叠超立方体连通的,则在FQn中必定存在至少K=min(Dk (u ), Dk (v ))条从非故障源结点u到目的结点v的并行路径,且每一条路径的长度不超过(d (Uk ,Vk )+3)2k 。
(2)局部k-维子折叠超立方体连通的n-维折叠超立方体 nFQ 中的所有非故障结点构成一个连通图。
(3)局部子折叠超立方体连通的n-维折叠超立方体 nFQ 中的所有非故障结点构成一个连通图。
(4)在一个拓展局部k-维子折叠超立方体连通的n-维折叠超立方体 nFQ 中所有的非故障结点构成一个连通图。
(5)在一个拓展局部子折叠超立方体连通的n-维折叠超立方体 nFQ 中,所有的非故障结点构成一个连通图。
算法1、具有大量故障结点的n-维折叠超立方体 nFQ 中的高效并行路由算法。
算法 2、基于拓展局部k-维子折叠超立方体连通性下n-维折叠超立方体 nFQ 中的高效并行路由算法。
第三章主要研究了增广超立方体的边泛圈性和边哈密顿性、加强超立方体在结点故障条件下的圈嵌入和交叉超立方体的局部连通性及其以及基于局部连通性下的高效容错路由算法。
第四章我们对全文的工作进行了总结和展望,并且提出了一些仍需要进一步研究的问题。