Asymptotically optimal importance sampling for Jackson networks with a tree topology

Download

index.pdf

Date

2010-02-01

Author

Sezer, Ali Devin

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

215
views

0
downloads

This note describes an importance sampling (IS) algorithm to estimate buffer overflows of stable Jackson networks with a tree topology. Three new measures of service capacity and traffic in Jackson networks are introduced and the algorithm is defined in their terms. These measures are effective service rate, effective utilization and effective service-to-arrival ratio of a node. They depend on the nonempty/empty states of the queues of the network. For a node with a nonempty queue, the effective service rate equals the node's nominal service rate. For a node i with an empty queue, it is either a weighted sum of the effective service rates of the nodes receiving traffic directly from node i, or the nominal service rate, whichever smaller. The effective utilization is the ratio of arrival rate to the effective service rate and the effective service-to-arrival ratio is its reciprocal. The rare overflow event of interest 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 shared by all nodes, and (2) each node has its own fixed size buffer. The constructed IS algorithm is asymptotically optimal, i. e., the variance of the associated estimator decays exponentially in the buffer size at the maximum possible rate. This is proved using methods from (Dupuis et al. in Ann. Appl. Probab. 17(4): 1306-1346, 2007), which are based on a limit Hamilton-Jacobi-Bellman equation and its boundary conditions and their smooth subsolutions. Numerical examples involving networks with as many as eight nodes are provided.

Subject Keywords

Dynamic Importance Sampling, Rare Event Simulation, Queuing Networks, Jackson Networks, Overflow Probability, Large Deviations, Hamilton-Jacobi-Bellmann Equation, Optimal Control

URI

https://hdl.handle.net/11511/31273

Journal

QUEUEING SYSTEMS

DOI

https://doi.org/10.1007/s11134-009-9139-4

Collections

Graduate School of Applied Mathematics, Article

Suggestions

OpenMETU
Core

Importance sampling for a Markov modulated queuing network Sezer, Ali Devin (2009-02-01) Importance sampling (IS) is a variance reduction method for simulating rare events. A recent paper by Dupuis, Wang and Sezer [Paul Dupuis, Ali Devin Sezer, Hui Wang, Dynamic importance sampling for queueing networks, Annals of Applied Probability 17 (4) (2007) 1306-1346] 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 of tandem Jackson Networks. The present paper carries out a p...
Incomplete-Leaf Multilevel Fast Multipole Algorithm for Multiscale Penetrable Objects Formulated With Volume Integral Equations Takrimi, Manouchehr; Ergül, Özgür Salih; ERTÜRK, VAKUR BEHÇET (2017-09-01) Recently introduced incomplete-leaf (IL) tree structures for multilevel fast multipole algorithm (referred to as IL-MLFMA) is proposed for the analysis of multiscale inhomogeneous penetrable objects, in which there are multiple orders of magnitude differences among the mesh sizes. Considering a maximum Schaubert-Wilton-Glisson function population threshold per box, only overcrowded boxes are recursively divided into proper smaller boxes, leading to IL tree structures consisting of variable box sizes. Such a...
Hierarchical Parallelization of the Multilevel Fast Multipole Algorithm (MLFMA) Gurel, Levent; Ergül, Özgür Salih (2013-02-01) Due to its O(NlogN) complexity, the multilevel fast multipole algorithm (MLFMA) is one of the most prized algorithms of computational electromagnetics and certain other disciplines. Various implementations of this algorithm have been used for rigorous solutions of large-scale scattering, radiation, and miscellaneous other electromagnetics problems involving 3-D objects with arbitrary geometries. Parallelization of MLFMA is crucial for solving real-life problems discretized with hundreds of millions of unkno...
Nested Iterative Solutions of Electromagnetic Problems Using Approximate Forms of the Multilevel Fast Multipole Algorithm Onol, Can; Ucuncu, Arif; Karaosmanoglu, Bariscan; Ergül, Özgür Salih (2017-03-24) Nested iterative solutions using full and approximate forms of the multilevel fast multipole algorithm (MLFMA) are presented for efficient analysis of electromagnetic problems. The developed mechanism is based on preconditioning an iterative solution via another iterative solution, and this way, nesting multiple solutions as layers. The accuracy is systematically reduced from top to bottom by using the on-the-fly characteristics of MLFMA, as well as the iterative residual errors. As a demonstration, a three...
PARALLEL MULTILEVEL FAST MULTIPOLE ALGORITHM FOR COMPLEX PLASMONIC METAMATERIAL STRUCTURES Ergül, Özgür Salih (2013-11-09) A parallel implementation of the multilevel fast multipole algorithm (MLFMA) is developed for fast and accurate solutions of electromagnetics problems involving complex plasmonic metamaterial structures. Composite objects that consist of multiple penetrable regions, such as dielectric, lossy, and plasmonic parts, are formulated rigorously with surface integral equations and solved iteratively via MLFMA. Using the hierarchical strategy for the parallelization, the developed implementation is capable of simul...

Citation Formats

A. D. Sezer, “Asymptotically optimal importance sampling for Jackson networks with a tree topology,” QUEUEING SYSTEMS, pp. 103–117, 2010, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/31273.