Solution of Large Markov Models for Computer Performance and Dependability Analysis

在设计阶段早期评估选项的能力是 对于当今复杂的计算机通信系统至关重要。 模型需要能够指定和分析设计 在实际投入大量资金之前， 系统的构建。 性能和可靠性 系统设计评估的两个主要标准，以及 评估的主要方法是模拟， 随机建模 最广泛使用的一类随机 模型是马尔可夫链 马尔可夫模型有其 限制，但在适用的情况下，它们通常较少 成本比模拟高，也有理论基础 允许我们考虑形式上的误差界限、灵敏度 马尔可夫模型的主要局限性是 所需的计算机内存和处理器时间 表示和求解模型。 所需数量 随着模型的复杂性， 不幸的是，真实的系统的模型往往 复杂. 这项研究的主旨是发展分析 这些技术极大地扩展了模型的范围， 用马尔可夫链数值方法进行分析。 唯一的办法 处理状态空间爆炸问题的方法是利用 感兴趣的特定类别问题的性质。 虽然识别和利用 特别的问题结构，这项研究的成功 也将通过结果的一般性来判断，即， 处理尽可能广泛的一类问题的能力。 这里采用的方法是检查几类 计算机系统性能的重要问题， 可靠性建模，并表明，每个特定的属性， 这些问题类建议的分析方法，将 允许计算模型解的紧界 这是不可能通过标准数值计算来解决的 解决方法 这项研究的结果将提供 在一组应用程序上的两个特定结果（可靠性 分析、负载平衡、并行处理和协议 分析），这是非常感兴趣的本身，但即使 更重要的是，将有助于正式的机构， 这些技术将为先进的设计提供基础 分析工具。

The ability to evaluate options early in the design phase is essential for today's complex computer-communication systems. Models are required to be able to specify and analyze designs prior to expending large amounts of capital on actual construction of the system. Performance and reliability are two of the major criteria for system design evaluation, and the main approaches to evaluation are simulation and stochastic modeling. The most widely used class of stochastic models is Markov chains. Markov models have their limitations, but where applicable they are generally less costly than simulation and also have a theoretical foundation that permits one to consider formal error bounds, sensitivity analysis, etc. The main limitation of Markov models is the amount of computer memory and processor time required for representing and solving the models. The amount of required resources grows very rapidly with the complexity of the model and unfortunately, models of real systems are often quite complex. The thrust of this research is to develop analysis techniques which greatly extend the range of models that can be analyzed with Markov chain numerical methods. The only way to deal with the state space explosion problem is to exploit properties of the particular class of problems of interest. Although it is often effective to identify and take advantage of special problem structures, the success of this research will also be judged by the generality of the results, i.e., the ability to handle as wide a class of problems as possible. The approach taken here is to examine several classes of important problems in computer system performance and reliability modeling and show that certain properties of each of these problem classes suggest methods of analysis that will permit computation of tight bounds on the solution of models that would be impossible to solve via standard numerical solution methods. The results of this research will provide both specific results on a set of applications (dependability analysis, load balancing, parallel processing and protocol analysis) that are of great interest by themselves but even more importantly will contribute to the body of formal techniques that will provide the basis for advanced design analysis tools.