Research On Fault Tolerance For Variations Of Hypercube Networks

Interconnection networks play an important role in parallel computing and communication systems.The interconnection network can be represented by undirected graph G=(V,E),where each node in graph G corresponds to the processor of the interconnection network and each edge in graph G corresponds to the communication link of the interconnection network.With the increasing number of fault nodes in multiprocessor systems,interconnection networks may collapse.Therefore,it is very important to maintain the reliability of the interconnection network by distinguishing the fault node from the non-fault node.The fault-tolerance of network is an important index of the performance of interconnection network.It mainly refers to the ability to maintain certain characteristics of the system when the network fails.Connectivity,edge connectivity and diagnosability are important parameters to measure network fault tolerance performance.When people define connectivity and edge connectivity,they assume that any part of the system may fail at the same time,which may not be accurate in practical application,so they can not accurately evaluate the reliability of the network.In order to overcome this shortcoming,the concepts of restricted connectivity and g-good-neighbor conditional diagnosability are introduced.S is the vertex-cut of system G,and any vertex of G-S has at least g neighbor.The minimum number of vertex-cut S is defined as g-restricted connectivity.This parameter can measure the fault tolerance of interconnection network more accurately than traditional connectivity.The g-good-neighbor conditional diagnosability refers to the maximum number of fault nodes that the system can diagnose when each node has at least g good neighbors.Compared with classical diagnosability,g-good-neighbor conditional diagnosability has better connectivity and diagnostic ability.In this paper,we use graph theory knowledge to study the three capabilities of network maintenance in case of system failure:restricted connectivity,restricted edge connectivity and g-good-neighbor conditional diagnosability.Hypercube is an early network.Its advantages are high symmetry,high fault tolerance,excellent embedding and simple routing algorithm.It is one of the most studied networks at present.However,according to different network design requirements,people have transformed the hypercube network and formed some deformed cube network structures:hierarchical cube network,(n,k)-star network and so on.This paper studies the fault-tolerant parameters of these two networks,and provides more detailed fault-tolerant information for network designers.In order to determine the g-good-neighbor conditional diagnosability of hierarchical cube network and(n,k)-star network,PMC model proposed by Preparata,Metzem and Chien and MM*model proposed by Sengupta and Dahbura are used.In the first chapter,the concept of fault tolerance and the basic knowledge of graph theory are introduced.In the second chapter,the fault-tolerant capability of hierarchical cubic networks is analyzed.The specific value of the restricted(edge)connectivity of n-HHC network is derived,Kg(n-HHC)=?g[n-HHC)=2g(m+1-g).And the g-good-neighbor con-ditional diagnosability of n-HHC network in PMC model and MM*model is determined,tg(n-HHC)=2g(m+2-g)-1for 1?g?m-1,m?2,n = 2m ?m.This provides a more detailed reference for the design of the network.In the third chapter,we mainly study the fault-tolerant parameter-super(edge)connectivity of(n,k)-star graph network Sn,k.At that time,Li and Xu got that forg>min?k-2,n/2-1?.In this chapter,we will derive that Kg(Sn,k)=?s(g)(Sn,k)=(n+1)!(n-g-1)/(n-k)!for n-k|k?g?n-2.Based on this,Wei and Xu deduced the g-good-neighbor conditional diagnosability of(n,k)-star network under PMC model and MM*model.It provides a reference for network designers.