Analytical models of combining banyan networks

Abstract

We present in this paper an analytical model of a multistage combhting Banyan network with output buffered switches, in hot-spot traffic. In a combining network, packets bound for the same destination are combined into one if they meet at a switch; this alleviates the problem of tree-sat ur:ation caused by hot-spot traffic. We model the flow processes in the network as Markov chains and recursively approximatee the departure processes of each stage of the network in terms of the departure processes of the preceding stage. This model is used to predict the throughput of the combining network, and comparison with simulation results shows the prediction to be accurate. A modified combining scheme based on low priorities for hot packets is proposed and analyzed. It is shown that this scheme yields substantial improvements in throughput over the standard combining scheme.