### 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.