The Study On Induced Embedding And Routing Algorithms In Parallel Interconnection 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 find 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 above two aspects, the fault-tolerance and routing algorithms of the hypercube are studied. The main results are following:1. A new kind of fault-tolerant model, LIP induced embedding model, is proposed. Some conceptions, properties, merits and the algorithm on LIP are given. Corresponding to the algorithm, a C++ realization program is present, which can get the precise length value of LIP when n equals 6 and 7.2. In order to efficiently analyze the fault-tolerance of hypercube network and to propose a better fault-tolerant algorithms, the evaluation of an upper bound and a lower bound on the LIP are given. A very significative conjecture on the bound of LIP is obtained. Besides, the...