Hostname: page-component-74656f9884-54qdv Total loading time: 0 Render date: 2026-11-10T06:18:35.677Z Has data issue: false hasContentIssue false
  • English
  • Français

The M/G/1 queue with two service speeds

Part of: Computer system organization Special processes

Published online by Cambridge University Press:  01 July 2016

O. J. Boxma  and
I. A. Kurkova
O. J. Boxma*
Affiliation:
Eindhoven University of Technology
I. A. Kurkova*
Affiliation:
EURANDOM
*
∗ Postal address: Department of Mathematics and Computer Science, Eindhoven University of Technology, PO Box 513, 5600 MB Eindhoven, The Netherlands.
∗∗ Current address: Laboratoire de Probabilités et Modèles Aléatoires, Université Paris IV, BC 188, 4, Place Jussieu, 75252 Paris Cedex 05, France. Email address: kurkova@ccr.jussieu.fr
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider an M/G/1 queue with the special feature that the speed of the server alternates between two constant values s L and s H > s L . The high-speed periods are exponentially distributed, and the low-speed periods have a general distribution. Our main results are: (i) for the case that the distribution of the low-speed periods has a rational Laplace–Stieltjes transform, we obtain the joint distribution of the buffer content and the state of the server speed; (ii) for the case that the distribution of the low-speed periods and/or the service request distribution is regularly varying at infinity, we obtain explicit asymptotics for the tail of the buffer content distribution. The two cases in which the offered traffic load is smaller or larger than the low service speed are shown to result in completely different asymptotics.

Keywords

M/G/1 queuevariable speedbuffer contentregular variation

MSC classification

Primary: 60K25: Queueing theory 68M20: Performance evaluation; queueing; scheduling

Information

Type
General Applied Probability
Information
Advances in Applied Probability , Volume 33 , Issue 2 , June 2001 , pp. 520 - 540
Copyright
Copyright © Applied Probability Trust 2001 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

References

[1] Asmussen, S. and Teugels, J. (1996). Convergence rates for M/G/1 queues and ruin problems with heavy tails. J. Appl. Prob. 33, 1181–1190.CrossRefGoogle Scholar
[2] Asmussen, S., Klüppelberg, C. and Sigman, K. (1999). Sampling at subexponential times with queueing applications. Stoch. Proc. Appl. 79, 265–286.Google Scholar
[3] Bingham, N. H., Goldie, C. M. and Teugels, J. L. (1989). Regular Variation. Cambridge University Press.Google Scholar
[4] Borst, S. C., Boxma, O. J. and Jelenković, P. R. (1999). Generalized processor sharing with long-tailed traffic sources. In Teletraffic Engineering in a Competitive World (Proc. 16th Int. Teletraffic Cong., Edinburgh), eds Key, P. and Smith, D. North-Holland, Amsterdam, pp. 345–354.Google Scholar
[5] Borst, S. C., Boxma, O. J. and Jelenković, P. R. (2000). Coupled processors with regularly varying service times. In Proc. INFOCOM 2000, Tel Aviv, Vol. 1. IEEE, Piscataway, NJ, pp. 157–164.Google Scholar
[6] Boxma, O. J. and Kurkova, I. A. (2000). The M/M/1 queue in a heavy-tailed random environment. Statist. Neerlandica 54, 221–236.Google Scholar
[7] Boxma, O. J., Deng, Q. and Zwart, A. P. (1999). Waiting-time asymptotics for the M/G/2 queue with heterogeneous servers. Tech. Rept COSOR 99-20, Eindhoven University of Technology.Google Scholar
[8] Cohen, J. W. (1973). Some results on regular variation for distributions in queueing and fluctuation theory. J. Appl. Prob. 10, 343–353.CrossRefGoogle Scholar
[9] Cohen, J. W. (1982). The Single Server Queue. North-Holland, Amsterdam.Google Scholar
[10] Cohen, J. W. and Boxma, O. J. (1983). Boundary Value Problems in Queueing System Analysis. North-Holland, Amsterdam.Google Scholar
[11] Davis, R. A. and Hsing, T. (1995). Point process and partial sum convergence for weakly dependent random variables with infinite variance. Ann. Prob. 23, 879–917.CrossRefGoogle Scholar
[12] De Meyer, A. and Teugels, J. L. (1980). On the asymptotic behaviour of the distributions of the busy period and service time in M/G/1. J. Appl. Prob. 17, 802–813.Google Scholar
[13] Dudin, A. (2001). Queue M/G/1 in a semi-Markovian random environment. Preprint, Laboratory of Applied Probabilistic Analysis, Belarus State University, Minsk.Google Scholar
[14] Dudin, A. and Markov, A. (1990). Calculation of the characteristics of the queue in the semi-Markovian cyclic RE. In Proc. 15th All-Union Workshop on Computer Networks, Part 2. Academy of Science of USSR, Moscow, pp. 241–246.Google Scholar
[15] Fayolle, G., Malyshev, V. A. and Menshikov, M. V. (1995). Constructive Theory of Markov Chains. Cambridge University Press.CrossRefGoogle Scholar
[16] Halfin, S. (1972). Steady-state distribution for the buffer content of an M/G/1 queue with varying service rate. SIAM J. Appl. Math. 23, 356–363.CrossRefGoogle Scholar
[17] Heyde, C. C. (1967). On large deviation problems for sums of independent random variables not attached to the normal law. Ann. Math. Statist. 38, 1575–1578.Google Scholar
[18] Heyman, D. P. and Lakshman, T. V. (1996). Source models for VBR broadcast-video traffic. IEEE/ACM Trans. Netw. 4, 40–48.Google Scholar
[19] Jelenković, P. R., Lazar, A. A. and Semret, N. (1997). The effect of multiple time scales and subexponentiality of MPEG video streams on queueing behaviour. IEEE J. Sel. Areas Commun. 15, 1052–1071.CrossRefGoogle Scholar
[20] Leland, W. E. et al. (1993). On the self-similar nature of Ethernet traffic. In Proc. SIGCOMM '93, Annual Tech. Conf. Association for Computing Machinery, New York, pp. 183–193. Available at http://www.acm.org/sigcomm/.Google Scholar
[21] Li, W., Shi, D. and Chao, X. (1997). Reliability analysis of M/G/1 queueing systems with server breakdowns and vacations. J. Appl. Prob. 34, 546–555.CrossRefGoogle Scholar
[22] Neuts, M. F. (1971). A queue subject to extraneous phase changes. Adv. Appl. Prob. 3, 78–119.Google Scholar
[23] Núñez-Queija, R. (2000). Sojourn times in a processor-sharing queue with service interruptions. Queueing Systems 34, 351–386.Google Scholar
[24] Park, K. and Willinger, W. (eds) (2000). Self-Similar Network Traffic and Performance Evaluation. John Wiley, New York.Google Scholar
[25] Regterschot, G. J. K. and de Smit, J. H. A. (1986). The queue M/G/1 with Markov modulated arrivals and service. Math. Operat. Res. 11, 465–483.CrossRefGoogle Scholar
[26] Takine, T. and Sengupta, B. (1997). A single server queue with service interruptions. Queueing Systems 26, 285–300.Google Scholar
[27] Yechiali, U. (1973). A queueing-type birth-and-death process defined on a continuous-time Markov chain. Operat. Res. 21, 604–609.CrossRefGoogle Scholar
[28] Yechiali, U. and Naor, P. (1971). Queueing problems with heterogeneous arrival and service. Operat. Res. 19, 722–734.Google Scholar