Efficient simulation of a Tandem Jackson Network

Kroese, D. P. and Nicola, V. F. (2002) Efficient simulation of a Tandem Jackson Network. ACM Transactions on Modeling and Computer Simulation, 12 2: 119-141. doi:10.1145/566392.566395


Author Kroese, D. P.
Nicola, V. F.
Title Efficient simulation of a Tandem Jackson Network
Journal name ACM Transactions on Modeling and Computer Simulation   Check publisher's open access policy
ISSN 1049-3301
Publication date 2002
Sub-type Article (original research)
DOI 10.1145/566392.566395
Volume 12
Issue 2
Start page 119
End page 141
Total pages 23
Editor D. M. Nicol
Place of publication New York, NY, U. S. A.
Publisher Association for Computing Machinery Inc.
Collection year 2002
Language eng
Subject C1
230202 Stochastic Analysis and Modelling
780101 Mathematical sciences
Abstract The two-node tandem Jackson network serves as a convenient reference model for the analysis and testing of different methodologies and techniques in rare event simulation. In this paper we consider a new approach to efficiently estimate the probability that the content of the second buffer exceeds some high level L before it becomes empty, starting from a given state. The approach is based on a Markov additive process representation of the buffer processes, leading to an exponential change of measure to be used in an importance sampling procedure. Unlike changes of measures proposed and studied in recent literature, the one derived here is a function of the content of the first buffer. We prove that when the first buffer is finite, this method yields asymptotically efficient simulation for any set of arrival and service rates. In fact, the relative error is bounded independent of the level L; a new result which is not established for any other known method. When the first buffer is infinite, we propose a natural extension of the exponential change of measure for the finite buffer case. In this case, the relative error is shown to be bounded (independent of L) only when the second server is the bottleneck; a result which is known to hold for some other methods derived through large deviations analysis. When the first server is the bottleneck, experimental results using our method seem to suggest that the relative error is bounded linearly in L.
Keyword Bounded relative error
Markov additive processes
importance sampling
orthogonal polynomials
rare event simulation
tandem Jackson network
Q-Index Code C1

Document type: Journal Article
Sub-type: Article (original research)
Collections: Excellence in Research Australia (ERA) - Collection
School of Physical Sciences Publications
 
Versions
Version Filter Type
Citation counts: Google Scholar Search Google Scholar
Created: Tue, 14 Aug 2007, 17:06:21 EST