This paper consists of two parts. In the first part, two new algorithms for deadlock- and livelock-free wormhole routing in the torus network are presented. The first algorithm, called Channels, is for the n-dimensional torus network. This technique is fully-adaptive minimal, that is, all paths with a minimal number of hops from source to destination are available for routing, and needs only five virtual channels per bidirectional link, the lowest channel requirement known in the literature for fully-adaptive minimal worm-hole routing. In addition, this result also yields the lowest buffer requirement known in the literature for packet-switched fully-adaptive minimal routing. The second algorithm, called 4-Classes, is for the bidimensional torus network. This technique is fully-adaptive minimal and requires only eight virtual channels per bidirectional link. Also, it allows for a highly parallel implementation of its associated routing node. In the second part of this paper, four worm-hole routing techniques for the two-dimensional torus are experimentally evaluated using a dynamic message injection model and different traffic patterns and message lengths.>

This paper consists of two parts. In the first part, a new algorithm for deadlock- and livelock-free routing for the n-dimensional torus network is presented. This algo- rithm, called *-Channels, is fully-adaptive minimal, i.e. all paths with a minimal number of hops from source to destination are available for routing. *-Channels works for messages of unknown size, thus yielding new rout- ing techniques for both packet-switched and worm-hole models. *.Channels differs radically from the packetswitched fully-adaptive minimal methods presented in SPAA '91 by Pifarr6, Gravano, Felperin, and Sanz [PGFS91]. In particular, the packet-based techniques in [PGFS91] do not work for worm-hole routing as dead- lock situations can be constructed.