Heuristic fault-tolerant routing in mesh using minimal-connected-component fault blocks

Gui Hai Chen, Peng Du, Dajin Wang, Li Xie

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

Rectangular fault block model is designated to solve the problem of fault-tolerant route in mesh and was improved as Minimal-Connected-Component (MCC) model. Based on MCC, we construct an overlapping graph and give a set of algorithm according to the graph to work out the route as short as possible to avoid the appearance of fault block when Manhattan route does not exist. The simulated test shows that the route found by the algorithm mentioned above is nearly the shortest one. Hence compared to other methods costing much more time, this new heuristic fault-tolerant algorithm is of no doubt a better method in finding the shortest route.

Original languageEnglish
Pages (from-to)318-322
Number of pages5
JournalTien Tzu Hsueh Pao/Acta Electronica Sinica
Volume32
Issue number2
StatePublished - 1 Feb 2004

Keywords

  • Adaptive routing
  • Fault block model
  • Fault tolerance
  • Mesh

Cite this

@article{03b4e1b0586f4effb22d612cfc78d9f1,
title = "Heuristic fault-tolerant routing in mesh using minimal-connected-component fault blocks",
abstract = "Rectangular fault block model is designated to solve the problem of fault-tolerant route in mesh and was improved as Minimal-Connected-Component (MCC) model. Based on MCC, we construct an overlapping graph and give a set of algorithm according to the graph to work out the route as short as possible to avoid the appearance of fault block when Manhattan route does not exist. The simulated test shows that the route found by the algorithm mentioned above is nearly the shortest one. Hence compared to other methods costing much more time, this new heuristic fault-tolerant algorithm is of no doubt a better method in finding the shortest route.",
keywords = "Adaptive routing, Fault block model, Fault tolerance, Mesh",
author = "Chen, {Gui Hai} and Peng Du and Dajin Wang and Li Xie",
year = "2004",
month = "2",
day = "1",
language = "English",
volume = "32",
pages = "318--322",
journal = "Tien Tzu Hsueh Pao/Acta Electronica Sinica",
issn = "0372-2112",
publisher = "Chinese Institute of Electronics",
number = "2",

}

Heuristic fault-tolerant routing in mesh using minimal-connected-component fault blocks. / Chen, Gui Hai; Du, Peng; Wang, Dajin; Xie, Li.

In: Tien Tzu Hsueh Pao/Acta Electronica Sinica, Vol. 32, No. 2, 01.02.2004, p. 318-322.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Heuristic fault-tolerant routing in mesh using minimal-connected-component fault blocks

AU - Chen, Gui Hai

AU - Du, Peng

AU - Wang, Dajin

AU - Xie, Li

PY - 2004/2/1

Y1 - 2004/2/1

N2 - Rectangular fault block model is designated to solve the problem of fault-tolerant route in mesh and was improved as Minimal-Connected-Component (MCC) model. Based on MCC, we construct an overlapping graph and give a set of algorithm according to the graph to work out the route as short as possible to avoid the appearance of fault block when Manhattan route does not exist. The simulated test shows that the route found by the algorithm mentioned above is nearly the shortest one. Hence compared to other methods costing much more time, this new heuristic fault-tolerant algorithm is of no doubt a better method in finding the shortest route.

AB - Rectangular fault block model is designated to solve the problem of fault-tolerant route in mesh and was improved as Minimal-Connected-Component (MCC) model. Based on MCC, we construct an overlapping graph and give a set of algorithm according to the graph to work out the route as short as possible to avoid the appearance of fault block when Manhattan route does not exist. The simulated test shows that the route found by the algorithm mentioned above is nearly the shortest one. Hence compared to other methods costing much more time, this new heuristic fault-tolerant algorithm is of no doubt a better method in finding the shortest route.

KW - Adaptive routing

KW - Fault block model

KW - Fault tolerance

KW - Mesh

UR - http://www.scopus.com/inward/record.url?scp=2942642207&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:2942642207

VL - 32

SP - 318

EP - 322

JO - Tien Tzu Hsueh Pao/Acta Electronica Sinica

JF - Tien Tzu Hsueh Pao/Acta Electronica Sinica

SN - 0372-2112

IS - 2

ER -