AN EFFICIENT APPROACH TO FAULT-TOLERANT ROUTING IN HYPERCUBE INTERCONNECTION NETWORK

Abstract

A central problem in massively parallel computing is efficiently routing data between processors. This problem is complicated by the consideration that, in any massively parallel system, some processors are bound to fail, disrupting message routing. A routing algorithm is 'employed to direct message traffic through the system. A .good algorithm ensures that messages do not take inordinately long paths. Many researchers have used hypercube interconnection networks for their good properties, such as symmetric structure and low diameter, to construct many parallel•processing systems. However, as the number of processors increases, the probability of occurrences of faulty nodes also increases. Hence, for hypercube interconnection networks which have faulty nodes, several fault-tolerant routing algorithms have been proposed in the past which allow each node to hold status information of its neighbor nodes. In this dissertation, an efficient fault-tolerant routing algorithm has been proposed. The new algorithm integrates the approach used by Chiu and Wu, that is, classification of unsafe nodes to determine the shortest path between the source and the destination nodes in a faulty hypercube, with the concept of routing capabilities introduced by Ge-Ming Chiu and Kai-Shung Chen. The new algorithm takes the benefits of both approaches into account while determining the shortest path between source and destination nodes. The performance of the new algorithm is compared with two other previous algorithms through simulation. The simulation program is coded in Borland C++ on Windows 9x platform for IA 32 architecture. Performances are compared for reachability percentages and shortest path routing percentages. The evaluation of the algorithm shows that the new algorithm can detect communication paths which do not include any faulty