zbMATH — the first resource for mathematics

Analysis of generalized processor-sharing systems with two classes of customers and exponential services. (English) Zbl 1065.60132
Summary: We derive closed formulae for the joint probability generating function of the number of customers in the two FIFO queues of a generalized processor-sharing (GPS) system with two classes of customers arriving according to Poisson processes and requiring exponential service times. In contrast to previous studies published on the GPS system, we show that it is possible to establish explicit expressions for the generating functions of the number of customers in each queue without calling for the formulation of a Riemann-Hilbert problem. We specifically prove that the problem of determining the unknown functions due to the reflecting conditions on the boundaries of the positive quarter plane can be reduced to a Poisson equation. The explicit formulae are then used to derive some characteristics of the GPS system (in particular the tails of the probability distributions of the numbers of customers in each queue).

60K25 Queueing theory (aspects of probability theory)
90B22 Queues and service in operations research
30E20 Integration, integrals of Cauchy type, integral representations of analytic functions in the complex plane
Full Text: DOI
[1] Abramowitz, M. and Stegun, I. (eds) (1972). Handbook of Mathematical Functions (National Bureau Standards Appl. Math. Ser. 55 ). National Bureau of Standards, Washington, D.C. · Zbl 0171.38503
[2] Bertsimas, D., Paschalidis, I. and Tsitsiklis, J. (1999). Large deviations analysis of the generalized processor sharing policy. Queueing Systems 32 , 319–349. · Zbl 0937.68011 · doi:10.1023/A:1019151423773
[3] Borst, S. C., Boxma, O. J. and Jelenkovic, P. R. (2000). Asymptotic behavior of generalized processor sharing with long-tailed traffic sources. In Proc. IEEE Infocom 2000 (Tel Aviv, March 2000), Vol. 2, pp. 912–921.
[4] Brandt, A. and Brandt, M. (1998). On the sojourn times for many-queue head-of-line processor-sharing systems with permanent customers. Math. Meth. Operat. Res. 47 , 181–220. · Zbl 0947.90022 · doi:10.1007/BF01194397
[5] Cohen, J. W. (1982). The Single Server Queue . North-Holland, Amsterdam. · Zbl 0481.60003
[6] Cohen, J. W. and Boxma, O. J. (1984). Boundary Value Problems in Queueing System Analysis . North-Holland, Amsterdam. · Zbl 0515.60092
[7] Dautray, R. and Lions, J.-L. (1985). Analyse Mathématique et Calcul Numérique pour les Sciences et les Techniques . Masson, Paris. · Zbl 0642.35001
[8] Davis, P. J. and Rabinowitz, P. (1984). Methods of Numerical Integration , 2nd edn. Academic Press, Orlando, FL. · Zbl 0537.65020
[9] Dieudonne, J. (1980). Calcul Infinitésimal . Hermann, Paris. · Zbl 0497.26004
[10] Duffield, N. G. and O’Connell, N. (1995). Large deviations and overflow probabilities for the general single server queue with applications. Math. Proc. Camb. Phil. Soc. 118 , 363–374. · Zbl 0840.60087 · doi:10.1017/S0305004100073709
[11] Dupuis, P. and Ramanan, K. (1998). A Skorokhod problem formulation and large deviation analysis of a processor sharing model. Queueing Systems 28 , 109–124. · Zbl 0909.90144 · doi:10.1023/A:1019186720196
[12] Erdélyi, A., Magnus, W., Oberhettinger, F. and Tricomi, F. G. (1953). Higher Transcendental Functions , Vol. 2. McGraw-Hill, New York. · Zbl 0052.29502
[13] Fayolle, G. and Iasnogorodski, R. (1979). Two coupled processors: the reduction to a Riemann–Hilbert problem. Z. Wahrscheinlichkeitsth. 47 , 325–351. · Zbl 0395.68032 · doi:10.1007/BF00535168
[14] Fayolle, G., Iasnogorodski, R. and Malyshev, V. (1999). Random Walks in the Quarter-Plane. Algebraic Methods, Boundary Value Problems and Applications (Appl. Math. 40 ). Springer, Berlin. · Zbl 0932.60002
[15] Fayolle, G., King, P. J. B. and Mitrani, I. (1982). The solution of certain two-dimensional Markov models. Adv. Appl. Prob. 14 , 295–308. · Zbl 0495.60087 · doi:10.2307/1426522
[16] Graves-Morris, P. R., Roberts, D. E. and Salam, A. (2000). The epsilon algorithm and related topics. J. Comput. Appl. Math. 122 , 51–80. · Zbl 0970.65004 · doi:10.1016/S0377-0427(00)00355-1
[17] Henrici, P. (1977). Applied and Computational Complex Analysis , Vol. 2. John Wiley, New York. · Zbl 0363.30001
[18] Massoulié, L. (1999). Large deviations estimates for polling and weighted fair queueing service systems. Adv. Performance Anal. 2 , 103–128.
[19] Roberts, J. and Massoulié, L. (1998). Bandwidth sharing and admission control for elastic traffic. In Proc. IEEE Infocom 1999 (New York, March 1999), Vol. 1, pp. 1395–1403.
[20] Rudin, W. (1965). Real and Complex Analysis . McGraw-Hill, New York. · Zbl 0147.11601
[21] Zhang, Z.-L. (1997). Large deviations and the generalised processor sharing scheduling for a two-queue system. Queueing Systems 27 , 229–264. · Zbl 0892.90087 · doi:10.1023/A:1019133208384
[22] Zhang, Z.-L. (1998). Large deviations and the general processor sharing scheduling for a multiple-queue system. Queueing Systems 28 , 349–376. · Zbl 0922.90070 · doi:10.1023/A:1019163509718
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.