The Research On Fault-Tolerant Model And Routing Algorithms In Hypercube Networks

With the development of computer networks and computing science,paralleling computer and interconnection networks,covering mathematics,computing science,information science and so on,are becoming one of the hotspots of computer science research. All kinds of interconnection networks with different topologies,such as Ring,Mesh, Hypercube,star topology network etc.,have been received rapidly development.In the multiprocessor interconnection networks,it is an important standard to evaluate the efficient communication among different processors.When the number of processors increases,the probability of the faults increases too.So the fault-tolerance in the message passing procedure among different processors becomes a very important problem.Therefore,it turned out most important that how to design a new kind fault-tolerance model to hold more faulty nodes and how to design more efficient fault-tolerant routing algorithm to ensure accurate and reliable message passing among non-faulty nodes.Hypercube is one of the common interconnection networks.It has small diameter,strong expansibility,symmetrical structure and simple path searching algorithms,etc.,what more, many interconnection networks with different topologies can be easily embedded in it.So it becomes one of the most important and attractive network models.In this thesis,based on the LIP and local connectivity,the fault-tolerance and routing algorithms of the hypercube are studied.The main results are following:1.The conceptions of the hypercube network and its k-subcube are proposed.Then combined with the concepts and properties of LIP,the program which is used to compute the length of LIP is improved.At the same time the analyses are made according to the result of the program.2.Combined with the conception of LIP in Chapter 2,a broadcast fault-tolerant routing algorithm based on LIP is proposed with the precondition that there is at least one LIP without wrong nodes in hypercube.Besides,the hypercube is global connectivity when the precondition is satisfied and the algorithm can hold many wrong nodes(2^n-1 or more),so the performance of fault-tolerance is largely improved.3.Based on the LIP and the 4-subcube of hypercube,a unicast fault-tolerant routing algorithm is proposed.During the necessary searching time,the algorithm can find the right path which connects the two right nodes in hypercube with many faulty nodes.And the algorithm is of momentous significance in that it is based on the local imformation of hypercube.Although some researches and some results on the fault-tolerance and routing algorithms of Hypercube are given,there are still many problems open.First,in order to ulteriorly analyze the fault-tolerance performance of hypercube,the LIP model and the approximate or precise formula about the lengh of LIP should be discussed.Second,some kinds of fault-tolerant routing algorithms in hypercube networks should be researched and the more efficient algorithms with the help of LIP fault-tolerant model would be obtained.Third,all kinds of fault-tolerant routing algorithms should be simulated,for example using NS2,in order to analyze the routing algorithms further with the help of simulation results.