A stochastic link-fault-tolerant routing algorithm in folded hypercubes.
Saved in:
| Title: | A stochastic link-fault-tolerant routing algorithm in folded hypercubes. |
|---|---|
| Authors: | Thuan, Bui Thi1, Ngoc, Lam Boi1, Kaneko, Keiichi1 |
| Source: | Journal of Supercomputing. Oct2018, Vol. 74 Issue 10, p5539-5557. 19p. |
| Subjects: | Routing algorithms, Hypercube networks (Computer networks), Fault-tolerant computing, Routing (Computer network management), Stochastic processes |
| Abstract: | A folded hypercube is obtained by adding complementary links to a hypercube. The diameter of the folded hypercube is almost half of that of the hypercube, while its degree is larger than the degree of the hypercube by only one. In this paper, we propose a stochastic link-fault-tolerant routing algorithm in a folded hypercube by introducing a limited global information called routing probabilities. For an n-dimensional folded hypercube, we have proved that the routing probabilities for all distances can be calculated in O(n2logn) time at each node and the message can be forwarded to its neighbor node at each node in O(n) time. We also conducted a computer experiment, the results of which show that our algorithm achieves a better performance than the best algorithm for a hypercube. [ABSTRACT FROM AUTHOR] |
| Copyright of Journal of Supercomputing is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| Abstract: | A folded hypercube is obtained by adding complementary links to a hypercube. The diameter of the folded hypercube is almost half of that of the hypercube, while its degree is larger than the degree of the hypercube by only one. In this paper, we propose a stochastic link-fault-tolerant routing algorithm in a folded hypercube by introducing a limited global information called routing probabilities. For an n-dimensional folded hypercube, we have proved that the routing probabilities for all distances can be calculated in O(n2logn) time at each node and the message can be forwarded to its neighbor node at each node in O(n) time. We also conducted a computer experiment, the results of which show that our algorithm achieves a better performance than the best algorithm for a hypercube. [ABSTRACT FROM AUTHOR] |
|---|---|
| ISSN: | 09208542 |
| DOI: | 10.1007/s11227-018-2456-9 |
