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.