Perfect Sampling of Phase-Type Servers Using Bounding Envelopes
Perfect Sampling of Phase-Type Servers Using Bounding Envelopes
复制标题
使用边界包络对阶段型服务器进行完美采样
DOI：
10.1007/978-3-642-21713-5_14
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
J. Vincent
中科院分区：
文献类型：
--
作者：
B. Gaujal;Gaël Gorgo;J. Vincent
在服务模型中，相位型服务器是非常有用的，因为它们可以用来近似现实生活中的电信网络的任何服务分布。然而，相应的马尔可夫链在大多数情况下是非常大的，很难解决没有一个有效的仿真模型的帮助。已经制定了一个基于完美抽样的模拟框架，以处理大型模拟模型的评价问题。完美的采样使我们能够从所有可能的状态开始，基于马尔可夫链轨迹的后向耦合计算平稳分布的无偏样本。我们使用一个优化算法，其中包括在计算一组极值包络约束所有的轨迹，以获得耦合。当链是单调的，包络线直接由来自极端状态的轨迹获得。在本文中，我们证明了相型系统在结构上是非单调的，即使是最简单的相型分布，如Erlang，超指数或Coxian-type分布。然后，我们提供了一个通用的方法来计算的上，下包络的一般有限相位型服务的嵌入式网络。这使得完美的采样，这样的系统和它的效率是通过几个例子来说明。
In queueing models, phase-type servers are very useful since they can be used to approximate any service distributions of real-life telecommunication networks. However, the corresponding Markov chains are in most cases very large and hard to solve without the help of an efficient simulation model. A simulation framework, based on perfect sampling, had already been developed to address the evaluation of large queueing models. Perfect sampling enables us to compute unbiased samples of the stationary distribution based on a backward coupling of the Markov chain trajectories, starting from all possible states. We use an optimized algorithm which consists in computing a set of extremal envelopes which bound all trajectories to obtain the coupling. When the chain is monotone, the envelopes are directly obtained by the trajectories coming from the extremal states. Otherwise, envelopes are upper and lower bounds over the whole set of trajectories.In this article we prove that phase-type systems are structurally non monotone even with the simplest phase-type distributions like Erlang, hyper-exponential or Coxian-type distributions. Then we provide a generic method for the computation of the upper and lower envelopes for general finite phase-type services in queueing networks. This allows the perfect sampling of such systems and its efficiency is illustrated through several examples.