The Importance Sampling Simulation of MMPP/D/1 Queueing

Kenji NAKAGAWA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E80-A   No.11   pp.2238-2244
Publication Date: 1997/11/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
Category: Stochastic Process/Signal Processing
Keyword: 
simulation,  queueing,  importance sampling,  MMPP,  large deviations theory,  

Full Text: PDF>>
Buy this Article




Summary: 
We investigate an importance sampling (IS) simulation of MMPP/D/1 queueing to obtain an estimate for the survivor function P(Q > q) of the queue length Q in the steady state. In Ref.[11], we studied the IS simulation of 2-state MMPP/D/1 queueing and obtained the optimal simulation distribution, but the mathematical fundation of the theory was not enough. In this paper, we construct a discrete time Markov chain model of the n-state MMPP/D/1 queueing and extend the results of Ref.[11] to the n-state MMPP/D/1. Based on the Markov chain model, we determine the optimal IS simulation distribution fo the n-state MMPP/D/1 queueing by applying the large deviations theory, especially, the sample path large deviations theory. Then, we carry out IS simulation with the obtained optimal simulation distribution. Finally, we compare the simulation results of the IS simulation with the ordinary Monte Carlo (MC) simulation. We show that, in a typical case, the ratio of the computation time of the IS simulation to that of the MC simulation is about 10-7, and the 95% confidence interval of the IS is slightly improved compared with the MC.