Node-to-Set Disjoint-Paths Routing in Recursive Dual-Net

Recursive dual-net (RDN) is a newly proposed interconnection network for massive parallel computers. The RDN is based on recursive dual-construction of a symmetric base-network. A k-level dual-construction for k >; 0 creates a network containing (2n₀)^2k /2 nodes with node-degree d₀ + k, where n₀ and d₀ are the number of nodes and the node-degree of the base network, respectively. The RDN is node and edge symmetric and can contain huge number of nodes with small node-degree and short diameter. Nodeto-set disjoint-paths routing is fundamental and has many applications for fault-tolerant and secure communication in a network. In this paper, we propose an efficient algorithm for node-to-set disjoint-paths routing on RDN.