#### Preview

The node-to-set disjoint paths problem in a *k*-connected network Ω is defined as follows: given a node *s* and a set of *k* other nodes *t*_{1}, *t*_{2}, … , *t*_{k} in Ω, find *k* node-disjoint paths connecting *s* and *t*_{i}, with 1 ≤ *i* ≤ *k*. It is known that such disjoint paths must exist since Ω is *k*-connected. However, building them, and ensuring that they are as short as possible are non-trivial problems. An efficient solution to the node-to-set disjoint paths problem in a network, with short paths, can be used as a building block in synthesizing collective communication operations that achieve high performance or are highly resilient to node or link failures. Recently proposed Biswapped networks, improved versions of well-known Optical Transpose Interconnection System networks or swapped networks, are a family of interconnection architectures applicable to constructing massive parallel computers. It has been known that any Biswapped network built of a connected factor network is maximally fault-tolerant, implying that such a Biswapped network has maximal connectivity. In this paper, we propose a general algorithm for the node-to-set disjoint paths problem in an arbitrary Biswapped network with a connected factor network that yields paths of length at most 1.5*D* + 3 in time, where *D*, Δ and *N* represent, respectively, the diameter, maximum degree and order of the Biswapped network, and *O*(*f*(*n*)) is the time complexity of a shortest-path routing algorithm for the *n*-node factor network. The algorithm is time-optimal for certain Biswapped networks of practical interest, including those built of meshes and hypercubes.

*Keywords: *
Biswapped network;
connectivity;
fault tolerance;
disjoint paths;
parallel routing

*Journal Article.*
*0 words.*

*Subjects: *
Computer Science

Full text: subscription required

How to subscribe Recommend to my Librarian

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content. subscribe or login to access all content.