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.