article

Geometric tail of queue length of low-priority customers in a nonpreemptive priority MAP/PH/1 queue

Authors:

Attahiru S. AlfaAuthors Info & Claims

Queueing Systems: Theory and Applications, Volume 69, Issue 1

Pages 45 - 76

https://doi.org/10.1007/s11134-011-9221-6

Published: 01 September 2011 Publication History

Abstract

We consider a MAP/PH/1 queue with two priority classes and nonpreemptive discipline, focusing on the asymptotic behavior of the tail probability of queue length of low-priority customers. A sufficient condition under which this tail probability decays asymptotically geometrically is derived. Numerical methods are presented to verify this sufficient condition and to compute the decay rate of the tail probability.

References

[1]

Abate, J., Whitt, W.: Asymptotics for M/G/1 low-priority waiting-time tail probabilities. Queueing Syst. 25, 173-233 (1997).

[2]

Berger, A.W., Whitt, W.: Effective bandwidths with priorities. IEEE/ACM Trans. Netw. 6, 447-460 (1998).

Digital Library

[3]

Berger, A.W., Whitt, W.: Extending the effective-bandwidth concept to networks with priority classes. IEEE Commun. Mag. 2-7 (1998).

[4]

Berman, A., Plemmons, R.J.: Nonnegative Matrices in the Mathematical Science. Academic Press, San Diego (1979).

[5]

Bertsimas, D., Paschalidis, I.C., Tsitsiklis, J.N.: Asymptotic buffer overflow probabilities in multiclass multiplexers: An optimal control approach. IEEE Trans. Autom. Control 43, 315-335 (1998).

[6]

Delas, S., Mazumdar, R.R., Rosenberg, C.P.: Tail asymptotics for HOL priority queues handling a large number of independent stationary sources. Queueing Syst. 40, 183-204 (2002).

[7]

Elwalid, A.I., Mitra, D.: Analysis, approximations and admission control of a multi-service multiplexing system with priorities. In: Proc. IEEE INFOCOM'95, Boston, MA, 2-6 April, pp. 463-472 (1995).

[8]

Falkenberg, E.: On the asymptotic behavior of the stationary distribution of Markov chains of M/G/1- type. Stoch. Models 10, 75-97 (1994).

[9]

Foley, R.D., McDonald, D.R.: Bridges and networks: exact asymptotics. Ann. Appl. Probab. 15, 542- 586 (2005).

[10]

Glynn, P.W., Whitt, W.: Logarithmic asymptotics for steady-state tail probability in a single-server queues. Appl. Probab. Adv. 31, 131-156 (1999).

[11]

Graham, A.: Kronecker Products and Matrix Calculus with Applications. Ellis Horwood, Chichester (1986).

[12]

Haque, L., Liu, L., Zhao, Y.Q.: Sufficient conditions for a geometric tail in a QBD process with countably many levels and phases. Stoch. Models 77-99 (2005).

[13]

Hashida, O., Takahashi, Y.: A discrete-time priority queue with switched batch Bernoulli process inputs and constant service times. In: Jensen, A., Iversen, V.B. (eds.) Teletraffic and Datatraffic in a Period of Change, pp. 521-526. North Holland, Amsterdam (1991).

[14]

Khamisy, A., Sidi, M.: Discrete-time priority queueing systems with two-state Markov modulated arrival process. In: INFOCOM 91, pp. 1456-1463 (1991).

[15]

Kingman, J.C.F.: A convexity property of positive matrices. Q. J. Math. 12, 283-284 (1961).

[16]

Latouche, G., Ramaswami, V.: Introduction to matrix analytic methods in stochastic modeling. In: ASA-SIAM. (1999).

[17]

Li, H., Miyazawa, M., Zhao, Y.Q.: Geometric decay in a QBD process with countable background states with applications to a join-the-shortest-queue model. Stoch. Models 413-438 (2007).

[18]

Lucantoni, D.M.: New results on the single server queue with a batch Markovian arrival process. Stoch. Models 7, 1-46 (1991).

[19]

Lucantoni, D.M., Meier-Hellstern, K.S., Neuts, M.F.: A single-server queue with server vacations and a class of non-renewal arrival process. Adv. Appl. Probab. 22, 676-705 (1990).

[20]

