Ghent University Academic Bibliography

Advanced

The impact of queue capacities on asymptotics in priority queues

Thomas Demoor, Joris Walraevens UGent, Dieter Fiems UGent and Herwig Bruneel UGent (2011) Stochastic Modelling and Simulation, International conference, Abstracts. p.29-29
abstract
Asymptotics are a major domain of interest in stochastic modelling as low-probability events are hard to characterize through simulation. It is generally known that tail probabilities of low-priority system content in a two-class priority queue with infinite capacity for customers of both priority classes can be non-exponential, even if the inter-arrival time and service time distributions are exponentially decaying. In contrast, when the capacity for the high-priority customers is limited to N, tail probabilities of low-priority system content are exponentially decaying. The convergence of the finite case to the infinite case1 is an open issue; it is still largely unclear how the non-exponentiality of tails in the infinite case is achieved as limiting behaviour of exponential tails in the finite case. The two-class priority queue falls within the broader class of reflected random walks on the two-dimensional lattice in the quarter plane: the number of customers of each class amounts to the coordinates of the random walk along an axis. The infinite case concerns the entire quarter plane whereas the finite case is restricted to a semi-infinite strip in the quarter plane. Let us call the coordinate that differs between both cases the phase and the one that remains the same the level such that finite case thus has N + 1 phases. By limiting the maximum number of concurrent arrivals, we can construct a recurrence relation in the number of phases for the finite case. This not only results in an explicit expression for the generating function of the low-priority system content, also a crucial relation between the characteristic polynomial of this recurrence relation in the finite case and the kernel in the infinite case is identified. We unveil that, in the finite case, all roots of the kernel influence system behaviour but cancel out each others branch cuts, much like the Fibonacci numbers. Furthermore, taking the limit of the finite case leads to the well-known behaviour for an infinite number of phases as the root inside the complex unit circle dominates the other roots, introducing a branch cut potentially causing non-exponential tails.
Please use this url to cite or link to this publication:
author
organization
year
type
conference
publication status
published
subject
in
Stochastic Modelling and Simulation, International conference, Abstracts
pages
29 - 29
publisher
Allied Publishers
conference name
2011 International conference on Stochastic Modelling and Simulation (ICSMS 2011)
conference location
Chennai, India
conference start
2011-12-15
conference end
2011-12-17
ISBN
9788184247435
language
English
UGent publication?
yes
classification
C3
id
1993506
handle
http://hdl.handle.net/1854/LU-1993506
date created
2012-01-18 15:59:31
date last changed
2016-12-19 15:36:26
@inproceedings{1993506,
  abstract     = {Asymptotics are a major domain of interest in stochastic modelling as low-probability events are hard to characterize through simulation. It is generally known that tail probabilities of low-priority system content in a two-class priority queue with infinite capacity for customers of both priority classes can be non-exponential, even if the inter-arrival time and service time distributions are exponentially decaying. In contrast, when the capacity for the high-priority customers is limited to N, tail probabilities of low-priority system content are exponentially decaying. The convergence of the finite case to the infinite case1 is an open issue; it is still largely unclear how the non-exponentiality of tails in the infinite case is achieved as limiting behaviour of exponential tails in the finite case. The two-class priority queue falls within the broader class of reflected random walks on the two-dimensional lattice in the quarter plane: the number of customers of each class amounts to the coordinates of the random walk along an axis. The infinite case concerns the entire quarter plane whereas the finite case is restricted to a semi-infinite strip in the quarter plane. Let us call the coordinate that differs between both cases the phase and the one that remains the same the level such that finite case thus has N + 1 phases. By limiting the maximum number of concurrent arrivals, we can construct a recurrence relation in the number of phases for the finite case. This not only results in an explicit expression for the generating function of the low-priority system content, also a crucial relation between the characteristic polynomial of this recurrence relation in the finite case and the kernel in the infinite case is identified. We unveil that, in the finite case, all roots of the kernel influence system behaviour but cancel out each others branch cuts, much like the Fibonacci numbers. Furthermore, taking the limit of the finite case leads to the well-known behaviour for an infinite number of phases as the root inside the complex unit circle dominates the other roots, introducing a branch cut potentially causing non-exponential tails.},
  author       = {Demoor, Thomas and Walraevens, Joris and Fiems, Dieter and Bruneel, Herwig},
  booktitle    = {Stochastic Modelling and Simulation, International conference, Abstracts},
  isbn         = {9788184247435},
  language     = {eng},
  location     = {Chennai, India},
  pages        = {29--29},
  publisher    = {Allied Publishers},
  title        = {The impact of queue capacities on asymptotics in priority queues},
  year         = {2011},
}

Chicago
Demoor, Thomas, Joris Walraevens, Dieter Fiems, and Herwig Bruneel. 2011. “The Impact of Queue Capacities on Asymptotics in Priority Queues.” In Stochastic Modelling and Simulation, International Conference, Abstracts, 29–29. Allied Publishers.
APA
Demoor, Thomas, Walraevens, J., Fiems, D., & Bruneel, H. (2011). The impact of queue capacities on asymptotics in priority queues. Stochastic Modelling and Simulation, International conference, Abstracts (pp. 29–29). Presented at the 2011 International conference on Stochastic Modelling and Simulation (ICSMS 2011), Allied Publishers.
Vancouver
1.
Demoor T, Walraevens J, Fiems D, Bruneel H. The impact of queue capacities on asymptotics in priority queues. Stochastic Modelling and Simulation, International conference, Abstracts. Allied Publishers; 2011. p. 29–29.
MLA
Demoor, Thomas, Joris Walraevens, Dieter Fiems, et al. “The Impact of Queue Capacities on Asymptotics in Priority Queues.” Stochastic Modelling and Simulation, International Conference, Abstracts. Allied Publishers, 2011. 29–29. Print.