Analysis of a state-independent change of measure for the $G|G|1$ tandem queue

Research output: Contribution to conferencePaperAcademicpeer-review

26 Downloads (Pure)

Abstract

In 1989, Parekh and Walrand introduced a method to efficiently estimate the probability of a rare event in a single queue or network of queues. The event they consider is that the total number of customers in the system reaches some level $N$ in a busy cycle. Parekh and Walrand introduce a simple change of measure, which is state independent, in order to estimate this probability efficiently using simulation. However, they do not provide any proofs of some kind of efficiency of their method. For the single queue (with multiple servers) it has been shown by Sadowsky, in 1991, that the change of measure as proposed by Parekh and Walrand is asymptotically efficient under some mild conditions. In this work we study the state-independent change of measure of the $G_j|G_j|1$ tandem queue, along the lines of Parekh and Walrand, and we provide necessary conditions for asymptotic efficiency. To the best of our knowledge, no results on asymptotic efficiency for the $G_j|G_j|1$ tandem queue had been obtained previously. Looking at the results for the $M_j|M_j|1$ tandem queue, it is expected that this state-independent change of measure is the only state independent change of measure for the $G_j|G_j|1$ tandem queue that can possibly be asymptotically efficient. We show that, under some conditions, it is indeed the only exponential state-independent change of measure that can be asymptotically efficient. However, we have also identified conditions for the two node $G_j|G_j|1$ tandem queue under which the Parekh and Walrand change of measure is still not asymptotically efficient.
Original languageUndefined
Pages48-48
Number of pages1
Publication statusPublished - 18 Jul 2016

Keywords

  • EWI-27197
  • IR-103423

Cite this

@conference{d3b152df3e3b4d899d9de8d59e2cc1c4,
title = "Analysis of a state-independent change of measure for the $G|G|1$ tandem queue",
abstract = "In 1989, Parekh and Walrand introduced a method to efficiently estimate the probability of a rare event in a single queue or network of queues. The event they consider is that the total number of customers in the system reaches some level $N$ in a busy cycle. Parekh and Walrand introduce a simple change of measure, which is state independent, in order to estimate this probability efficiently using simulation. However, they do not provide any proofs of some kind of efficiency of their method. For the single queue (with multiple servers) it has been shown by Sadowsky, in 1991, that the change of measure as proposed by Parekh and Walrand is asymptotically efficient under some mild conditions. In this work we study the state-independent change of measure of the $G_j|G_j|1$ tandem queue, along the lines of Parekh and Walrand, and we provide necessary conditions for asymptotic efficiency. To the best of our knowledge, no results on asymptotic efficiency for the $G_j|G_j|1$ tandem queue had been obtained previously. Looking at the results for the $M_j|M_j|1$ tandem queue, it is expected that this state-independent change of measure is the only state independent change of measure for the $G_j|G_j|1$ tandem queue that can possibly be asymptotically efficient. We show that, under some conditions, it is indeed the only exponential state-independent change of measure that can be asymptotically efficient. However, we have also identified conditions for the two node $G_j|G_j|1$ tandem queue under which the Parekh and Walrand change of measure is still not asymptotically efficient.",
keywords = "EWI-27197, IR-103423",
author = "Anne Buijsrogge and {de Boer}, Pieter-Tjerk and Scheinhardt, {Willem R.W.}",
year = "2016",
month = "7",
day = "18",
language = "Undefined",
pages = "48--48",

}

Analysis of a state-independent change of measure for the $G|G|1$ tandem queue. / Buijsrogge, Anne; de Boer, Pieter-Tjerk; Scheinhardt, Willem R.W.

2016. 48-48.

Research output: Contribution to conferencePaperAcademicpeer-review

TY - CONF

T1 - Analysis of a state-independent change of measure for the $G|G|1$ tandem queue

AU - Buijsrogge, Anne

AU - de Boer, Pieter-Tjerk

AU - Scheinhardt, Willem R.W.

PY - 2016/7/18

Y1 - 2016/7/18

N2 - In 1989, Parekh and Walrand introduced a method to efficiently estimate the probability of a rare event in a single queue or network of queues. The event they consider is that the total number of customers in the system reaches some level $N$ in a busy cycle. Parekh and Walrand introduce a simple change of measure, which is state independent, in order to estimate this probability efficiently using simulation. However, they do not provide any proofs of some kind of efficiency of their method. For the single queue (with multiple servers) it has been shown by Sadowsky, in 1991, that the change of measure as proposed by Parekh and Walrand is asymptotically efficient under some mild conditions. In this work we study the state-independent change of measure of the $G_j|G_j|1$ tandem queue, along the lines of Parekh and Walrand, and we provide necessary conditions for asymptotic efficiency. To the best of our knowledge, no results on asymptotic efficiency for the $G_j|G_j|1$ tandem queue had been obtained previously. Looking at the results for the $M_j|M_j|1$ tandem queue, it is expected that this state-independent change of measure is the only state independent change of measure for the $G_j|G_j|1$ tandem queue that can possibly be asymptotically efficient. We show that, under some conditions, it is indeed the only exponential state-independent change of measure that can be asymptotically efficient. However, we have also identified conditions for the two node $G_j|G_j|1$ tandem queue under which the Parekh and Walrand change of measure is still not asymptotically efficient.

AB - In 1989, Parekh and Walrand introduced a method to efficiently estimate the probability of a rare event in a single queue or network of queues. The event they consider is that the total number of customers in the system reaches some level $N$ in a busy cycle. Parekh and Walrand introduce a simple change of measure, which is state independent, in order to estimate this probability efficiently using simulation. However, they do not provide any proofs of some kind of efficiency of their method. For the single queue (with multiple servers) it has been shown by Sadowsky, in 1991, that the change of measure as proposed by Parekh and Walrand is asymptotically efficient under some mild conditions. In this work we study the state-independent change of measure of the $G_j|G_j|1$ tandem queue, along the lines of Parekh and Walrand, and we provide necessary conditions for asymptotic efficiency. To the best of our knowledge, no results on asymptotic efficiency for the $G_j|G_j|1$ tandem queue had been obtained previously. Looking at the results for the $M_j|M_j|1$ tandem queue, it is expected that this state-independent change of measure is the only state independent change of measure for the $G_j|G_j|1$ tandem queue that can possibly be asymptotically efficient. We show that, under some conditions, it is indeed the only exponential state-independent change of measure that can be asymptotically efficient. However, we have also identified conditions for the two node $G_j|G_j|1$ tandem queue under which the Parekh and Walrand change of measure is still not asymptotically efficient.

KW - EWI-27197

KW - IR-103423

M3 - Paper

SP - 48

EP - 48

ER -