Journal Article

Node-to-Set Disjoint Paths in Biswapped Networks

Shan Ling and Weidong Chen

in The Computer Journal

Published on behalf of British Computer Society

Volume 57, issue 7, pages 953-967
Published in print July 2014 | ISSN: 0010-4620
Published online April 2013 | e-ISSN: 1460-2067 | DOI:
Node-to-Set Disjoint Paths in Biswapped Networks

Show Summary Details


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 t1, t2, … , tk in Ω, find k node-disjoint paths connecting s and ti, with 1 ≤ ik. 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.5D + 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.