Pairwise Disjoint Paths Routing in Tori
Pairwise Disjoint Paths Routing in Tori
复制标题
DOI：
10.1109/access.2020.3032684
复制
发表时间：
2020
期刊：
影响因子：
3.9
通讯作者：
K. Kaneko;Son Van Nguyen;Hyunh Thi Thanh Binh
中科院分区：
文献类型：
--
作者：
K. Kaneko;Son Van Nguyen;Hyunh Thi Thanh Binh
The pairwise disjoint paths problem is to construct $c$ disjoint paths $\boldsymbol {s} _{i}\leadsto \boldsymbol {d} _{i}$ ( $1\le i\le c$ ) between given pairs of nodes $(\boldsymbol {s} _{i}, \boldsymbol {d} _{i})$ ( $1\le i\le 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\le n$ . The time complexity of their algorithm is $O(c^{4}n+kcn)$ , and the maximum path length is $\lfloor k/2\rfloor n+2k(c-1)$ . However, the algorithm proposed in this paper achieves a time complexity of $O(c^{3}n+kcn)$ , and its maximum path length is $\lfloor k/2\rfloor n+(\lceil 3k/2\rceil -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 to $n$ 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 $n^{2}$ 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(n^{2})$ , which is better than the average execution time of the previous algorithm $O(n^{3})$ in the experimental framework.
The pairwise disjoint paths problem is to construct $c$ disjoint paths $\boldsymbol {s} _{i}\leadsto \boldsymbol {d} _{i}$ ( $1\le i\le c$ ) between given pairs of nodes $(\boldsymbol {s} _{i}, \boldsymbol {d} _{i})$ ( $1\le i\le 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\le n$ . The time complexity of their algorithm is $O(c^{4}n+kcn)$ , and the maximum path length is $\lfloor k/2\rfloor n+2k(c-1)$ . However, the algorithm proposed in this paper achieves a time complexity of $O(c^{3}n+kcn)$ , and its maximum path length is $\lfloor k/2\rfloor n+(\lceil 3k/2\rceil -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 to $n$ 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 $n^{2}$ 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(n^{2})$ , which is better than the average execution time of the previous algorithm $O(n^{3})$ in the experimental framework.