Deadlock probability in unrestricted wormhole routing networks

To minimize latency in local area networks, the wormhole routing technique can be used. Drawbacks of this technique are the blocking of messages and, if backpressure flow control is used, the possibility of deadlock. Two principal mechanisms can be employed to deal with deadlocks, namely a deadlock-free routing scheme or a deadlock resolution mechanism. The relative performance of these two mechanisms depends mainly on the deadlock frequency. In this paper, we study analytically the probability of deadlock in an unrestricted wormhole routing network. We capture the topology of the system in two parameters with intuitive meaning, and we derive a closed form expression for an upper bound of the deadlock probability. Simulation runs with different topologies provide good confirmation for the analytical results