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.