On Different Models for Packet Flow in Multistage Interconnection Networks

Article type: Research Article

Authors: Dietzfelbinger, Martin | Gambin, Anna | Lasota, Sławomir

Abstract: Multistage interconnection networks (MINs) have a number of applications in many areas, for example in parallel computing systems or high-speed communication networks. In the paper we define Markov chains describing several models of packet flow through the buffered MIN with a butterfly interconnection structure and 2×2 switching elements. We develop a notation together with a mathematical framework enabling to prove certain results relating the models. Moreover, we show that all considered Markov chains are ergodic and discuss relationships between stationary distributions. The important novelty is that our approach is compositional, which allows to keep the complexity of description of a very complicated network's behaviour on a reasonable and tractable level. Considerations are mostly independent of specific network topology and routing protocol, hence we expect our method to be applicable also in other contexts for stochastic models of massively parallel systems.

Keywords: Multistage Interconnection Networks, continuous routing, throughput, Markov chains

Journal: Fundamenta Informaticae, vol. 46, no. 4, pp. 287-314, 2001