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

Zhen Jiang, Jie Wu, Dajin Wang

Research output: Contribution to journalArticle

22 Scopus citations

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