An Euler-path-based multicasting model for wormhole-routed networks: Its applications to damaged 2D tori and meshes

In this paper, 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 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.