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

数学物理学报 ›› 2004, Vol. 24 ›› Issue (2): 168-176.

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

聂晓冬, 刘红美, 徐俊明

中国科学技术大学数学系合肥 230026 三峡大学理学院宜昌 443002

中国科学技术大学数学系合肥 230026

出版日期:2004-04-27 发布日期:2004-04-27
基金资助:
国家自然科学基金项目(10301031及10271114)资助

The Fault Tolerant Analysis of Star Graph Interconnection Network

NIE Xiao-Dong, LIU Hong-Mei, XU Jun-Ming

Online:2004-04-27 Published:2004-04-27
Supported by:
国家自然科学基金项目(10301031及10271114)资助

摘要/Abstract

摘要：

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

关键词: Star图, 连通度, 容错性;限制连通度, 限制容错直径, 分离集

Abstract:

The restricted connectivity and the restricted fault diam eter are two reliability measures for interconnection networks, in which the aut hors 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 set s 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 and n≥7 and |_3(n-1)/2_|+3 for n=4,6, i.e., its fault diameter plus one.

Key words: Star graph, Connectivity, Fault tolerance, Restricted co nnectivity, Restricted fault diameter, Separating set

中图分类号:

05C05

聂晓冬, 刘红美, 徐俊明. Star图互连网络的容错性分析[J]. 数学物理学报, 2004, 24(2): 168-176.

NIE Xiao-Dong, LIU Hong-Mei, XU Jun-Ming. The Fault Tolerant Analysis of Star Graph Interconnection Network[J]. Acta mathematica scientia,Series A, 2004, 24(2): 168-176.

参考文献

[1]Akers S B, Harel D,Krishnamurthy B. The Star Graph, an Attrative Alternative to the n Cube.Proc Internet Conf on Pararllel Processing.Berlin:SpringerVerlag, 1987. 393-400

[2]Akers S B, Krisnamurthy B. A group theoretic model for symmetric interconnection networks. IEEE Trans Comput,1989,38(4):555-566

[3]Krishnamoorthy M S,Krishnamurthy B.Fault diameter of interconnection networks. Comput Math Appl, 1987,13: 577-582

[4]Latifi S. On the faultdiameter of the star graph.Inform Process Lett,1993, 46: 143-150

[5]Esfahanian A H, Hakimi S L. On computing a condition edge. Inform Process Lett, 1988, 27:195-199

[6]Esfahanian A H. Generalized measures of fault torelance with application to N cube networks. IEEE Trans Comput, 1989, 38: 1586-1591

[7]Latifi S. Combinatorial Analysis of the Faultdiameter of the n cube. IEEE Trans Comput, 1993, 42: 27-33

[8]Li Qiao， Zhang Yi. Restricted connectivity and restricted fault diameter of some interconnection networks.DIMACS series in Discrete Mathematics and Theoretic Computer Science, 1995, 21: 267-273

[9]Bondy J A, Murty U S R. Graph Theory with Applications. N ew York: North Holland, 1979

[10]Day K, Trapathi A. A comparative study of topological properties of hypercubes and star graphs.IEEE Trans.Parallel Distributed Systems,1994,5(1): 31-38

[11]Akers S B, Krishnamurthy B.A group graphs and their fault tolerance. IEEE Trans Comput, 1987, 36(7): 885-888

[12]Akers S B, Krishnamurthy B. The fault tolerance of star graphs. Proc 2nd Intl Conf on Surpercomputing, 1987, 3: 270-276

[13]Bermond J C, ed.. Interconnection Network. Discrete Appl Math. Amsterdam:NorthHolland, 1992, 37/38(special issue)

[14]Hsu D F, Luczak T. Note on the k diameter of k connected graphs. Discrete Math, 1994, 133: 291-296

[15]Menn A,Somani A K.An Efficient Sorting Algorithmforthe Star Graph Interconnection Network.Proc Internet Conf on Parallel Processing.Berlin:Springer Verlag,1990.1-8