The Red Rover Algorithm for Deadlock-Free Routing on Bidirectional Rings.
Jeffrey T. Draper · 1996
An algorithm for deadlock-free routing in bidirectional ring structures in multicomputer networks is presented. This algorithm provides greater throughput and lower message latencies than those of previously presented ring routing algorithms. Insight into these results is given by a message traffic analysis, and increased performance for wormhole-routed networks is quantified through simulation experiments. Additionally, a routing element which implements this algorithm is shown to be simpler and faster than that for a currently-used algorithm. Keywords: Multicomputer Networks, Routing, Virtual Channels 1 Introduction First generation distributed-memory multicomputers such as the Cosmic Cube [10] used "store-and-forward" packet-switching methods for routing messages among the multicomputer nodes. The present generation of multicomputers is able to reduce hardware communication overheads of first-generation machines by over two orders of magnitude by employing innovative routing techni...