Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-12T19:42:12.205Z Has data issue: false hasContentIssue false
  • English
  • Français

On measuring fairness in queues

Part of: Computer system organization Special processes

Published online by Cambridge University Press:  01 July 2016

Benjamin Avi-Itzhak  and
Hanoch Levy
Benjamin Avi-Itzhak*
Affiliation:
Rutgers University
Hanoch Levy*
Affiliation:
Tel Aviv University
*
∗ Postal address: RUTCOR, Rutgers University, 640 Bartholomew Street, Piscataway, NJ 08554, USA. Email address: [email protected]
∗∗ Postal address: School of Computer Science, Tel Aviv University, Tel Aviv 69978, Israel. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The issue of ‘fairness’ is raised frequently in the context of evaluating queueing policies, notably in relation to telecommunications and computer systems where it may be of no lesser importance than the conventional measures of performance. Comparisons of the fairness of various systems and policies are often awkward due to lack of generally accepted definitions and measures for this important property. The purpose of this work is to propose possible fairness measures enabling us to quantitatively measure and compare the level of fairness associated with G/G/R queueing systems. We define and discuss order (of service) fairness and use an axiomatic approach for developing a measure for it in the G/D/1 case. The measure obtained for the G/D/1 system is then generalized and applied to the G/G/R class of systems. A practical implication of this work is that, for a wide class of service disciplines, the variance of the waiting time can be used as a yardstick for comparing fairness levels.

Keywords

Queueingfairnessservice orderqueue disciplinecustomer scheduling

MSC classification

Primary: 68M20: Performance evaluation; queueing; scheduling 60K25: Queueing theory
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 36 , Issue 3 , September 2004 , pp. 919 - 936
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

Bennet, J. C. R. and Zhang, H. (1996). WF2Q: worst case fair weighted fair queueing. In Proc. IEEE INFOCOM 1996 (San Francisco, CA, March 1996), pp. 120–128.Google Scholar
Cox, D. R. and Smith, W. L. (1961). Queues. John Wiley, New York.Google Scholar
Demers, A., Keshav, S. and Shenker, S. (1990). Analysis and simulation of a fair queueing algorithm. Internetworking Res. Experience 1, 3–26.Google Scholar
Golestani, S. J. (1994). A self-clocked fair queueing scheme for broadband applications. In Proc. IEEE INFOCOM 1994 (Toronto, Ontario, June 1994), pp. 636–646.CrossRefGoogle Scholar
Greenberg, A. G. and Madras, N. (1992). How fair is fair queueing? J. Assoc. Comput. Mach. 39, 568–598.CrossRefGoogle Scholar
Kelly, F. P. (1979). Reversibility and Stochastic Networks. John Wiley, New York.Google Scholar
Kingman, J. F. C. (1962). The effect of queue discipline on waiting time variance. Proc. Camb. Phil. Soc. 58, 163–164.CrossRefGoogle Scholar
Larson, R. C. (1987). Perspective on queues: social justice and the psychology of queueing. Operat. Res. 35, 895–905.CrossRefGoogle Scholar
Mann, I. (1969). Queue culture: the waiting line as a social system. Amer. J. Sociol. 75, 340–354.CrossRefGoogle Scholar
Palm, C. (1953). Methods of judging the annoyance caused by congestions. TELE 4, 189–208.Google Scholar
Parekh, A. (1992). A generalized processor sharing approach to flow control in integrated services networks. , MIT.Google Scholar
Parekh, A. 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
Parekh, A. and Gallager, R. G. (1994). A generalized processor sharing approach to flow control in integrated services networks: the multiple node case. IEEE/ACM Trans. Networking 2, 137–150.CrossRefGoogle Scholar
Rexford, J., Greenberg, A. and Bonomi, F. (1996). Hardware-efficient fair queueing architectures for high-speed networks. In Proc. IEEE INFOCOM 1996 (San Francisco, CA, March 1996) pp. 638–646.CrossRefGoogle Scholar
Rothkopf, M. H. and Rech, P. (1987). Perspectives on queues: combining queues is not always beneficial. Operat. Res. 35, 906–909.CrossRefGoogle Scholar
Wang, Y. T. and Morris, R. J. T. (1985). Load sharing in distributed systems. IEEE Trans. Comput. 34, 204–217.CrossRefGoogle Scholar
Whitt, W. (1984). The amount of overtaking in a network of queues. Networks 14, 411–426.CrossRefGoogle Scholar