On different models for packet flow in Multistage Interconnection Networks

• Autorzy: Dietzfelbiner M , Gambin A. , Lasota S.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

multistage interconnection networks; continuous routing; throughput; Markov chains

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2001
• Tom: Vol. 46, nr 4
• Strony: 287--314
• Opis fizyczny: wykr., bibliogr. 25 poz.

Twórcy

autor

Dietzfelbiner M

autor

Gambin A.

autor

Lasota S.

• Institute of Informatics, Warsaw University, 02-097 Warsaw Banacha 2, Poland,