DISJOINT-PATHS AND FAULT-TOLERANT ROUTING ON RECURSIVE DUAL-NET

The recursive dual-net is a newly proposed interconnection network for massive parallel computers. The recursive dual-net is based on recursive dual-construction of a symmetric base network. A k-level dual-construction for k > 0 creates a network containing (2n(0))(2k) /2 nodes with node-degree d(0) + k, where n(0) and d(0) are the number of nodes and the node-degree of the base network, respectively. The recursive dual-net is node and edge symmetric and can contain huge number of nodes with small node-degree and short diameter. Disjoint-paths routing and fault-tolerant routing are fundamental and critical issues for the performance of an interconnection network. In this paper, we propose efficient algorithms for disjoint-paths and fault-tolerant routings on the recursive dual-net.