Title :
An Euler-path-based multicasting model for wormhole-routed networks: its applications to damaged 2D Tori and meshes
Author :
Juang, Tong-Ying ; Tseng, Yu-Chee ; Yang, Ming-Hour
Author_Institution :
Dept. of Comput. Sci., Chung-Hua Polytech. Inst., Taiwan
Abstract :
We develop a new multicasting model for wormhole-routed networks based on the concept of Euler path in graph theory. The model can support multiple multicasts freely from deadlock and can be applied to any network which is Eulerian or is Eulerian after some links being removed. We demonstrate the power of this model by showing its fault-tolerant capability in supporting multicasting in a damaged 2-D torus/meshes with regular fault patterns (such as a single node, block, L-shape, +-shape, U-shape, and H-shape). In this regard, it is the first known multicasting algorithm in the literature with such strong fault-tolerant capability
Keywords :
fault diagnosis; graph theory; network topology; telecommunication channels; telecommunication network routing; +-shape; Euler path based multicasting model; H-shape; L-shape; U-shape; block faults; damaged 2D Tori; damaged 2D meshes; fault patterns; fault tolerant capability; graph theory; multicasting algorithm; multiple multicasts; single node; wormhole routed networks; Application software; Computer science; Costs; Delay; Fault tolerance; Graph theory; Network topology; Routing; Shape; System recovery;
Conference_Titel :
Performance, Computing, and Communications Conference, 1997. IPCCC 1997., IEEE International
Conference_Location :
Phoenix, Tempe, AZ
Print_ISBN :
0-7803-3873-1
DOI :
10.1109/PCCC.1997.581549
