About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
SIGMETRICS 1991
Conference paper
A Markov chain approximation for the analysis of Banyan networks
Abstract
This paper analyzes the delay suffered by messages in a clocked, packet-switched, square Banyan network with k x k output-buffered switches by approximating the flow processes in the network with Markov chains. We recursively approximate the departure process of buffers of the nth stage in terms of that at the n - 1st stage. We show how to construct the transition matrix for the Markov chain at each stage of the network and how to solve for the stationary distribution of the delay in the queues of that stage. The analytical results are compared with simulation results for several cases. Finally, we give a method based on this approximation and the technique of coupling to compute upper bounds on the time for the system to approach steady state.