Star图互连网络的容错性分析

The Fault Tolerant Analysis of Star Graph Interconnection Network

限制连通度和限制容错直径是衡量互连网络可靠性的两个重要参数 .当考察这两个参数时 ,总假设网络中和一台计算机相连接的所有计算机不会同时出现故障 .该文证明了 Star图互连网络的极小分离集和极小限制分离集的唯一性 ,然后得到了 Star图的限制连通度是 2 n- 4,当 n=3,5和 n≥ 7时 ,它的限制容错直径是 | - 3( n- 1 ) /2 - | + 2 ,对于 n=4,6,限制容错直径是| - 3( n- 1 ) /2 - | + 3,即限制容错直径只比它的容错直径大 1 .

The restricted connectivity and the restricted fault diameter are two reliability measures for interconnection networks, in which the authors assume that all the neighbors of a vertex do not fail at the same time. In this paper, the authors show the uniqueness of minimal (vertex-) separating sets and of minimal restricted separating sets in the star graphs. The authors present that for the n-star graph S-n, its restricted connectivity is 2n-4 and its restricted fault diameter is |-3(n-1)/2-|+2 for n=5 and n≥7 and |-3(n-1)/2-|+3 for n=4,6, i.e., its fault diameter plus one.