BLOCKING IN ASYNCHRONOUS, BUFFERED BANYAN NETWORKS

An approximate algorithm is developed for the performance analysis of buffered, packet-switched, asynchronous networks with no feedback. We focus on banyan networks which are important in parallel computer architectures and telecommunication systems to illustrate our approach and our algorithm is tailored to this problem. The networks we consider are organised in a finite number of stages through each of which a task passes successively in its transmission. The components which forward messages in each stage are modelled independently as small sub-networks of queues; these components are crossbars in the case of Banyan networks. Blocking can occur on several upstream paths preceding a full component and this effect is represented by considering joint distributions of queue lengths in each stage. The inter-stage blocking effect is taken into account by the iterative algorithm. The networks we consider may be non-homogeneous in that different servers may have different rates and the arrival processes need not be identical. Service times are restricted to two-phase Coxian for computational tractability. We derive the queue length probability distribution of each switch from which the usual performance measures, such as throughput and mean transmission time, follow.