Fault-tolerant and deadlock-free routing in 2-D meshes using rectilinear-monotone polygonal fault blocks

Jie Wu, Dajin Wang

Research output: Contribution to journalArticle

7 Citations (Scopus)

Abstract

We propose a deterministic fault-tolerant and deadlock-free routing protocol in 2-dimensional (2-D) meshes based on Wu's fault-tolerant odd-even turn model and Wang's rectilinear-monotone polygonal fault block model. The fault-tolerant odd-even turn protocol, also called extended X-Y routing, was originally proposed to achieve fault-tolerant and deadlock-free routing among traditional, rectangular fault blocks. It uses no virtual channels. The number of faults to be tolerated is unbounded as long as nodes outside fault blocks are connected in the mesh network. The recently proposed rectilinear-monotone polygonal fault blocks (also called minimal-connected-components or MCCs) are of the polygonal shapes, and are a refinement of rectangular fault blocks. The formation of MCCs depends on the relative locations of source and destination, and MCCs include far fewer healthy nodes in resultant fault blocks. In this paper, we show that with a simple modification, the extended X-Y routing can also be applied to 2-D meshes using extended MCCs.

Original languageEnglish
Pages (from-to)99-111
Number of pages13
JournalInternational Journal of Parallel, Emergent and Distributed Systems
Volume20
Issue number2
DOIs
StatePublished - 1 Jun 2005

Fingerprint

Routing protocols
Network protocols

Keywords

  • Deadlock-free routing
  • Deterministic routing
  • Fault models
  • Fault tolerance
  • Turn models
  • Virtual channels

Cite this

@article{047ce2b131434d0c85d67d1bf7c85358,
title = "Fault-tolerant and deadlock-free routing in 2-D meshes using rectilinear-monotone polygonal fault blocks",
abstract = "We propose a deterministic fault-tolerant and deadlock-free routing protocol in 2-dimensional (2-D) meshes based on Wu's fault-tolerant odd-even turn model and Wang's rectilinear-monotone polygonal fault block model. The fault-tolerant odd-even turn protocol, also called extended X-Y routing, was originally proposed to achieve fault-tolerant and deadlock-free routing among traditional, rectangular fault blocks. It uses no virtual channels. The number of faults to be tolerated is unbounded as long as nodes outside fault blocks are connected in the mesh network. The recently proposed rectilinear-monotone polygonal fault blocks (also called minimal-connected-components or MCCs) are of the polygonal shapes, and are a refinement of rectangular fault blocks. The formation of MCCs depends on the relative locations of source and destination, and MCCs include far fewer healthy nodes in resultant fault blocks. In this paper, we show that with a simple modification, the extended X-Y routing can also be applied to 2-D meshes using extended MCCs.",
keywords = "Deadlock-free routing, Deterministic routing, Fault models, Fault tolerance, Turn models, Virtual channels",
author = "Jie Wu and Dajin Wang",
year = "2005",
month = "6",
day = "1",
doi = "10.1080/17445760500033341",
language = "English",
volume = "20",
pages = "99--111",
journal = "International Journal of Parallel, Emergent and Distributed Systems",
issn = "1744-5760",
publisher = "Taylor and Francis Ltd.",
number = "2",

}

TY - JOUR

T1 - Fault-tolerant and deadlock-free routing in 2-D meshes using rectilinear-monotone polygonal fault blocks

AU - Wu, Jie

AU - Wang, Dajin

PY - 2005/6/1

Y1 - 2005/6/1

N2 - We propose a deterministic fault-tolerant and deadlock-free routing protocol in 2-dimensional (2-D) meshes based on Wu's fault-tolerant odd-even turn model and Wang's rectilinear-monotone polygonal fault block model. The fault-tolerant odd-even turn protocol, also called extended X-Y routing, was originally proposed to achieve fault-tolerant and deadlock-free routing among traditional, rectangular fault blocks. It uses no virtual channels. The number of faults to be tolerated is unbounded as long as nodes outside fault blocks are connected in the mesh network. The recently proposed rectilinear-monotone polygonal fault blocks (also called minimal-connected-components or MCCs) are of the polygonal shapes, and are a refinement of rectangular fault blocks. The formation of MCCs depends on the relative locations of source and destination, and MCCs include far fewer healthy nodes in resultant fault blocks. In this paper, we show that with a simple modification, the extended X-Y routing can also be applied to 2-D meshes using extended MCCs.

AB - We propose a deterministic fault-tolerant and deadlock-free routing protocol in 2-dimensional (2-D) meshes based on Wu's fault-tolerant odd-even turn model and Wang's rectilinear-monotone polygonal fault block model. The fault-tolerant odd-even turn protocol, also called extended X-Y routing, was originally proposed to achieve fault-tolerant and deadlock-free routing among traditional, rectangular fault blocks. It uses no virtual channels. The number of faults to be tolerated is unbounded as long as nodes outside fault blocks are connected in the mesh network. The recently proposed rectilinear-monotone polygonal fault blocks (also called minimal-connected-components or MCCs) are of the polygonal shapes, and are a refinement of rectangular fault blocks. The formation of MCCs depends on the relative locations of source and destination, and MCCs include far fewer healthy nodes in resultant fault blocks. In this paper, we show that with a simple modification, the extended X-Y routing can also be applied to 2-D meshes using extended MCCs.

KW - Deadlock-free routing

KW - Deterministic routing

KW - Fault models

KW - Fault tolerance

KW - Turn models

KW - Virtual channels

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

U2 - 10.1080/17445760500033341

DO - 10.1080/17445760500033341

M3 - Article

AN - SCOPUS:27844432698

VL - 20

SP - 99

EP - 111

JO - International Journal of Parallel, Emergent and Distributed Systems

JF - International Journal of Parallel, Emergent and Distributed Systems

SN - 1744-5760

IS - 2

ER -