|
Abstract : |
Multistage networks (MIN) are used as interconnection structure in a large number of applications. Their performance is mainly determined by their communication throughput which, in most cases, has to be investigated by time-consuming simulations or approximated by simple models. In this paper, we investigate the steady state throughput of single buffered multistage interconnection networks using the so called relaxed blocking model, where a message is deleted, if the receiving buffer is occupied. We derive upper and lower bounds on the throughput of MINs of arbitrary height and show that the throughput of singlebuffered networks is an order of magnitude higher than the throughput of non-buffered MINs. In detail we show, that the throughput is \Theta(n= p log n) if n is the size of the network. Because the time-dynamic of finite buffered MINs defies each marcov- or semi-marcov approach, we analyze the the equilibrium-situation of the network and give tight upper and lower bounds on the steady state distribution of, |
