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

PDF### Refbacks

- There are currently no refbacks.