Fault Tolerance Analysis Of Hierarchical Cubic Network

When we design and select a topological structure for an interconnection net-work, reliability is a significant measure for evaluating the performance of network. High reliability 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.In the introduction, we show our motivation and background of this research and introduce system level diagnosis theory with some application fields.In the first chapter, we mainly introduce some basic knowledge and notations about the graph theory and combinatorial network theory, fault diagnosis model based on comparison, followed by the introduction of hypercube and some variants as well as the construction of hierarchical cubic networks, which will be explored in this thesis.In the second chapter, we mainly consider the effect on reliability caused by hard-ware failures from the topological structure of network, that is, the reliability of data transmission when there are faulty vertices. Under this concept, fault tolerance means when how many failures exist does the remained sub-network still contain some special structure and perform correctly. Fault tolerant analysis is an important topic of interconnection networks studied today. Restricted connectivity and extra-connectivity have been proposed as the important parameters to estimate the fault tolerance of connected networks. We give fault tolerant analysis of hierarchical cubic network HCNn, and determine the extra-connectivities and restricted connectivities of hierarchical cubic network HCNn. In detail, we show that ko(1)(HCNn)=2n, ko(2)(HCNn)=3n-2,kr(1)(HCNn)=2n and kr(2)(HCNn)=4n-4.In the third chapter, we theoretically determine that the conditional diagnos-ability of HCNn(n≥3) under the comparison model is tc(HCNn)=3n-2.Conclusions and some problems to be studied further are in the fourth chapter.