Hostname: page-component-76fb5796d-zzh7m Total loading time: 0 Render date: 2024-04-26T00:17:01.377Z Has data issue: false hasContentIssue false
  • English
  • Français

HEAVY-TRAFFIC ANALYSIS OF A NON-PREEMPTIVE MULTI-CLASS QUEUE WITH RELATIVE PRIORITIES

Published online by Cambridge University Press:  20 January 2015

A. Izagirre ,
I.M. Verloop  and
U. Ayesta
A. Izagirre
Affiliation:
CNRS; IRIT; 2 rue C. Camichel, F-31071 Toulouse, France CNRS; LAAS; 7 avenue du colonel Roche, F-31400 Toulouse, France Université de Toulouse;INP, INSA; IRIT, LAAS; F-31400 Toulouse, France E-mail: ane.izagirre@laas.fr, urtzi@laas.fr, maaike.verloop@enseeiht.fr
I.M. Verloop
Affiliation:
CNRS; IRIT; 2 rue C. Camichel, F-31071 Toulouse, France Université de Toulouse;INP, INSA; IRIT, LAAS; F-31400 Toulouse, France E-mail: ane.izagirre@laas.fr, urtzi@laas.fr, maaike.verloop@enseeiht.fr
U. Ayesta
Affiliation:
CNRS; LAAS; 7 avenue du colonel Roche, F-31400 Toulouse, France IKERBASQUE, Basque Foundation for Science, 48011 Bilbao, Spain UPV/EHU, University of the Basque Country, 20018 Donostia, Spain Université de Toulouse;INP, INSA; IRIT, LAAS; F-31400 Toulouse, France E-mail: ane.izagirre@laas.fr, urtzi@laas.fr, maaike.verloop@enseeiht.fr
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We study the steady-state queue-length vector in a multi-class queue with relative priorities. Upon service completion, the probability that the next served customer is from class k is controlled by class-dependent weights. Once a customer has started service, it is served without interruption until completion. We establish a state-space collapse for the scaled queue-length vector in the heavy-traffic regime, that is, in the limit the scaled queue-length vector is distributed as the product of an exponentially distributed random variable and a deterministic vector. We observe that the scaled queue length reduces as classes with smaller mean service requirement obtain relatively larger weights. We finally show that the scaled waiting time of a class-k customer is distributed as the product of two exponentially distributed random variables.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 29 , Issue 2 , April 2015 , pp. 153 - 180
Copyright
Copyright © Cambridge University Press 2015 

References

1.Asmussen, S. (2003). Applied probability and queues. New York: Springer.Google Scholar
2.Ayesta, U., Izagirre, A. & Verloop, I.M. (2011). Heavy-traffic analysis of the discriminatory random-order-of-service discipline. Performance Evaluation Review, 32(2): 41–43.Google Scholar
3.Banerjea, A. & Keshav, S. (1993). Queueing delays in rate controlled ATM networks. In Proceedings of INFOCOM 1993, vol. 2, pp. 547–556.Google Scholar
4.Billingsley, P. (1999). Convergence of Probability Measures. New York: Wiley.Google Scholar
5.Borst, S.C., Boxma, O.J., Morrison, J.A. & Núñez-Queija, R. (2003). The equivalence between processor sharing and service in random order. Operations Research Letters 31: 254–262.Google Scholar
6.Boxma, O.J., Denteneer, D. & Resing, J.A.C. (2002). Some models for contention resolution in cable networks. Lecture Notes on Computer Science 2345: 117–128.CrossRefGoogle Scholar
7.Boxma, O.J., Foss, S.G., Lasgouttes, J.-M. & Núñez-Queija, R. (2004). Waiting time asymptotics in the single server queue with service in random order. Queueing Systems 46: 35–73.Google Scholar
8.Bramson, M. & Dai, J.G. (2001). Heavy traffic limits for some queueing networks. Annals of Applied Probability 11: 49–90.Google Scholar
9.Feller, W. (1971). An Introduction to Probability Theory and Its Applications, Vol. II, New York: Wiley.Google Scholar
10.Gelenbe, E. & Mitrani, I. (2010). Analysis and Synthesis of Computer Systems. London: Imperial College Press.Google Scholar
11.Haviv, M. & van der Wal, J. (1997). Equilibrium strategies for processor sharing and random queues with relative priorities. Probability in the Engineering and Informational Sciences 11: 403–412.Google Scholar
12.Haviv, M. & van der Wal, J. (2007). Waiting times in queues with relative priorities. Operations Research Letters 35: 591–594.CrossRefGoogle Scholar
13.Kim, J. (2009). Queue length distribution in a queue with relative priorities. Bulletin of Korean Mathematical Society 46: 107–116.Google Scholar
14.Kim, J., Kim, J. & Kim, B. (2011). Analysis of the M/G/1 queue with discriminatory random order service policy. Performance Evaluation 68(3): 256–270.CrossRefGoogle Scholar
15.Kingman, J.F.C. (1961). The single server queue in heavy traffic. Proceedings of the Cambridge Philosophical Society 57: 902–904.Google Scholar
16.Kingman, J.F.C. (1962). On queues in which customers are served in random order. Proceedings of the Cambridge Philosophical Society 58: 79–91.Google Scholar
17.Kingman, J.F.C. (1982). Queue disciplines in heavy traffic. Mathematics of Operations Research 7(2): 262–271.Google Scholar
18.Mather, W.H., Cookson, N.A., Hasty, J., Tsimring, L.S. & Williams, R.J. (2010). Correlation resonance generated by coupled enzymatic processing. Biophysical Journal 99: 3172–3181.CrossRefGoogle ScholarPubMed
19.Palm, C. (1957). Waiting times with random served queue. Tele1 (English edn., original 1938), 1–107.Google Scholar
20.Verloop, I.M., Ayesta, U. & Núñez-Queija, R. (2011). Heavy-traffic analysis of a multiple-phase network with discriminatory processor sharing. Operations Research 59: 648–660.Google Scholar
21.Zwart, A.P. (2005). Heavy-traffic asymptotics for the single-server queue with random order of service. Operations Research Letters 33: 511–518.Google Scholar