An Euler-path-based multicasting model for wormhole-routed networks with multi-destination capability

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

11 Scopus citations

Abstract

Recently, wormhole routers with multi-destination capability have been proposed to support fast multicast in a multi-computer network. In this paper, we develop a new multicasting model for such networks based on the concept of Euler path/circuit in graph theory. The model can support multiple concurrent multicasts freely from deadlock and can be applied to any network which is Eulerian or is Eulerian after some links being removed. No virtual channels are needed. In particular, we demonstrate the potential of this model by showing its fault-tolerant capability in supporting multicasting in the currently popular torus/mesh topology of any dimension with regular fault patterns (such as single node, block, L-shape, +-shape, U-shape, and H-shape) and even irregular fault patterns. The result has improved over existing fault-tolerant routing algorithms for meshes/tori in at least one of the following aspects: the number of faults tolerable, the shape of fault patterns, the number of deactivated healthy nodes, the requirement of support of virtual channels, and the range of network topology acceptable.

Original languageEnglish
Title of host publicationProceedings - 1998 International Conference on Parallel Processing, ICPP 1998
EditorsTen H. Lai
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages366-373
Number of pages8
ISBN (Electronic)0818686502
DOIs
StatePublished - 1 Jan 1998
Event1998 International Conference on Parallel Processing, ICPP 1998 - Minneapolis, United States
Duration: 10 Aug 199814 Aug 1998

Publication series

NameProceedings of the International Conference on Parallel Processing
ISSN (Print)0190-3918

Conference

Conference1998 International Conference on Parallel Processing, ICPP 1998
CountryUnited States
CityMinneapolis
Period10/08/9814/08/98

Fingerprint Dive into the research topics of 'An Euler-path-based multicasting model for wormhole-routed networks with multi-destination capability'. Together they form a unique fingerprint.

Cite this