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.
- There are currently no refbacks.