Solution of Large Markov Models using Lumping Techniques and Symbolic Data Structures

Continuous time Markov chains (CTMCs) are among the most fundamental mathematical structures used for performance and dependability modeling of communication and computer systems. They are often constructed from models described in one of the various high-level formalisms. Since the size of a CTMC usually grows exponentially with the size of the corre-sponding high-level model, one often encounters the infamous state-space explosion problem, which often makes solution of the CTMCs intractable and sometimes makes it impossible. In state-based numerical analysis, which is the solution technique we have chosen to use to solve for measures defined on a CTMC, the state-space explosion problem is manifested in two ways: 1) large state transition rate matrices, and 2) large iteration vectors. The goal of this dissertation is to extend, improve, and combine existing solutions of the state-space explosion problem in order to make possible the construction and solution of very large CTMCs generated from high-level models. Our new techniques follow largeness avoidance and largeness tolerance approaches. In the former approach, we reduce the size of the CTMC that needs to be solved in order to compute the measures of interest. Tha