Preventing congestion in multistage networks in the presence of hotspots

Abstract

The authors present a method of switching data packets through a MIN (multistage interconnection network) that avoids tree saturation and ensures that hot-spot traffic can be supported with little degradation to uniform traffic that is equiprobably directed to other output ports of the network. An incoming packet is accepted at a switch buffer only if the buffer does not contain a packet destined for the same output port as the incoming packet, and rejected packets are rotated to the tail of the buffer. This simple method prevents tree saturation and the consequent loss of throughput for the uniform traffic. This policy has some adverse effects on the throughput when there are no hot spots. These adverse effects are alleviated by extensions to the basic scheme.