A fault-tolerant deadlock-free routing algorithm in a meshed network

Deogkyoo Lee, Daekeun Moon, Ilgu Yun, Hagbae Kim

Research output: Contribution to journalArticlepeer-review


Since components faults occurring at arbitrary places (primarily on the links) affect seriously network performance and reliability, the multicomputers operating in harsh environments should be designed to guarantee normal network-missions in presence of those faults. One solution to the end is a fault-tolerant routing scheme, which enables messages to safely reach their destinations avoiding failed links when transmission of messages is blocked by certain faults. In the paper, we develop a fault-tolerant routing algorithm with deadlock freedom in an n-dimensional meshed network, and validate its efficiency and effectiveness through proper simulations. The aspects of fault-tolerance is adopted by appending partial-adaptiveness and detouring to the e-cube algorithm, while using a wormhole routing for the backbone routing method. The phenomenon of deadlock incurred due to its adaptiveness is eliminated by classifying a physical channel into a couple of virtual channels.

Original languageEnglish
Pages (from-to)722-726
Number of pages5
JournalIEICE Transactions on Information and Systems
Issue number4
Publication statusPublished - 2002 Apr

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Vision and Pattern Recognition
  • Electrical and Electronic Engineering
  • Artificial Intelligence


Dive into the research topics of 'A fault-tolerant deadlock-free routing algorithm in a meshed network'. Together they form a unique fingerprint.

Cite this