Fault-Tolerant Communication Mechanism Based on Disjoint Paths in Interconnection Networks

Different interconnection structures exert a significant impact on network communication ability, directly influencing system performance. The half hypercube Network has an excellent topology that can provide high network fault tolerance and communication efficiency while maintaining a low node degree. In this paper, we investigate efficient and reliable communication algorithms for half hypercube networks in distributed system. Firstly, we design a disjoint path construction algorithm for a half hypercube, which enables reliable communication of the optimal number of disjoint paths between any two nodes in the network. Secondly, we present a fault-tolerant path embedding algorithm for a half hypercube. When the number of faulty nodes does not exceed ⌈n/2⌉, this algorithm can obtain a fault-tolerant unicast path between any two non-faulty nodes in ann-dimensional half hypercube network. Finally, we evaluate the performance of communication algorithms through simulation experiments and real testbed. Experimental results demonstrate that the efficiency and buffer utilization rate of the proposed algorithms can be improved by at least 21.8% and 15.6%, respectively. Testbed results show that the data delivery rate increased by 21.8%, and the path interference degree decreased by 32.5%.