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

Recently, wormhole routers with multidestination capability have been propo sed to support fast multicast in a multicomputer network. To avoid communic ation deadlock, existing results have proposed to construct a Hamilton path , Euler path, trip, or their variants in the network, perhaps with some deg ree of support of virtual channels [1], [14], [15], [18], [23]. In this pap er, we identify that a network which is itself Eulerian or is Eulerian afte r 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 dime nsion with regular fault patterns (such as single node, block, L-shape, T-s hape, +-shape, U-shape, and H-shape) and even irregular fault patterns. The result improves over existing results on the requirement of support of vir tual channels and fault-tolerant capability. Simulation results on tori are presented.