AN APPROXIMATE ANALYSIS OF ASYNCHRONOUS, PACKET-SWITCHED BUFFERED BANYAN NETWORKS WITH BLOCKING

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 the inter-stage blocking effect is taken into account iteratively, blocking probabilities being computed in terms of results of a previous step. The networks we consider may be non-homogeneous in that different servers may have different rates and the arrival processes need not be identical. We derive the queue length probability distribution of each switch from which performance measures, such as blocking probability, mean buffer occupancy and mean transmission time, follow.