The Message Flow Model for Routing in Wormhole-Routed Networks

Abstract

In this paper, we introduce a new approach to deadlock-free routing in wormhole-routed networks called the message flow model. We first establish the necessary and sufficient condition for deadlock-free routing based on the analysis of the message flow on each channel. We then show how to use the model to prove that a given adaptive routing algorithm is deadlock-free. Finally, we use the method to develop new, efficient adaptive routing algorithms for 2D meshes and hypercubes.