Fault Tolerance And Fault Diagnosis Of Interconnection Networks

With the development of information technology,the importance of in-terconnection networks come into focus.However,it is inevitable that the processors of interconnection networks and the links between some processors may fail.Thus fault tolerance and fault diagnosis of interconnection network-s have drawn considerable attention.As the topology of a interconnection network can be modeled as a graph,graph theory becomes a powerful math-ematical tool to study fault tolerance and fault diagnosis of interconnection networks.Firstly,this thesis studies two fault tolerant parameters of inter-connection networks by using graph theory methods,that is,matchable and R~k-vertex-connectivity.Secondly,the relationship between g-good-neighbor diagnosability of network under the PMC model and MM~*model is explored.This thesis consists of five chapters.In Chapter 1,we first give a brief introduction to the relevant background of our research questions and main results.Then we introduce some concepts that used in this paper and some famous interconnection networks models.n-dimensional torus network has many good properties,such as smaller diameter and vertex transitive.Thus n-dimensional torus network is an im-portant interconnection network topology,and can be used to design massively interconnection networks systems.Wang et al.and Cheng et al.studied the matching preclusion problem of n-dimensional torus network with even or-der,respectively.In Chapter 2,we consider the matching preclusion problem of n-dimensional torus network with odd order.Firstly,we determine the matching preclusion number of 2-dimensional torus network with odd order,and prove that it is not super matched.Secondly,we determine the matching preclusion number of n-dimensional(n?3)torus network with odd order,and characterize its all the minimum matching preclusion sets.Strong matching preclusion is a generalization problem of matching preclu-sion,and has received much attention from many researchers.In Chapter 3,we mainly consider the strong matching preclusion problem of k-composition networks with odd order.Firstly,we prove that a class of k-composition networks with odd order are super strong matched.Secondly,we show that n-dimensional(n?3)torus network with odd order,recursive circulant graphs with odd order and Cayley graphs on abelian groups generated by minimal generating sets are all super strong matched.Connectivity is the classic parameter to evaluate the fault tolerance of inter-connection networks.For futher study,the concept of R~k-vertex-connectivity with profound background was proposed.The R~k-vertex-connectivity of many interconnection networks models have been solved.In view of recent stud-ies,there are few results on the study of characterization the minimum R~k-vertex-cuts of a graph.In Chapter 4,based on the characterization of all the minimum R~k-vertex-cuts of a graph,we introduce the concept of super R~k-vertex-connectedness and prove that Cayley graphs generated by wheel graph are super R~1-vertex-connectedness and super R~2-vertex-connectedness.With the growing number of the processors in interconnection networks,some processors in it may fail.It is crucial to locate the faulty processors efficiently.Thus identify the fault processors is favored by scholars.Diagnos-ability is the maximum number of fault processors that the interconnection network can be diagnosis.PMC model and MM~*model are two well-known diagnosis models and have been widely adopted.Because the g-good neigh-bor diagnosability of many interconnection networks models under the PMC model and MM~*model are dealt with respectively,thus the relationship be-tween g-good-neighbor diagnosability of interconnection networks under the PMC model and MM~*model is a subject that worth discussing.In Chapter5,we study some sufficient conditions such that the g-good-neighbor diag-nosability of a graph under the PMC model is equal to the g-good-neighbor diagnosability under the MM~*model,and consider the relationship between g-good-neighbor diagnosability and R~g-vertex-connectivity.Secondly,we estab-lish g-good-neighbor diagnosability of many interconnection networks models under the PMC model and MM~*model.