Asymptotically optimal importance sampling for Jackson networks with a tree topology

DOI10.1007/S11134-009-9139-4MaRDI QIDQ2268463zbMATHOpenAlexFDO

Authors Ali Devin Sezer

Publication date 8 March 2010

Published in Queueing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0708.3260

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Large deviations (60F10) Queues and service in operations research (90B22) Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Dynamic programming in optimal control and differential games (49L20) Optimal stochastic control (93E20)

Abstract: Importance sampling (IS) is a variance reduction method for simulating rare events. A recent paper by Dupuis, Wang and Sezer (Ann. App. Probab. 17(4):1306- 1346, 2007) exploits connections between IS and stochastic games and optimal control problems to show how to design and analyze simple and efficient IS algorithms for various overflow events for tandem Jackson networks. The present paper uses the same approach to build asymptotically optimal IS schemes for stable open Jackson networks with a tree topology. Customers arrive at the single root of the tree. The rare overflow event we consider is the following: given that initially the network is empty, the system experiences a buffer overflow before returning to the empty state. Two types of buffer structures are considered: 1) A single system-wide buffer of size $n$ shared by all nodes, 2) each node $i$ has its own buffer of size $$, $$.

Recommendations

• Importance sampling for Jackson networks
• Performance evaluation of an importance sampling technique in a Jackson network
• State-dependent importance sampling for a Jackson tandem network
• Importance sampling for maxima on trees
• Importance sampling algorithms for Bayesian networks: principles and performance
• Theoretical analysis and practical insights on importance sampling in Bayesian networks
• Efficient importance sampling heuristics for the simulation of population overflow in Jackson networks
• Dynamic importance sampling in Bayesian networks based on probability trees
• Importance sampling-based estimation over AND/OR search spaces for graphical models

Cites work

• A fast cross-entropy method for estimating buffer overflows in queueing networks
• A quick simulation method for excessive backlogs in networks of queues
• Analysis of an importance sampling estimator for tandem queues
• Dynamic importance sampling for queueing networks
• Dynamic importance sampling for uniformly recurrent Markov chains
• Importance Sampling, Large Deviations, and Differential Games
• Importance sampling for Jackson networks
• Importance sampling in the Monte Carlo study of sequential tests
• Large deviations theory and efficient simulation of excessive backlogs in a GI/GI/m queue
• Subsolutions of an Isaacs Equation and Efficient Schemes for Importance Sampling

Cited in

(10)

• Excessive backlog probabilities of two parallel queues
• Approximation of bounds on mixed-level orthogonal arrays
• Approximation of the exit probability of a stable Markov modulated constrained random walk
• Approximation of excessive backlog probabilities of two tandem queues
• Optimal sampling of overflow paths in Jackson networks
• Importance sampling for maxima on trees
• Importance sampling for a Markov modulated queuing network
• Efficient simulation of buffer overflow probabilities in Jackson networks with feedback
• Recurrence times of buffer overflows in Jackson networks
• Importance sampling for Jackson networks

This page was built for publication: Asymptotically optimal importance sampling for Jackson networks with a tree topology

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2268463)