AESOP home


Anaytical Models for Multi-Stage Interconnection Networks

Peter G. Harrison

International Seminars on the Teaching of Computing Science: System Modelling

Central to all parallel architectures is a switching network which facilitates the communication between a machine's components necessary to support their cooperation. Multi-stage interconnection networks (MINs) are classified and two queueing models for packet-switched MINs with unlimited buffer space are introduced. The first uses standard techniques and is exact with respect to it assumptions, hence providing a standard against which to access approximate models. From this exact model, we can also obtain distributions of transmission times; previous work has either used simulation, which can be unreliable and is expensive to run, or produced only Laplace transforms. The second model has much milder assumptions, is more generally applicable and can be implemented more efficiently, but is approximate. However, it has been found to give accurate predictions for a wide range of traffic patterns and distributions of link transmission times. Established techniques can be integrated into our queueing-based methodology to model MINs with finite buffers and hence blocking.


PDF from

PDF of full publication (6 megabytes)
(need help viewing PDF files?)

Information from