Advanced search
1 file | 616.03 KB

Tail behaviour of a finite-/infinite-capacity priority queue

Thomas Demoor (UGent) , Joris Walraevens (UGent) , Dieter Fiems (UGent) and Herwig Bruneel (UGent)
Author
Organization
Abstract
Priority queues have been studied extensively throughout the last few decades. One of the main performance measures of interest is the loss probability, caused by the evident finiteness of queues. From analytical point of view, finite-capacity queues are more complex to study than queues with infinite capacity. Therefore, the most common approach for studying the loss probability is to analyze the tail behaviour of the corresponding infinite-capacity system. From this behaviour, the loss probability of the finite-capacity system can be approximated. However, this approximation can be rather inaccurate. Consider a system with two priority classes where the low-priority queue has infinite capacity but the high-priority queue can only accommodate N packets. In the system where both queues have infinite capacity, the tail behaviour of the queue content of the low-priority class can be geometric or non-geometric, dependent on whether the dominant singularity of the respective generating function is a pole or a branch point. However, in the system with a finite high-priority queue the tail is always geometric, even when N is large. Investigating this discrepancy is the topic of our contribution. In the finite system, the low-priority queue content can be expressed by a matrix equation. These matrices contain (partial) generating functions. Finding the poles corresponds to solving a non-linear eigenvalue problem. However, finding all poles is infeasible for larger N. Therefore, a numerical method is used to obtain the poles in a certain region (around the dominant pole).

Downloads

  • (...).pdf
    • full text
    • |
    • UGent only
    • |
    • PDF
    • |
    • 616.03 KB

Citation

Please use this url to cite or link to this publication:

Chicago
Demoor, Thomas, Joris Walraevens, Dieter Fiems, and Herwig Bruneel. 2010. “Tail Behaviour of a Finite-/infinite-capacity Priority Queue.” In Queueing Theory, 3rd Madrid Conference, Booklet of Abstracts, 31–32.
APA
Demoor, Thomas, Walraevens, J., Fiems, D., & Bruneel, H. (2010). Tail behaviour of a finite-/infinite-capacity priority queue. Queueing Theory, 3rd Madrid conference, Booklet of abstracts (pp. 31–32). Presented at the 3rd Madrid conference on Queueing Theory (MCQT  ’10).
Vancouver
1.
Demoor T, Walraevens J, Fiems D, Bruneel H. Tail behaviour of a finite-/infinite-capacity priority queue. Queueing Theory, 3rd Madrid conference, Booklet of abstracts. 2010. p. 31–2.
MLA
Demoor, Thomas, Joris Walraevens, Dieter Fiems, et al. “Tail Behaviour of a Finite-/infinite-capacity Priority Queue.” Queueing Theory, 3rd Madrid Conference, Booklet of Abstracts. 2010. 31–32. Print.
@inproceedings{1255985,
  abstract     = {Priority queues have been studied extensively throughout the last few decades. One of the main performance measures of interest is the loss probability, caused by the evident finiteness of queues. From analytical point of view, finite-capacity queues are more complex to study than queues with infinite capacity. Therefore, the most common approach for studying the loss probability is to analyze the tail behaviour of the corresponding infinite-capacity system. From this behaviour, the loss probability of the finite-capacity system can be approximated. However, this approximation can be rather inaccurate.
Consider a system with two priority classes where the low-priority queue has infinite capacity but the high-priority queue can only accommodate N packets. In the system where both queues have infinite capacity, the tail
behaviour of the queue content of the low-priority class can be geometric or non-geometric, dependent on whether the dominant singularity of the respective generating function is a pole or a branch point. However, in the system with a finite high-priority queue the tail is always geometric,
even when N is large. Investigating this discrepancy is the topic of our contribution.
In the finite system, the low-priority queue content can be expressed by a matrix equation. These matrices contain (partial) generating functions. Finding the poles corresponds to solving a non-linear eigenvalue problem. However, finding all poles is infeasible for larger N. Therefore, a numerical method is used to obtain the poles in a certain region (around the dominant pole).},
  author       = {Demoor, Thomas and Walraevens, Joris and Fiems, Dieter and Bruneel, Herwig},
  booktitle    = {Queueing Theory, 3rd Madrid conference, Booklet of abstracts},
  language     = {eng},
  location     = {Toledo, Spain},
  pages        = {31--32},
  title        = {Tail behaviour of a finite-/infinite-capacity priority queue},
  year         = {2010},
}