Pairwise Disjoint Paths Routing in Tori
The pairwise disjoint paths problem is to construct c disjoint paths s<sub>i</sub> → d<sub>i</sub> (1 ≤ i ≤ c) between given pairs of nodes (s<sub>i</sub>, d<sub>i</sub>) (1 ≤ i ≤ c) in a graph who...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2020-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9234411/ |
| _version_ | 1830083408522379264 |
|---|---|
| author | Keiichi Kaneko Son Van Nguyen Hyunh Thi Thanh Binh |
| author_facet | Keiichi Kaneko Son Van Nguyen Hyunh Thi Thanh Binh |
| author_sort | Keiichi Kaneko |
| collection | DOAJ |
| description | The pairwise disjoint paths problem is to construct c disjoint paths s<sub>i</sub> → d<sub>i</sub> (1 ≤ i ≤ c) between given pairs of nodes (s<sub>i</sub>, d<sub>i</sub>) (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(c<sup>4</sup>n+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(c<sup>3</sup>n+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 n<sup>2</sup> 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<sup>2</sup>), which is better than the average execution time of the previous algorithm O(n<sup>3</sup>) in the experimental framework. |
| first_indexed | 2024-12-14T16:22:05Z |
| format | Article |
| id | doaj.art-59732e3d12d04ee09ffdc8250f875328 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-14T16:22:05Z |
| publishDate | 2020-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-59732e3d12d04ee09ffdc8250f8753282022-12-21T22:54:47ZengIEEEIEEE Access2169-35362020-01-01819220619221710.1109/ACCESS.2020.30326849234411Pairwise Disjoint Paths Routing in ToriKeiichi Kaneko0https://orcid.org/0000-0003-1790-4615Son Van Nguyen1https://orcid.org/0000-0001-8188-4984Hyunh Thi Thanh Binh2https://orcid.org/0000-0003-1976-6113Institute of Engineering, Tokyo University of Agriculture and Technology, Tokyo, JapanSchool of Information and Communication Technology, Hanoi University of Science and Technology, Hanoi, VietnamSchool of Information and Communication Technology, Hanoi University of Science and Technology, Hanoi, VietnamThe pairwise disjoint paths problem is to construct c disjoint paths s<sub>i</sub> → d<sub>i</sub> (1 ≤ i ≤ c) between given pairs of nodes (s<sub>i</sub>, d<sub>i</sub>) (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(c<sup>4</sup>n+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(c<sup>3</sup>n+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 n<sup>2</sup> 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<sup>2</sup>), which is better than the average execution time of the previous algorithm O(n<sup>3</sup>) in the experimental framework.https://ieeexplore.ieee.org/document/9234411/Fault tolerant systemsmultiprocessor interconnection networksnetwork topologyparallel processingsupercomputers |
| spellingShingle | Keiichi Kaneko Son Van Nguyen Hyunh Thi Thanh Binh Pairwise Disjoint Paths Routing in Tori IEEE Access Fault tolerant systems multiprocessor interconnection networks network topology parallel processing supercomputers |
| title | Pairwise Disjoint Paths Routing in Tori |
| title_full | Pairwise Disjoint Paths Routing in Tori |
| title_fullStr | Pairwise Disjoint Paths Routing in Tori |
| title_full_unstemmed | Pairwise Disjoint Paths Routing in Tori |
| title_short | Pairwise Disjoint Paths Routing in Tori |
| title_sort | pairwise disjoint paths routing in tori |
| topic | Fault tolerant systems multiprocessor interconnection networks network topology parallel processing supercomputers |
| url | https://ieeexplore.ieee.org/document/9234411/ |
| work_keys_str_mv | AT keiichikaneko pairwisedisjointpathsroutingintori AT sonvannguyen pairwisedisjointpathsroutingintori AT hyunhthithanhbinh pairwisedisjointpathsroutingintori |