State representation tradeoffs in Markov chains of serialization delays in computer systems

Abstract

A large class of non-product form queueing network models arising in computer system modelling can be analysed approximately, yet with high accuracy, using the well known hierarchical decomposition method. The solution cost of this method is determined by the number of states in the higher level Markov chain model. This number can be reduced by lumping the states of the Markov chain or by adopting a compact state representation, which is the case in this paper. The adoption of different state representations is illustrated in the framework of a computer system with serialization delays, modelled as a closed queueing network with multiple job types. Five state representations are proposed and the corresponding number of states are enumerated using generating functions. Numerical examples are provided to compare the accuracy of performance measures obtained by the most and the least detailed state representation. The least detailed state representation results in a reduction in the number of states by several orders of magnitude compared to the most detailed state representation. The reduction in the solution cost for the considered cases clearly outweighs the possible reduction in accuracy of the solution for secondary performance measures.