Dynamic importance sampling for queueing networks

DOI10.1214/105051607000000122zbMATH Open1144.60022arXiv0710.4389OpenAlexW3100817765MaRDI QIDQ2467605FDOQ2467605

Hui Wang, Paul Dupuis, Ali Devin Sezer

Publication date: 28 January 2008

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Abstract: Importance sampling is a technique that is commonly used to speed up Monte Carlo simulation of rare events. However, little is known regarding the design of efficient importance sampling algorithms in the context of queueing networks. The standard approach, which simulates the system using an a priori fixed change of measure suggested by large deviation analysis, has been shown to fail in even the simplest network setting (e.g., a two-node tandem network). Exploiting connections between importance sampling, differential games, and classical subsolutions of the corresponding Isaacs equation, we show how to design and analyze simple and efficient dynamic importance sampling schemes for general classes of networks. The models used to illustrate the approach include $d$-node tandem Jackson networks and a two-node network with feedback, and the rare events studied are those of large queueing backlogs, including total population overflow and the overflow of individual buffers.

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

Recommendations

• Importance sampling for Jackson networks
• Importance sampling for a Markov modulated queuing network
• State-dependent importance sampling for a Jackson tandem network
• Efficient importance sampling schemes for a feed-forward network
• Subsolutions of an Isaacs Equation and Efficient Schemes for Importance Sampling

zbMATH Keywords

asymptotic optimalityIsaacs equationsubsolutionsimportance sampling, tandem queueing networks

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Large deviations (60F10) Queueing theory (aspects of probability theory) (60K25) Applications of optimal control and differential games (49N90)

Cites Work

• Applied Probability and Queues
• Title not available (Why is that?)
• Conditioned limit theorems relating a random walk to its associate, with applications to risk reserve processes and the GI/G/1 queue
• Importance Sampling, Large Deviations, and Differential Games
• Fast simulation of rare events in queueing and reliability models
• A viscosity solution approach to the asymptotic analysis of queueing systems
• Neumann type boundary conditions for Hamilton-Jacobi equations
• Dynamic importance sampling for uniformly recurrent Markov chains
• Analysis of an importance sampling estimator for tandem queues
• Subsolutions of an Isaacs Equation and Efficient Schemes for Importance Sampling
• The interchangeability of ·/M/1 queues in series
• 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
• Analysis of state-independent importance-sampling measures for the two-node tandem queue
• Large deviations for Markov processes with discontinuous statistics. I: General upper bounds

Cited In (36)

• Importance Sampling for Weighted-Serve-the-Longest-Queue
• The Convergence Rate and Asymptotic Distribution of the Bootstrap Quantile Variance Estimator for Importance Sampling
• Performance evaluation of an importance sampling technique in a Jackson network
• An Automatic Adaptive Importance Sampling Algorithm for Molecular Dynamics in Reaction Coordinates
• Quantitative Differentiation: A General Formulation
• Approximation of the exit probability of a stable Markov modulated constrained random walk
• Importance Sampling, Large Deviations, and Differential Games
• Excessive backlog probabilities of two parallel queues
• Importance Sampling for Metastable and Multiscale Dynamical Systems
• Splitting algorithms for rare event simulation over long time intervals
• Importance sampling algorithms for first passage time probabilities in the infinite server queue
• Analysis of a Splitting Estimator for Rare Event Probabilities in Jackson Networks
• Alternative proof and interpretations for a recent state-dependent importance sampling scheme
• Importance sampling for Jackson networks
• On Efficiency of Multilevel Splitting
• Subsolutions of an Isaacs Equation and Efficient Schemes for Importance Sampling
• Large deviations and importance sampling for a tandem network with slow-down
• The cross-entropy method with patching for rare-event simulation of large Markov chains
• Efficient Rare-Event Simulation for Multiple Jump Events in Regularly Varying Random Walks and Compound Poisson Processes
• Importance sampling for a simple Markovian intensity model using subsolutions
• Approximation of bounds on mixed-level orthogonal arrays
• Approximation of excessive backlog probabilities of two tandem queues
• Asymptotically optimal importance sampling for Jackson networks with a tree topology
• ON STATE-INDEPENDENT IMPORTANCE SAMPLING FOR THE GI|GI|1 TANDEM QUEUE¹
• Importance sampling for non-Markovian tandem queues using subsolutions
• Efficient exponential tilting with applications
• Fluid heuristics, Lyapunov bounds and efficient importance sampling for a heavy-tailed \(G/G/1\) queue
• The design and analysis of a generalized RESTART/DPR algorithm for rare event simulation
• Splitting for rare event simulation: A large deviation approach to design and analysis
• State-dependent importance sampling for a slowdown tandem queue
• Instanton based importance sampling for rare events in stochastic PDEs
• Moderate deviations-based importance sampling for stochastic recursive equations
• Rare Event Simulation of Small Noise Diffusions
• Stochastic viscosity approximations of Hamilton–Jacobi equations and variance reduction
• Importance sampling for a Markov modulated queuing network
• Escaping from an attractor: Importance sampling and rest points. I.

This page was built for publication: Dynamic importance sampling for queueing networks

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