Constructing node-disjoint routes in K-Ary N-cubes

Abstract EN

In this paper, a method for constructing node-disjoint (parallel) paths in k-ary n-cube interconnection networks is described.

We start by showing in general how to construct parallel paths in any Cartesian product of two graphs based on known paths in the factor graphs.

Then we apply the general result to build a complete set of parallel paths (i.e., as many paths as the degree of the network) between any two nodes of a k-ary n-cube which can be viewed as the Cartesian product of complete graphs.

Each of the constructed paths is of length at most 2 plus the minimum distance between the two nodes.

These parallel paths are useful in speeding-up the transfer of large amounts of data between two nodes and in offering alternate routes in cases of faulty nodes.