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

Abstract

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 RDN^k(B) containing N = (2n₀)^{2^k}/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 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 d₀+k nodes T in RDN^k(B), d₀+k disjoint paths, each connecting s to a node in T, can be found in O(((d₀+k)D₀/lgn₀)lg N) time, and the length of the paths is at most 3(D₀/2+1)(lg N+1)/(lg n₀+1),where N is the number of nodes in RDN^k(B), d₀, D₀, and n₀ are the node-degree, the diameter, and the number of nodes of base-network B, respectively.