Diagnosability Of Interconnection Network And Its Application In Overlay Networks

This thesis focuses on the diagnosability of interconnection network and its applications in overlay networks.When we design and select a topological structure for an interconnection network,reliability is a significant measure for evaluating the performance of network.Node failure would be inevitable with the increasing scale of network,Since high reliability is always one of the most important goals pursued by designers.In this paper,we study the fault tolerance?fault diagnosability of(n,k)-star graph Sn,k and exchange hypercube EH(s,t).In addition we work on how minimizes the overhead in the transmission by applying the diagnosability of interconnection network in the overlay.The first chapter gives the fault tolerance and fault condition analysis of(n,k)-star graph Sn,k,which proves that when the fault size does not exceed n+3k-8,the remaining ones the fault-free point can be almost included by the unique maximum connected branch.Fault tolerance and diagnosability ability are used to study(n,k)-star graph Sn,k under the PMC model for t/m-diagnosability to achieve the diagnostic power of(n,k)-star graph.The t/m-diagnosability is a pessimistic diagnosis strategy,the basic idea is to enhance the self-diagnosis ability with a limited number of misdiagnosed nodes.The second chapter studies the neighbor set of a particular structure size of the exchange hypercube EH(s,t)based on the Abel group,and then analyzes and proves the diagnosability of EH(s,t)in the comparison model of g-good neighbor conditional diagnosability.g-good neighbor conditional diagnosability assumes that each node has at least g fault-free neighbors adjacent,which is defined as the max-imum cardinality of a g-good neighbor conditional faulty set that the system can guarantee to identify.The third chapter studies the overly network with minimal overhead based on the(n,k)-star graph network.From the(n,k)-star graph overlay network,the wait node pool can be adjusted,and the minimization overhead is theoretically analyzed.The numerical analysis is given in three aspects.It is further concluded that by adding the replication mechanism to further improve the routing performance.In addition reducing the hop count of the routing information,the overhead of trans-mission is mitigated.