Performance of Congestion Control Mechanisms in Wormhole Routing Networks

In order to minimize latency in high-speed interconnection networks, the wormhole routing technique can be employed. With this technique, a switch transmits an incoming message as soon as it receives it, without waiting for the entire message. The problem then is that a message stretches over several links and locks network resources, thus making a contention situation possible. Two principal congestion control mechanisms can be considered, backpressure flow control and deflection routing. The performance of these mechanisms depends both on the traffic characteristics and on the network topology. In order to compare them, we study analytically the behavior of a wormhole routing network model with random input traffic under both policies. We estimate the probability of collision between messages and express the average message transit delay as a function of the offered load. Simulation provides a good confirmation for the analytical results. This study gives us an understanding of the ..