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 B. A k-level dual-construction for k>0 creates a network RDNk(B) containing N = (2n0)2^k/2 nodes with node-degree d0+k, where n0 and d0 are the number of nodes and the node-degree of the base network, respectively. The RDN is a symmetric graph and can contain huge number of nodes with small node-degree and short diameter. Node-to-set disjoint-paths routing is fundamental and has many applications for fault-tolerant and secure communications in a network. In this paper, we propose an efficient algorithm for node-to-set disjoint-paths routing in RDN. We show that, given a node s and a set of d0+k nodes T in RDNk(B), d0+k disjoint paths, each connecting s to a node in T, can be found in O(((d0+k)D0/lgn0)lg N) time, and the length of the paths is at most 3(D0/2+1)(lg N+1)/(lg n0+1),where N is the number of nodes in RDNk(B), d0, D0, and n0 are the node-degree, the diameter, and the number of nodes of base-network B, respectively.