Approximate/perfect samplers for closed Jackson networks

Author

Kijima, Shuji ; Matsui, Tomomi

Author_Institution

Dept. of Math. Informatics, Tokyo Univ., Japan

fYear

2005

fDate

4-7 Dec. 2005

Abstract

In this paper, we propose two samplers for the product-form solution of basic queueing networks, closed Jackson networks with multiple servers. Our approach is sampling via Markov chain, but it is not a simulation of behavior of customers in queueing networks. We propose two of new ergodic Markov chains both of which have a unique stationary distribution that is the product form solution of closed Jackson networks. One of them is for approximate sampling, and we show it mixes rapidly. To our knowledge, this is the first approximate polynomial-time sampler for closed Jackson networks with multiple servers. The other is for perfect sampling based on monotone CFTP (coupling from the past) algorithm proposed by Propp and Wilson,and we show the monotonicity of the chain.

Keywords

Markov processes; computer networks; network servers; polynomial approximation; queueing theory; sampling methods; statistical distributions; Markov chain; approximate polynomial-time sampler; approximate sampling; basic queueing network; closed Jackson network; ergodic Markov chains; monotone coupling from the past; perfect sampling; product-form solution; stationary distribution; Algorithm design and analysis; Informatics; Information science; Monte Carlo methods; Network servers; Polynomials; Queueing analysis; Sampling methods; Steady-state; Throughput;

fLanguage

English

Publisher

ieee

Conference_Titel

Simulation Conference, 2005 Proceedings of the Winter

Print_ISBN

0-7803-9519-0

Type

conf

DOI

10.1109/WSC.2005.1574333

Filename

1574333