Achieving fault-tolerant multicast in injured wormhole-routed tori and meshes based on euler path construction

Yu-Chee Tseng*, Ming Hour Yang, Tong Ying Juang

*Corresponding author for this work

Research output: Contribution to journalArticle

8 Scopus citations

Abstract

Recently, wormhole routers with multidestination capability have been proposed to support fast multicast in a multicomputer network. To avoid communication deadlock, existing results have proposed to construct a Hamilton path, Euler path, trip, or their variants in the network, perhaps with some degree of support of virtual channels [1], [14], [15], [18], [23]. In this paper, we identify that a network which is itself Eulerian or is Eulerian after some links are removed, can enjoy the multidestination capability without support of virtual channels. From this definition, we then develop several techniques to achieve fault-tolerant multicast in a torus/mesh of any dimension with regular fault patterns (such as single node, block, L-shape, T-shape, +-shape, U-shape, and H-shape) and even irregular fault patterns. The result improves over existing results on the requirement of support of virtual channels and fault-tolerant capability. Simulation results on tori are presented.

Original languageEnglish
Pages (from-to)1282-1293
Number of pages12
JournalIEEE Transactions on Computers
Volume48
Issue number11
DOIs
StatePublished - 1 Nov 1999

Keywords

  • Euler path
  • Fault tolerance
  • Mesh
  • Multicast
  • Multicomputer network
  • Torus
  • Virtual channel
  • Wormhole routing

Fingerprint Dive into the research topics of 'Achieving fault-tolerant multicast in injured wormhole-routed tori and meshes based on euler path construction'. Together they form a unique fingerprint.

  • Cite this