Fault-tolerant routing over all shortest node-disjoint paths in hypercube networks

Data transmission is the critical issue when dealing with parallel processing systems. As the number of processors increases day by day inside the supercomputers, faults are very common to occur. Therefore, generating node-disjoint paths is the guarantee to sending data from source process to destination process successfully, since single faulty process can affect maximum one path. Beyond selecting right and efficient interconnection topology, routing is also a major issue to propagate the data in a efficient way. Given paper gives an optimal fault-tolerant routing algorithm for faulty hypercube topology which provides n disjoint paths from source process s to n destination processes in n-dimensional hypercube in O(n2) time with optimal path lengths at most n + f + 1. Then simulation results showed that the proposed algorithm reduce the average path length by about 10% in comparison of Bossard´s algorithm in 8-dimensional hypercube.