| The effective communication is a crucial criterion reflects the performance of the multi-processor system. The network delay time determined by the topology of the interconnection is a static measure. It is affected directly by the diameter of the network. When failure happens, we need to research the reliability of the system. The fault-diameter inflects the fault-tolerant capacity and It is hard to be attained. It is also a main task to find the shortest and reliable path when failure happens.In this paper, we use the Breadth-First Search Algorithm to study all the above questions we have mentioned. What we do is given as following:First, a breadth-first spanning tree is the shortest one among all the spanning trees having the same node as their boot node. According to this we got the diameter of the hypercube, crossed-cube, twisted Cube according to the theory. Furthermore we have shown the diameter limit of the BC network. It's a new method to research the diameter and fault diameter of the network.Next, we considered the fault-tolerant capacity. We show how many nodes and link are removed can maintain the graph's connectivity. Based on Menger theorem, we have found n disjoined paths between any two nodes in a graph by using the Breadth-First Search method. There is no path shorter than these n disjoined paths. Then we get the fault-diameter of a network.Last, we discussed the distributed Breadth-First Search Algorithm. In a practical parallel system, the distributed Breadth-First Search Algorithm can give the one-to-all routing paths, even there exist faulty in the network. We also give a simple algorithm using the Breadth-First Search idea. By the algorithm we can get the path between any two given nodes when the network is connected.The method and algorithm given in this paper have been proved correct. It's a new method to study the new interconnection network topology, and it have tested in the low dimension BC interconnection network. |
PDF Full Text Request