Node-to-Set Disjoint Paths in Biswapped Networks
Shiqing Ling, W. Chen · The Computer Journal · 2013
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 ≤ 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.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.