Minimal, Deadlock-Free Routing in Hypercubic and Arbitrary Networks

In this paper we consider the problem of creating minimal, deadlock-free routing algorithms, where a routing algorithm is said to be minimal if it uses only shortest paths. In particular, we examine the possibility of creating scalable algorithms that use only a constant number of buffers per node. Minimal, scalable, deadlock-free routing algorithms are known for many important networks including meshes, tori, trees and hypercubes. In addition, it is known that a scalable, deadlock-free routing algorithm exists for every network. However, it is unknown whether or not a minimal, scalable, deadlock-free routing algorithm exists for every network, and no such algorithm is known for the de Bruijn or shuffle-exchange networks. We present three main results. First, we prove that there is no minimal, scalable, deadlock-free routing algorithm for the hypercube that uses only the standard Ascend (dimension-order) paths. Second, we prove that there exist networks for which no minimal, scalable, ..