Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-14T14:35:30.528Z Has data issue: false hasContentIssue false
  • English
  • Français

A Unifying Conservation Law for Single-Server Queues

Part of:Special processesComputer system organizationOperations research and management science

Published online by Cambridge University Press:  14 July 2016

Urtzi Ayesta
Urtzi Ayesta*
Affiliation:
LAAS-CNRS
*
∗ Postal address: LAAS-CNRS, 7 Avenue Colonel Roche, Toulouse, 31077, France. Email address: urtzi@laas.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 develop a conservation law for a multi-class GI/GI/1 queue operating under a general work-conserving scheduling discipline. For single-class single-server queues, conservation laws have been obtained for both nonanticipating and anticipating disciplines with general service time distributions. For multi-class single-server queues, conservation laws have been obtained for (i) nonanticipating disciplines with exponential service time distributions and (ii) nonpreemptive nonanticipating disciplines with general service time distributions. The unifying conservation law we develop generalizes already existing conservation laws. In addition, it covers popular nonanticipating multi-class time-sharing disciplines such as discriminatory processor sharing (DPS) and generalized processor sharing (GPS) with general service time distributions. As an application, we show that the unifying conservation law can be used to compare the expected unconditional response time under two scheduling disciplines.

Keywords

Queueing theoryperformance evaluationscheduling

MSC classification

Secondary:60K25: Queueing theory68M20: Performance evaluation; queueing; scheduling90B36: Scheduling theory, stochastic

Information

Type
Research Papers
Information
Journal of Applied Probability , Volume 44 , Issue 4 , December 2007, pp. 1078 - 1087
Copyright
Copyright © Applied Probability Trust 2007 

References

[1] Avrachenkov, K. E., Ayesta, U., Brown, P. and Núñez-Queija, R. (2005). Discriminatory processor sharing revisited. In Proc. IEEE INFOCOM 2005, pp. 784–795.CrossRefGoogle Scholar
[2] Baccelli, F. and Brémaud, P. (2003). Elements of Queuing Theory. Palm Martingale Calculus and Stochastic Recurrences, 2nd edn. Springer, Berlin.Google Scholar
[3] Brumelle, S. L. (1971). On the relation between customer and time average in queues. J. Appl. Prob. 2, 508–520.CrossRefGoogle Scholar
[4] Coffman, E. G. Jr. and Mitrani, I. (1980). A characterization of waiting time performance realizable by single-server queues. Operat. Res. 28, 810–821.CrossRefGoogle Scholar
[5] Cohen, J. W. (1982). The Single Server Queue. North-Holland, Amsterdam.Google Scholar
[6] Dacre, M., Glazebrook, K. and Niño-Mora, J. (1996). The achievable region approach to the optimal control of stochastic systems. J. R. Statist. Soc. Ser. B 61, 747–791.CrossRefGoogle Scholar
[7] Fayolle, G., Mitrani, I. and Iasnogorodski, R. (1980). Sharing a processor among many Job classes. J. Assoc. Comput Mach. 27, 519–532.CrossRefGoogle Scholar
[8] Federgruen, A. and Groenevelt, H. (1988). Characterization and optimization of achievable performance in general queueing systems. Operat. Res. 36, 733–741.CrossRefGoogle Scholar
[9] Friedman, E. and Henderson, S. (2003). Fairness and efficiency in processor sharing protocols to minimize sojourn times. In Proc. ACM SIGMETRICS, pp. 229–337.Google Scholar
[10] Gelenbe, E. and Mitrani, I. (1980). Analysis and Synthesis of Computer Systems. Academic Press, London.Google Scholar
[11] Green, T. C., and Stidham, S. (2000). Sample-path conservation laws, with application to scheduling queues and fluid systems. Queueing Systems 36, 175–199.CrossRefGoogle Scholar
[12] Gut, A. (1988). Stopped Random Walks. Limit Theorems and Applications. Springer, New York.CrossRefGoogle Scholar
[13] Heyman, D. P., and Sobel, M. J. (1982). Stochastic Models in Operations Research, Vol. I, Stochastic Processes and Operating Characteristics. McGraw-Hill, New York.Google Scholar
[14] Kiefer, J. and Wolfowitz, J. (1955). On the theory of queues with many servers. Trans. Amer. Math. Soc 78, 1–18.CrossRefGoogle Scholar
[15] Kleinrock, L. (1967). Time-shared systems: a theoretical treatment. J. Assoc. Comput Mach. 14, 242–261.CrossRefGoogle Scholar
[16] Kleinrock, L. (1976). Queueing Systems, Vol. 2. John Wiley, New York.Google Scholar
[17] O'Donovan, T. M. (1974). Distribution of attained service and residual service in general queueing systems. Operat. Res. 22, 570–575.CrossRefGoogle Scholar
[18] Parekh, A. K. and Gallager, R. G. (1993). A generalized processor sharing approach to flow control in integrated services networks: the single-node case. IEEE/ACM Trans. Networking 1, 344–357.CrossRefGoogle Scholar
[19] Schrage, L. E. (1967). The queue M/G/1 with feedback to lower priority queues. Manag. Sci. 13, 466–471.CrossRefGoogle Scholar
[20] Schrage, L. E. (1970). An alternative proof of a conservation law for the queue G/G/1. Operat. Res. 18, 185–187.CrossRefGoogle Scholar
[21] Schrage, L. E. and Miller, L. W. (1966). The queue M/G/1 with the shortest remaining processing time discipline. Operat. Res. 14, 670–684.CrossRefGoogle Scholar
[22] Shanthikumar, J. and Yao, D. (1992). Multiclass queueing systems: polymatroidal structure and optimal scheduling control. Operat. Res. 40, 293–299.CrossRefGoogle Scholar
[23] Sigman, K. (1991). A note on a sample-path rate conservation law and its relationship with H=λ G. Adv. Appl. Prob. 23, 662–665.CrossRefGoogle Scholar
[24] Van Uitert, M. J. G. (2003). Generalized processor sharing queues. Doctoral Thesis, Eindhoven University of Technology.Google Scholar
[25] Wierman, A., Harchol-Balter, M. and Osogami, T. (2005). Nearly insensitive bounds on SMART scheduling. In Proc. ACM SIGMETRICS, pp. 205–216.CrossRefGoogle Scholar
[26] Wolff, R. W. (1989). Stochastic Modeling and the Theory of Queues. Prentice-Hall, Englewood Cliffs, NJ.Google Scholar