Algorithms for an irreducible and lumpable strong stochastic bound Original Research Article

Despite considerable works, the numerical analysis of large chains remains a difficult problem. Fortunately enough, while modeling computer networks, it is often sufficient to check if the studied mechanism satisfies the requirements of the Quality of Service (QoS) we expect and exact values of the performance indices are not necessary. So we advocate a new method based on the algorithmic derivation of a lumpable stochastic bounding matrix to analyze large state-space problems. Because of the lumpability, the numerical analysis deals with smaller matrices. The stochastic bounds provide upper bounds for performance indices defined as reward functions. Our work is purely algorithmic and algebraic and does not require proofs based on the sample-path theorem and coupling (see [Stoyan, Comparison Methods for Queues and Other Stochastic Models, Wiley, 1983] for some examples). We present the algorithms, time complexity, memory requirements and an example.