BC图多处理器网络类中基于限制故障集条件下的可靠单播和广播研究

项目名称： BC图多处理器网络类中基于限制故障集条件下的可靠单播和广播研究

项目编号： No.60873047

项目类型： 面上项目

立项/批准年度： 2009

项目学科： 金属学与金属工艺

项目作者： 樊建席

作者单位： 苏州大学

项目金额： 25万元

中文摘要： 通常的多处理器网络中的可靠信息传递是基于无限制故障顶点/边集条件下的，但基于该条件下网络的容错度一般是较低的。BC图是一类包含若干个性质优越的超立方体变型的多处理器网络。为了提高BC图的容错度，本项目将限制顶点/边连通度的概念引入BC图类中并证明了这一引入的合理性。证明了由此使得BC图的容错度（即连通度减1）比无限制故障集条件下提高大约一倍。给出了BC图上基于限制故障顶点/边集条件下的高效可靠单播和广播算法以及时间复杂度分析。通过模拟实验将我们的算法与传统的广度优先搜索算法进行了对比。理论和实验结果表明，我们的可靠单播算法所求得的给定两个无故障顶点间的可靠路径长度较短，并且我们的可靠广播算法所求得的以给定无故障顶点为根的可靠生成树的高度较低。由于我们利用了BC图中所有网络的共性进行研究，因此研究方法具有一般性，从而避免了对BC图中特殊网络逐一进行研究的缺点。研究结果不仅适用于已定义的几种超立方体的变型，而且适用于除它们以外的尚未定义的其它若干变型。另外，我们还根据该方向近年来新的研究动态，增加了与BC图相关的一些新的研究内容，如网格可嵌入性，可诊断性，提出了几种新型的互连网络。

中文关键词： BC图；限制故障集；限制连通度；可靠单播；可靠广播

英文摘要： Reliable information transmission in multiprocessor interconnection networks is usually based on the condition of sets of random faulty nodes/edges. However, the fault-tolerant degree of it under this condition is generally lower. BC graphs are a family of advantageous interconnection networks including various hypercube variants. In order to heighten the fault-tolerant degrees of BC graphs, this grant introduced the concept of the restricted node/edge connectivity to the family of BC graphs and proved the reasonability of this introduction. We proved that the fault-tolerant degrees (equaling the corresponding connectivity minus 1) of BC graphs under this introduction approximately doubles that under the condition of sets of random faulty nodes/edges. We gave efficient and reliable unicast and broadcast algorithms based on the condition of the restricted fault node/edge sets and the analysis of corresponding time complexities. We compared our algorithms with traditional breadth-first search algorithm by using experiments. Both theoretical and experimental results demonstrate that the length of the reliable path between given two fault-free nodes obtained by our reliable unicast algorithm is shorter and the height of the reliable spanning tree rooted at given fault-free node obtained by our reliable broadcast algorithm is lower. Because our research is conducted by the common properties of all networks among the family of BC graphs, our research method is of generality and thus avoids the shortcoming to study the corresponding properties of the special networks among them one by one. Our research results are not only adaptable to the defined hypercube variants, but also the other undefined hypercube variants except them. On the other hand, according to the new motivation of this research area, we still add new research contents to be related to BC graphs, such as mesh embeddability, diagnosability, proposing some new interconnection networks, and so on.

英文关键词： BC graph;restricted fault set; restricted connectivity; reliable unicast; reliable broadcast