A new fault-information model for adaptive & minimal routing in 3-D meshes

Zhen Jiang, Jie Wu, Dajin Wang

Research output: Contribution to journalArticle

20 Citations (Scopus)

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 languageEnglish
Pages (from-to)149-162
Number of pages14
JournalIEEE Transactions on Reliability
Volume57
Issue number1
DOIs
StatePublished - 1 Mar 2008

Keywords

  • 3-D meshes
  • Adaptive routing
  • Distributed algorithms
  • Fault-tolerant routing
  • Minimal routing

Cite this

@article{99fc0f75afb1404295d49065caf8f1e4,
title = "A new fault-information model for adaptive & minimal routing in 3-D meshes",
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.",
keywords = "3-D meshes, Adaptive routing, Distributed algorithms, Fault-tolerant routing, Minimal routing",
author = "Zhen Jiang and Jie Wu and Dajin Wang",
year = "2008",
month = "3",
day = "1",
doi = "10.1109/TR.2007.909768",
language = "English",
volume = "57",
pages = "149--162",
journal = "IEEE Transactions on Reliability",
issn = "0018-9529",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "1",

}

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 journalArticle

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

AN - SCOPUS:41449110757

VL - 57

SP - 149

EP - 162

JO - IEEE Transactions on Reliability

JF - IEEE Transactions on Reliability

SN - 0018-9529

IS - 1

ER -