Solutions of large and non-Markovian performance models

Analytical modeling is a fast and cost-effective method of evaluating the performance of computer and communication systems. Some of the challenges for research in analytical modeling of performance are largeness of models, non-Markovian behavior and obtaining of detailed measures such as response time distributions and transient measures. In this thesis, we present solutions for specific problems in each of these categories.; Iterative techniques are used to tackle the problems of largeness of the state-space underlying stochastic reward net models of systems. In the case of fixed-point iteration, it is essential to prove the existence of a solution to the fixed-point equation. In this thesis, we establish sufficient conditions in terms of stochastic reward net entities for the existence of a solution to a fixed point equation. Such iterative modeling has been used before, for instance, for modeling the availability of VAXclusters at DEC.; We use stochastic reward nets to model the performance of a heterogeneous multiprocessor system with priority scheduling of tasks. The tasks in the system can spawn and/or branch into other tasks. This structure was a generalization of the task system of a railway interlocking computer designed by Union Switch and Signal. We used fixed-point iteration to solve the problem of largeness of the model, and use the theoretical results that we established to prove the existence of a solution.; Sensitivity analysis of performance measures can provide intermediate feedback to the designer for choosing system parameters that optimize performance. We derive equations for the sensitivity analysis of steady-state probabilities of the Markov regenerative stochastic Petri net. These can be implemented directly in a tool that solves Markov regenerative stochastic Petri nets because it requires the same numerical solvers as are required for steady-state analysis of Markov regenerative stochastic Petri nets.; Real-time systems offer unique challenges to analytical modeling because of the deterministic timing associated with periodic tasks. We use deterministic and stochastic Petri nets and the Markov regenerative theory in presenting detailed performance analysis of real-time systems, including their time-dependent behavior, and the response time distribution of aperiodic tasks. This work is being referred to as one of the initial steps in formal verification methods for temporal characteristics of real-time systems by members of the Honeywell Technology Center.; Finally we present an approximation technique for computation of sojourn time distribution in Markovian and non-Markovian open queueing networks. In the case of Markovian queueing networks, the technique consists of mapping the queuing network to a continuous-time Markov chain. We then use an existing implementation of a continuous-time Markov chain transient solution to compute the sojourn time distribution. In the case of non-Markovian queueing networks, the technique consists of mapping the queueing network to a semi-Markov process. We needed to implement a transient solution method for a semi-Markov process. In both cases, the number of states in the (semi-)Markov chain is linear in the number of nodes in the queueing network. The approximation works well, and offers a viable alternative to simulation. This work was carried out with a goal of possible inclusion in performance analysis software package being developed at IBM.