Bounds for Point and Steady-State Availability: An Algorithmic Approach Based on Lumpability and Stochastic Ordering
Bounds for Point and Steady-State Availability: An Algorithmic Approach Based on Lumpability and Stochastic Ordering
复制标题
点和稳态可用性的界限：基于集总性和随机排序的算法方法
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
J. Fourneau
中科院分区：
文献类型：
--
作者：
A. Bušić;J. Fourneau
马尔可夫链和奖励已被广泛用于评估计算机系统和网络的性能、可靠性和可执行性特征。尽管进行了大量工作，但当马尔可夫链较大或特征值分布不良时，对马尔可夫链进行数值分析以获得瞬态或稳态分布仍然是一个难题。因此，长期以来一直提出边界技术来分析稳态分布。
在这里，我们展示了如何使用算法方法来限制一些可靠性特征，例如稳态和点可用性。该界限基于马尔可夫链的随机比较，但它不使用样本路径参数。该算法构建了一个集总马尔可夫链，其稳态或瞬态分布是精确分布的强随机意义上的上限。在本文中，详细介绍了算法的实现，并展示了一些数值结果。我们还展示了如何避免生成状态空间和转换矩阵来对具有超过 1010 个状态的模型链进行建模。
Markov chains and rewards have been widely used to evaluate performance, dependability and performability characteristics of computer systems and networks. Despite considerable works, the numerical analysis of Markov chains to obtain transient or steady-state distribution is still a difficult problem when the chain is large or the eigenvalues badly distributed. Thus bounding techniques have been proposed for long to analyze steady-state distribution.
Here, we show how to bound some dependability characteristics such as steady-state and point availability using an algorithmic approach. The bound is based on stochastic comparison of Markov chains but it does not use sample-path arguments. The algorithm builds a lumped Markov chain whose steady-state or transient distributions are upper bounds in the strong stochastic sense of the exact distributions. In this paper, the implementation of algorithm is detailed and we show some numerical results. We also show how we can avoid the generation of the state space and the transition matrix to model chains with more than 1010 states.