Fault-tolerant routing algorithm based on disjoint paths in 3-ary n-cube networks with structure faults

摘要

The 3-ary n-cube network is widely used in large-scale multi-processor parallel computers. It is an important issue to design high-performance communication technology with fault tolerance. In this paper, we study the fault-tolerant routing of 3-ary n-cube without desired intersection. Firstly, we propose a fully adaptive routing algorithm for 3-ary n-cube network based on the new virtual network partition technology. The virtual channel allocation of the algorithm is given and its deadlock free property is proved. Secondly, we propose a construction of disjoint paths in 3-ary n-cube networks under the fault model. Finally, we propose a novel fault-tolerant routing algorithm for 3-ary n-cube networks based on the disjoint path with structure faults. The simulation results show that the proposed fault-tolerant routing algorithm outperforms the previous fault-tolerant routing algorithm in many situations, which has a 19-21 percent increase in throughput and the injection rate.