Pairwise Disjoint Paths Routing in Tori

Abstract

The pairwise disjoint paths problem is to construct c disjoint paths si → di (1 ≤ i ≤ c) between given pairs of nodes (si, di) (1 ≤ i ≤ c) in a graph whose connectivity is no less than 2c. It is a major problem for interconnection networks, together with the node-to-node disjoint paths problem, the node-to-set disjoint paths problem, and the set-to-set disjoint paths problem. In this paper, we propose an algorithm that solves this problem for a torus. In a previous work, Bossard and Kaneko have developed an algorithm that constructs disjoint paths between c pairs of nodes in a k-ary n-dimensional torus, where c ≤ n. The time complexity of their algorithm is O(c4n+kcn), and the maximum path length is [k/2jn+2k(c-1). However, the algorithm proposed in this paper achieves a time complexity of O(c3n+kcn), and its maximum path length is [k/2jn + ([3k/21 - 2)(c - 1), which are both improvements over the previous algorithm. We also conducted an evaluation experiment to show that the average path lengths are proportional to k if n is fixed, and ton if k is fixed. The theoretical maximum path lengths were not attained by the paths constructed by our algorithm, and the average execution time was proportional to k if n is fixed, and to n2 if k is fixed. Additional experimental results show that, compared to the previous algorithm by Bossard and Kaneko, our algorithm achieves a better performance with respect to the maximum path lengths, but both algorithms achieve a similar level of performance with respect to the average maximum path lengths. Also, it is shown that the average execution time of our algorithm is about O(n2), which is better than the average execution time of the previous algorithm O(n3) in the experimental framework.

Keywords

• Fault tolerant systems
• multiprocessor interconnection networks
• network topology
• parallel processing
• supercomputers