The node-to-set parallel routing problem for a k-connected network Γ is as follows: given a node s and k other nodes {t1, t2, … , tk} in Γ, find k node-disjoint paths connecting s and ti, for 1 ≤ i ≤ k. From the viewpoint of applications in synthesizing fast and resilient collective communication operations, it is desirable to make the parallel paths as short as possible. Building such paths is a nontrivial problem for a general network. Optical transpose interconnection system (OTIS, also known as swapped) networks, a class of hierarchical structures built of n identical n-node factor networks, are known to be maximally fault-tolerant for any connected factor network, implying that they have maximal connectivity. We propose a general algorithm for the node-to-set parallel routing problem in OTIS/swapped networks that yields paths of length no greater than D + 4 in O(Δ2 + Δf(n)) time, where D and Δ represent the diameter and degree of the OTIS network and O(f(n)) is the time complexity of a shortest-path routing algorithm for the n-node factor network. Our node-to-set routing algorithm is shown to have optimal time complexity for certain OTIS networks of practical interest, including OTIS-Mesh and OTIS-Hypercube.
['Weidong Chen', 'Wenjun Xiao', 'Behrooz Parhami']
NEARLY OPTIMAL NODE-TO-SET PARALLEL ROUTING IN OTIS NETWORKS