Reliability Evaluation Of Two Classes Of Network Structures

When we design and select a topological structure for an interconnection network, reliability is a significant measure for evaluating the performance of network. High relia-bility is always one of the important goals pursued by network designers. Processor fault diagnosis has played an important role in measuring the reliability of a multiprocessor system, and the diagnosabilities of many well-known multiprocessor systems have been investigated in detail.This thesis takes two classes of networks, namely twisted-cube connected network TNn and Burnt Pancake graph BPn, as subjects investigated, and explores their fault tolerance, fault diagnosability as well as diagnosis algorithms.The first chapter prepares some basic knowledge of the paper. It mainly introduces basis conceptions., notions of graph theory, combinatorial network theory, and presents diagnosis model, diagnosis strategy with research progress in system level diagnosis theory.The second chapter introduces the topological construction of twisted-cube connected networks TNn followed by the fault tolerant analysis of TNn, which paves the way for fault diagnosis.The third chapter theoretically determines that the conditional diagnosabilities of TNn under the PMC testing model and the comparison model. In detail, we show that the conditional diagnosability of TNn under the PMC model is4n-7(n≥5), and that the conditional diagnosability of TNn under the comparison model is3n-5(n≥7). Finally, we give a quick t/t-diagnosis algorithm.The fourth chapter introduces the topological construction of Burnt Pancake BPn and shows that BPn is isomorphic to the Cayley graph, Cay(Z2Sn, S’) of the wreath product based on cyclic group Z2and symmetric group Sn, Z2Sn, so is vertex transitive.The fifth chapter mainly focuses on conditional diagnosability of Burnt Pancake cube BPn under comparison model based on its fault tolerance analysis, and determine that the conditional diagnosability of BPn under the comparison model is3n-(n≥4).Finally, Chapter six gives concluding remarks and outlines some possible future work in this area.