An Analytical Performance Model for Multistage Interconnection Networks with Blocking

Multistage Interconnection Networks (MINs) allow efficient communication between network components and also among the components of parallel systems. This paper presents an approximate performance model for self routing multistage interconnection networks, applied for 2 x 2 switches which are subject to blocking situations when the packets compete for a full output port of a next stage switch. We apply our model to variable network size MINs and we study the performance under different traffic conditions. In our approximation the bulk of packets that arrive in each cycle to the MIN inputs, follow a Bernoulli distribution. We derive an approximate formula for the utilization of each queue and based on this, we approximate the blocking behavior (probabilities) and the steady-state distributions of populations for each queue of the MIN. This novel analytical model is validated by extensive simulations. Our analytical method gives more accurate results than previous existing analytical models and converges very fast.