Reliability Analysis Of Some Interconnection Networks

The application of high performance computing has played a huge role in the various fields,and has become a significant symbol to measure a country’s comprehensive national strength and the technological development level.With the development of high performance computing applications and the expansion of scale,people put forward higher requirements for the reliability of high performance computing system.With the increasing number of processors in the system,the probability of system failure increases.Esfahanian called the system fault-tolerant,if the large-scale multiprocessor system failure still has the function.A system is t-diagnosable if all faulty processors can be identified without replacement,provided that the number of faults presented does not exceed t.The performance of high performance computing system depends on the performance of its interconnection networks.Therefore,the reliability of the system depends on the reliability of interconnection networks.An interconnection network is modeled as an undirected simple graph,whose vertices represent processors and edges represent communication links.Research on the reliability of interconnection network is transformed into the research on relevant parameters of the graph.Connectivity and diagnosability are two important parameters to measure the reliability of interconnection networks.The traditional connectivity allows that a faulty set can contain all neighbors of a vetex at the same time,this greatly underestimates the reliability of the interconnection networks.Then conditional connectivity,g-extra connectivity and g-good-neighbor connectivity are proposed.Because g-good-neighbor connectivity has more strength capacity than other conditional connectivity,it has been widely studied by scholars.The traditional diagnosability greatly underestimates the fault diagnosis ability of the system too.Then conditional diagnosability,g-good-neighbor diagnosability and g-extra diagnosability are proposed successively.When g is small,compared with conditional diagnosability and g-extra diagnosability,the restricted conditions of g-good-neighbor diagnosability is not only wide and flexible,but also shows stronger adaptability.When g is large,the g-good-neighbor diagnosability is larger than the traditional diagnosability and g-extra diagnosability.In particular,the g-good-neighbor diagnosability at its upper bound.Therefore,g-good-neighbor diagnosability is not only accords with the reality of system diagnosis,but also stronger than other conditional diagnosability.In this thesis,we mainly study the g-good-neighbor diagnosability of bubble sort graph and star graph under the PMC model and MM*Model.The specific research content of this thesis is summarized as follows:(1)The bubble-sort graph Bn is a special case of tree-transposition graphs,and its generated graph is a path P.As a well-known interconnection network topology,it has a lot of routing properties.First,we prove the traditional diagnosability of Bn under the PMC model and MM*model t(Bn)=t0(Bn)=n-1,n≥4.Then,we determine the g-good-neighbor diagnosability of Bn under the PMC model and MM*model when g=1,2,3,respectively.#12 and#12(2)The star graph Sn is another special case of tree-transposition graphs7 and its generated graph is a star K1,n-1.It is seen as an alternative to the next generation interconnection networks of high-performance computing,which can replace the Qn.It is used as an alternative to hypercube for the interconnection network of the next generation of high performance computing systems.First,we determine the traditional diagnosability of Sn under the PMC model and MM*model#12 Then,we prove the g-good-neighbor diagnosability of Sn under the PMC model and MM*model tg(Sn)=(g+1)!(n-g)-1,n≥4,0≤g≤n-2.By analyzing and comparing with other diagnosability,g-good-neighbor diagnosability is not only more accordant with the actual fault diagnosis of the system,but also has a stronger diagnostic ability.