A Routing Algorithm in Faulty n-Rotator Graph and Its Perfomance Evaluation

概要

論文の詳細を見る
The star graph and the hypercube are receiving attention among researchers as attractive models for highly parallel distributed computing, because they have regular structure, and connect many processors with small diameter and degree. Recently, an interesting interconnection network called Rotator graph was proposed and presents some advantages over the star graph and the hypercube. Namely, Rotator graph has very small diameter and average distance, and simple routing algorithm. We present a fault tolerant routing algorithm for n-Rotator graph. This graph has only one shortest path between any two nodes which is not a good fault tolerant property, but it possesses many short paths. From this fact, we develop an algorithm that looks for the shortest path or a short path by exploiting the network properties of the n-Rotator graph. We show the mathematical expression for the probability of finding the shortest path or the second shortest path (of length equal to the shortest path +1) in the presence of faulty components (links or nodes). The results show that the algorithm finds a very short path with high probability. They enhance the rich topological properties of the n-Rotator graph.
1995-07-15