Node-Disjoint Paths in Balanced Hypercubes with Application to Fault-Tolerant Routing

The study of interconnection networks plays an essential role in the design of parallel computing systems because their topological properties make a great impact on the performance and reliability of the systems. The balanced hypercube, designed for fault tolerance, is a variant of the hypercube with desirable properties of strong connectivity, regularity, and symmetry. Over the past decade, the node-disjoint paths problem has received much attention. The existence of these parallel paths can improve reliability, fault tolerance, message throughput, and information security. In this paper, we propose algorithms to construct a maximal number of node-disjoint paths between any two distinct nodes of an n-dimensional balanced hypercube in \(O(n^2)\) time. The lengths of these parallel paths exceed the internode distance by no more than six. In addition, we conduct simulation experiments to evaluate the performance of the fault-tolerant routing using multiple node-disjoint paths as transmission channels.