Abstract
In this paper, we rewrite the Minimal-Connected-Component (MCC) model in 2-D meshes in a fully-distributed manner without using global information so that not only can the existence of a Manhattan-distance-path be ensured at the source, but also such a path can be formed by routing-decisions made at intermediate nodes along the path. We propose the MCC model in 3-D meshes, and extend the corresponding routing in 2-D meshes to 3-D meshes. We consider the positions of source & destination when the new faulty components are constructed. Specifically, all faulty nodes will be contained in some disjoint fault-components, and a healthy node will be included in a faulty component only if using it in the routing will definitely cause a non-minimal routing-path. A distributed process is provided to collect & distribute MCC information to a limited number of nodes along so-called boundaries. Moreover, a sufficient & necessary condition is provided for the existence of a Manhattan-distance-path in the presence of our faulty components. As a result, only the routing having a Manhattan-distance-path will be activated at the source, and its success can be guaranteed by using the information of boundary in routing-decisions at the intermediate nodes. The results of our Monte-Carlo-estimate show substantial improvement of the new fault-information model in the percentage of successful Manhattan-routing conducted in 3-D meshes.
| Original language | English |
|---|---|
| Pages (from-to) | 149-162 |
| Number of pages | 14 |
| Journal | IEEE Transactions on Reliability |
| Volume | 57 |
| Issue number | 1 |
| DOIs | |
| State | Published - 1 Mar 2008 |
Keywords
- 3-D meshes
- Adaptive routing
- Distributed algorithms
- Fault-tolerant routing
- Minimal routing
Cite this
}
A new fault-information model for adaptive & minimal routing in 3-D meshes. / Jiang, Zhen; Wu, Jie; Wang, Dajin.
In: IEEE Transactions on Reliability, Vol. 57, No. 1, 01.03.2008, p. 149-162.Research output: Contribution to journal › Article › Research › peer-review
TY - JOUR
T1 - A new fault-information model for adaptive & minimal routing in 3-D meshes
AU - Jiang, Zhen
AU - Wu, Jie
AU - Wang, Dajin
PY - 2008/3/1
Y1 - 2008/3/1
N2 - In this paper, we rewrite the Minimal-Connected-Component (MCC) model in 2-D meshes in a fully-distributed manner without using global information so that not only can the existence of a Manhattan-distance-path be ensured at the source, but also such a path can be formed by routing-decisions made at intermediate nodes along the path. We propose the MCC model in 3-D meshes, and extend the corresponding routing in 2-D meshes to 3-D meshes. We consider the positions of source & destination when the new faulty components are constructed. Specifically, all faulty nodes will be contained in some disjoint fault-components, and a healthy node will be included in a faulty component only if using it in the routing will definitely cause a non-minimal routing-path. A distributed process is provided to collect & distribute MCC information to a limited number of nodes along so-called boundaries. Moreover, a sufficient & necessary condition is provided for the existence of a Manhattan-distance-path in the presence of our faulty components. As a result, only the routing having a Manhattan-distance-path will be activated at the source, and its success can be guaranteed by using the information of boundary in routing-decisions at the intermediate nodes. The results of our Monte-Carlo-estimate show substantial improvement of the new fault-information model in the percentage of successful Manhattan-routing conducted in 3-D meshes.
AB - In this paper, we rewrite the Minimal-Connected-Component (MCC) model in 2-D meshes in a fully-distributed manner without using global information so that not only can the existence of a Manhattan-distance-path be ensured at the source, but also such a path can be formed by routing-decisions made at intermediate nodes along the path. We propose the MCC model in 3-D meshes, and extend the corresponding routing in 2-D meshes to 3-D meshes. We consider the positions of source & destination when the new faulty components are constructed. Specifically, all faulty nodes will be contained in some disjoint fault-components, and a healthy node will be included in a faulty component only if using it in the routing will definitely cause a non-minimal routing-path. A distributed process is provided to collect & distribute MCC information to a limited number of nodes along so-called boundaries. Moreover, a sufficient & necessary condition is provided for the existence of a Manhattan-distance-path in the presence of our faulty components. As a result, only the routing having a Manhattan-distance-path will be activated at the source, and its success can be guaranteed by using the information of boundary in routing-decisions at the intermediate nodes. The results of our Monte-Carlo-estimate show substantial improvement of the new fault-information model in the percentage of successful Manhattan-routing conducted in 3-D meshes.
KW - 3-D meshes
KW - Adaptive routing
KW - Distributed algorithms
KW - Fault-tolerant routing
KW - Minimal routing
UR - http://www.scopus.com/inward/record.url?scp=41449110757&partnerID=8YFLogxK
U2 - 10.1109/TR.2007.909768
DO - 10.1109/TR.2007.909768
M3 - Article
VL - 57
SP - 149
EP - 162
JO - IEEE Transactions on Reliability
JF - IEEE Transactions on Reliability
SN - 0018-9529
IS - 1
ER -