Modeling message blocking and deadlock in interconnection networks

This paper presents an approach to modeling resource allocations and dependencies within cut-through and wormhole interconnection networks. This model allows various types of message blocking to be represented precisely, including deadlock. Our model of deadlock distinguishes between messages involved in deadlock and those simply dependent on deadlock, thus providing specification criteria for precise deadlock detection and recovery. The model and its implementation in a network simulator are described. Time and space complexity of the implementation is also discussed.