A NECESSARY AND SUFFICIENT CONDITION FOR DEADLOCK-FREE ADAPTIVE ROUTING IN WORMHOLE NETWORKS

Deadlock avoidance is a key issue in wormhole networks. A first approach [8] consists of removing the cyclic dependencies between channels, Many deterministic and adaptive routing algorithms have been proposed based on that approach. Although the absence of cyclic dependencies is a necessary and sufficient condition for deadlock-free deterministic routing, it is only a sufficient condition for deadlock-free adaptive routing. A more powerful approach [11] only requires the absence of cyclic dependencies on a connected channel subset. The remaining channels can be used in almost any way. In this paper, we show that the previously mentioned approach is also a sufficient condition. Moreover, we propose a necessary and sufficient condition for deadlock-free adaptive routing. This condition is the key for the design of fully adaptive routing algorithms with minimum restrictions. An example shows the application of the new theory.