Miyazawa, M., Zhao, Y.Q.: The stationary tail asymptotics in the GI/G/1 type queue with countably many background states. Adv. Appl. Probab. 36, 1231-1251 (2004).

[21]

Neuts, M.F.: A versatile Markovian point process. J. Appl. Probab. 16, 764-779 (1979).

[22]

Neuts, M.F.: Matrix-Geometric Solutions in Stochastic Models. The Johns Hopkins University Press, Baltimore (1981).

[23]

Neuts, M.F.: Structured stochastic matrices of the M/G/1 type and their applications. Marcel Dekker, New York (1989).

[24]

Sidi, M., Segall, A.: Structured priority queueing systems with applications to packet-radio networks. Perform. Eval. 3, 265-275 (1983).

[25]

Subramanian, V., Srikant, R.: Tail probabilities of low-priority waiting times and queue lengths in MAP/GI/1 queue. Queueing Syst. 34, 215-236 (2000).

[26]

Takahashi, Y., Fujimoto, K., Makimoto, N.: Geometric decay of the steady-state probabilities in a Quasi-Birth-And Death process with a countable number of phases. Stoch. Models 17, 1-24 (2001).

[27]

Takine, T., Sengupta, B., Hasegawa, T.: An analysis of a discrete-time queue for broadband ISDN with priorities among traffic classes. IEEE Trans. Commun. 42, 1837-1845 (1994).

[28]

Takine, T.: A nonpreemptive priority MAP/G/1 queue with two classes of customers. J. Oper. Res. Soc. Jpn. 39, 266-290 (1996).

[29]

Takine, T.: The nonpreemptive priority MAP/G/1 queue. Oper. Res. 47, 917-927 (1999).

Digital Library

[30]

Tweedie, R.L.: Operator-geometric stationary distribution for Markov chains, with application to queueing models. Adv. Appl. Probab. 14, 392-433 (1982).

[31]

Xue, J., Alfa, A.S.: Tail probability of low-priority queue length in a discrete-time priority BMAP/PH/1 queue. Stoch. Models 21, 799-820 (2005).

Cited By

Ozawa T(2018)Asymptotics for the sojourn time distribution in the queue defined by a general QBD process with a countable phase spaceQueueing Systems: Theory and Applications10.1007/s11134-013-9359-576:1(73-103)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.1007/s11134-013-9359-5
Ozawa T(2018)Asymptotics for the stationary distribution in a discrete-time two-dimensional quasi-birth-and-death processQueueing Systems: Theory and Applications10.1007/s11134-012-9323-974:2-3(109-149)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.1007/s11134-012-9323-9

Recommendations

Waiting time distributions in the accumulating priority queue

We are interested in queues in which customers of different classes arrive to a service facility, and where performance targets are specified for each class. The manager of such a queue has the task of implementing a queueing discipline that results in ...
On priority queues with impatient customers

In this paper, we study three different problems where one class of customers is given priority over the other class. In the first problem, a single server receives two classes of customers with general service time requirements and follows a preemptive-...
A matrix-analytic solution for the DBMAP/PH/1 priority queue

Priority queueing models have been commonly used in telecommunication systems. The development of analytically tractable models to determine their performance is vitally important. The discrete time batch Markovian arrival process ( DBMAP ) has been ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Queueing Systems: Theory and Applications

Queueing Systems: Theory and Applications Volume 69, Issue 1

September 2011

100 pages

ISSN:0257-0130

Issue’s Table of Contents

Copyright © Copyright © 2011 Springer Science+Business Media, LLC.

Publisher

J. C. Baltzer AG, Science Publishers

United States

Publication History

Published: 01 September 2011

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ozawa T(2018)Asymptotics for the sojourn time distribution in the queue defined by a general QBD process with a countable phase spaceQueueing Systems: Theory and Applications10.1007/s11134-013-9359-576:1(73-103)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.1007/s11134-013-9359-5
Ozawa T(2018)Asymptotics for the stationary distribution in a discrete-time two-dimensional quasi-birth-and-death processQueueing Systems: Theory and Applications10.1007/s11134-012-9323-974:2-3(109-149)Online publication date: 29-Dec-2018
https://dl.acm.org/doi/10.1007/s11134-012-9323-9

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents