Deadlock-Free Oblivious Wormhole Routing with Cyclic Dependenices
Abstract
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