Deadlock-Free Oblivious Wormhole Routing with Cyclic
Dependencies
Abstract
A great deal of work has been done recently 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
\emph{unreachable configurations\/} and \emph{false resource cycles}.
In this paper, we apply the notion of unreachable cyclic
configurations to oblivious routing algorithms. An oblivious routing
algorithm is thus constructed that is deadlock-free even though there
are cycles in the channel dependency graph. The idea of unreachable
configurations is then further developed to show various restrictions
on when such configurations can exist with oblivious routing
algorithms. Finally, the example is generalized to allow the
construction of larger networks with unreachable cycles. One benefit
of characterizing when unreachable cyclic configurations can occur is
that proving deadlock freedom is simplified for networks in which
unreachable cycles cannot exist. Another contribution of this work is
a first step toward a more formal model of unreachable cycles in
wormhole-routed networks.
Return to the Publication list.
Last updated by Loren Schwiebert Email: 
on Mar-22-2002