Balls and buckets for discrete time Markov chain generation

Abstract

This work presents an extension of the balls and buckets description formalism to the case of discrete time systems. This formalism allows for flexible modeling and compact representation of Markovian systems, supporting automatic generation of both the state space and the transition matrix of the underlying canonical Markov chain. A discrete time balls and buckets interpreter has been implemented in the BB library, which provides different basic services (Markov chain generation, storage, exact evaluation, and simulation) supporting system description and performance and dependability quantitative analysis. As an application example, we present the balls and buckets model and the performance analysis of an ATM switch architecture, which is of interest in high performance network design. By using simulation techniques, we reproduce results (already established by other methods in the literature) showing that, given a fixed load, the performance of this kind of switches is highly sensitive to the characteristics of the data packets arrival process. `