Designing Matrice Fault-Tolerant Routing Algorithms On Hypercubes Networks With A Large Number Of Faulty Nodes

Hypercube topology of network is a common multi-computers network, and has a broad application on the Internet, so studies focus on fault-tolerant routing. With the increasing size of a multi-computers network, fault possibility of nodes and their links increase. This paper introduces some basic conceptions and some related works;Firstly, this paper analysis the traditional fault-tolerant routing algorithm, find the shortcomings in Traditional routing algorithm to resolve circuitous and deadlock, raise the safety matrices fault-tolerant routing algorithm;The traditional search optimal routing algorithm can only access road and can not access the records of the optimal number, raise the Maximum Safety-Link Matrices fault-tolerant routing algorithm, and analysis the data of the searching results.Our works are as follows:(1)A novel fault-tolerant routing design in hypercube systerm and in the course of transferring communications exist circuity is proposed, in which each node uses a Safety Matrices (SMs) to record the paths to the other nodes, and how to construct the SMs and the SMs fault-tolerant routing algorithm are given. The paper proof the related natures. Each node in hypercube need n~2 bit to store the information and record most of the optimal paths of neighboring nodes. The SMs fault-tolerant routing algorithm can avoid circuity and lock in the communications transmission, which is the optimal paths compared with the tradition fault-tolerant routing algorithm.(2)This paper,based on the faulty link in the hypercube multiprocessor system, and in the transmission of information in the course of the traditional routing algorithm can only determine the source node and the destination nodes between the existence of the optimal path and can not access the number of the optimal routing, in which each node uses a maximum safety-link matrices (MSLMs) to record the paths to the other nodes, how to construct the MSLMs and the MSLMs fault-tolerant routing algorithm are given.It records most of the optimal paths by n-1 rounds of information exchanges between neighbor nodes. It proves that MSLMs records most of the optimal paths compared with the Optimal Path Matrices (OPMs), the Extended Optimal Path Matrices (EOPMs) and the Maximum Safety-Path Matrices (MSPMs), so the problem of how to record the most of optimal paths in the n dimensional hypercube multi-computers system by using matrices is solved finally. And the more faulty nodes and faulty links in the hypercube, the Maximum Safety-Path Matrices (MSPMs) is more simple.