Jonatha Anselmi Anselmi
Abstract
We consider Jackson queueing networks (JQN) with finite capacity constraints and analyze the temporal computational complexity of sampling from their stationary distribution. In the context of perfect sampling, the monotonicity of JQNs ensures that it is the coupling time of extremal sample-paths. In the context of approximate sampling, it is given by the mixing time. We give a sufficient condition to prove that the coupling time of JQNs with M queues is O(M ∑Mi=1 Ci), where Ci denotes the capacity (buffer size) of queue i. This condition lets us deal with networks having arbitrary topology, for which the best bound known is exponential in the Ci's or in M. Then, we use this result to show that the mixing time of JQNs is log2 1/∈ O(M ∑Mi=1 Ci), where ∈ is a precision threshold. The main idea of our proof relies on a recursive formula on the coupling times of special sample-paths and provides a methodology for analyzing the coupling and mixing times of several monotone Markovian networks.
- S. Andradóttir and M. Hosseini-Nasab. Efficiency of time segmentation parallel simulation of finite markovian queueing networks. Operation Research, 51(2):272--280, 2003. Google Scholar
Digital Library
- G. Bolch, S. Greiner, H. de Meer, and K. Trivedi. Queueing Networks and Markov Chains. Wiley-Interscience, 2005. Google ScholarDigital Library
- P. Bremaud. Markov Chains, Gibbs Fields, Monte Carlo Simulation and Queues. Texts in Applied Mathematics. Springer-Verlag, Berlin-Heidelberg, 1999.Google Scholar
- S. Kijima and T. Matsui. Approximation algorithm and perfect sampler for closed jackson networks with single servers. SIAM J. Comput., 38(4):1484--1503, 2008. Google ScholarDigital Library
- D. A. Levin, Y. Peres, and E. L. Wilmer. Markov Chains and Mixing Times. American Math. Soc., 2008.Google ScholarCross Ref
- J. G. Propp and D. B. Wilson. Exact sampling with coupled markov chains and applications to statistical mechanics. Rand. Struct. Alg., 9(1-2):223--252, 1996. Google ScholarDigital Library
Index Terms
- On the efficiency of perfect simulation in monotone queueing networks
Recommendations
Efficiency of simulation in monotone hyper-stable queueing networks
We consider Jackson queueing networks with finite buffer constraints (JQN) and analyze the efficiency of sampling from their stationary distribution. In the context of exact sampling, the monotonicity structure of JQNs ensures that such efficiency is of ...
A multiserver retrial queue: regenerative stability analysis
We consider a multiserver retrial GI / G / m queue with renewal input of primary customers, interarrival time with rate $\lambda=1/\mathsf{E}\tau$ , service time S , and exponential retrial times of customers blocked in the orbit. In the model, an arriving primary ...
Perfect sampling of Jackson queueing networks
We consider open Jackson networks with losses with mixed finite and infinite queues and analyze the efficiency of sampling from their exact stationary distribution. We show that perfect sampling is possible, although the underlying Markov chain may have ...
Comments