Asymptotically optimal importance sampling for Jackson networks with a tree topology

DOI10.1007/S11134-009-9139-4zbMATH Open1182.90027arXiv0708.3260OpenAlexW2044799837MaRDI QIDQ2268463FDOQ2268463

Authors: Ali Devin Sezer 

Publication date: 8 March 2010

Published in: Queueing Systems (Search for Journal in Brave)

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 $$, $$.

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

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

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)

Cites Work

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

Cited In (10)

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

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)