A Universal Proof Technique for Deadlock-Free Routing in Interconnection Networks
Abstract
An important open problem in interconnection network routing has been
to characterize the conditions under which routing algorithms are
deadlock-free. Although this problem has been resolved for restricted
classes of routing algorithms, no general solution has been found. In
this paper, we solve this problem by proving a necessary and
sufficient condition that can be used for any interconnection network
routing algorithm, as long as only local information is required for
routing. Our proof technique is universal: it can be used with any
switching technique that is not inherently deadlock-free. This
includes switching techniques such as wormhole routing,
store-and-forward routing, and virtual cut-through. The proof
technique for the necessary and sufficient condition introduces a new
type of dependency graph, the buffer waiting graph, which omits
most dependencies that cannot be used to create a deadlock
configuration. Our methodology is illustrated by proving deadlock
freedom for a store-and-forward routing algorithm for meshes and a
wormhole routing algorithm for hypercubes. The hypercube routing
algorithm requires only two virtual channels per physical channel and
is more adaptive than any previously proposed wormhole routing
algorithm for hypercubes.
Return to the Publication list.
Last updated by Loren Schwiebert Email: 
on Jun-06-2001