A new theory of deadlock-free adaptive multicast routing in wormhole networks

A theory for the design of deadlock-free adaptive routing algorithms for wormhole networks has been proposed previously. This theory supplies the sufficient conditions for an adaptive routing algorithm to be deadlock-free, even when there are cyclic dependencies between channels. Also, two design methodologies have been proposed. Multicast communication refers to the delivery of the same message from one source node to an arbitrary number of destination nodes. Two multicast wormhole routing methods have been presented previously for multicomputers with 2D-mesh and hypercube topologies. This paper develops the theoretical background for the design of deadlock-free adaptive multicast routing algorithms for wormhole networks. Some basic definitions and two theorems are proposed, developing conditions to verify that an adaptive multicast routing algorithm is deadlock-free, even when there are cyclic dependencies between channels. As an example, the multicast routing algorithms presented previously are extended, so that they can take advantage of the alternative paths offered by the network