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