Hostname: page-component-78c5997874-lj6df Total loading time: 0 Render date: 2024-11-06T02:40:03.914Z Has data issue: false hasContentIssue false
  • English
  • Français

Analysis of generalized processor-sharing systems with two classes of customers and exponential services

Part of: Miscellaneous topics of analysis in the complex domain

Published online by Cambridge University Press:  14 July 2016

Fabrice Guillemin  and
Didier Pinchon
Fabrice Guillemin*
Affiliation:
France Télécom
Didier Pinchon*
Affiliation:
Université Paul Sabatier
*
∗ Postal address: France Télécom R&D, 2, Avenue Pierre Marzin, 22300 Lannion, France. Email address: [email protected]
∗∗ Postal address: Laboratoire MIP, Université Paul Sabatier, 118 Rue de Narbonne, 31062 Toulouse, France. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We derive in this paper 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).

Keywords

Weighted fair queueinggenerating functionPoisson equationasymptotic analysis

MSC classification

Secondary: 30E20: Integration, integrals of Cauchy type, integral representations of analytic functions
Type
Research Papers
Information
Journal of Applied Probability , Volume 41 , Issue 3 , September 2004 , pp. 832 - 858
Copyright
Copyright © Applied Probability Trust 2004 

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.)

References

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. Google Scholar
Bertsimas, D., Paschalidis, I., and Tsitsiklis, J. (1999). Large deviations analysis of the generalized processor sharing policy. Queueing Systems 32, 319–349.10.1023/A:1019151423773Google Scholar
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.Google Scholar
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.10.1007/BF01194397Google Scholar
Cohen, J. W. (1982). The Single Server Queue. North-Holland, Amsterdam.Google Scholar
Cohen, J. W., and Boxma, O. J. (1984). Boundary Value Problems in Queueing System Analysis. North-Holland, Amsterdam.Google Scholar
Dautray, R., and Lions, J.-L. (1985). Analyse Mathématique et Calcul Numérique pour les Sciences et les Techniques. Masson, Paris.Google Scholar
Davis, P. J., and Rabinowitz, P. (1984). Methods of Numerical Integration, 2nd edn. Academic Press, Orlando, FL.Google Scholar
Dieudonne, J. (1980). Calcul Infinitésimal. Hermann, Paris.Google Scholar
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.10.1017/S0305004100073709Google Scholar
Dupuis, P., and Ramanan, K. (1998). A Skorokhod problem formulation and large deviation analysis of a processor sharing model. Queueing Systems 28, 109–124.10.1023/A:1019186720196Google Scholar
Erdélyi, A., Magnus, W., Oberhettinger, F., and Tricomi, F. G. (1953). Higher Transcendental Functions, Vol. 2. McGraw-Hill, New York.Google Scholar
Fayolle, G., and Iasnogorodski, R. (1979). Two coupled processors: the reduction to a Riemann–Hilbert problem. Z. Wahrscheinlichkeitsth. 47, 325–351.10.1007/BF00535168Google Scholar
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.Google Scholar
Fayolle, G., King, P. J. B., and Mitrani, I. (1982). The solution of certain two-dimensional Markov models. Adv. Appl. Prob. 14, 295–308.10.2307/1426522Google Scholar
Graves-Morris, P. R., Roberts, D. E., and Salam, A. (2000). The epsilon algorithm and related topics. J. Comput. Appl. Math. 122, 51–80.10.1016/S0377-0427(00)00355-1Google Scholar
Henrici, P. (1977). Applied and Computational Complex Analysis, Vol. 2. John Wiley, New York.Google Scholar
Massoulié, L. (1999). Large deviations estimates for polling and weighted fair queueing service systems. Adv. Performance Anal. 2, 103–128.Google Scholar
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.Google Scholar
Rudin, W. (1965). Real and Complex Analysis. McGraw-Hill, New York.Google Scholar
Zhang, Z.-L. (1997). Large deviations and the generalised processor sharing scheduling for a two-queue system. Queueing Systems 27, 229–264.10.1023/A:1019133208384Google Scholar
Zhang, Z.-L. (1998). Large deviations and the general processor sharing scheduling for a multiple-queue system. Queueing Systems 28, 349–376.10.1023/A:1019163509718Google Scholar