Deadlock-Free Oblivious Wormhole Routing with Cyclic Dependenices


A great deal of recent work has been done on developing techniques for proving deadlock freedom for wormhole routing algorithms. One approach has been to restrict the class of routing algorithms for which the proof technique applies. The other approach is to provide a generic method that can be applied to all routing algorithms. Although this latter approach offers clear advantages, a general technique must deal with many complications. Foremost among these is the issue of irreducible cyclic dependencies that cannot result in deadlock. Such dependencies have been referred to alternatively as unreachable configurations and false resource cycles. In this paper, we apply the notion of unreachable configurations to oblivious routing algorithms and thereby provide a counter-example to Dally and Seitz's [6] theorem for deadlock-free routing in wormhole-routed networks. This idea is then further developed to show various restrictions on when unreachable configurations can exist with oblivious routing algorithms.

Return to the Publication list.

Last updated by Loren Schwiebert Email: on Jun-06-2001