Locality of reference and the use of sojourn time variance for measuring queue unfairness: extended abstract

ABSTRACT

The variance of customer sojourn time (or waiting time) is used, either explicitly or implicitly, as an indication of fairness for as long as queueing theory exists. In this work we demonstrate that this quantity has a disadvantage as a fairness measure, since it is not local to the busy period in which it is measured. It therefore may account for customer discrepancies which are not relevant to fairness of scheduling. We show that RAQFM, a recently proposed job fairness measure, does possess such a locality property. We further show that within a large class of fairness measures RAQFM is unique in possessing this property.

REFERENCES

• 1: B. Avi-Itzhak and H. Levy. On measuring fairness in queues. Advances in Applied Probability, 36(3):919--936, September 2004.
• 2: J. F. C. Kingman. The effect of queue discipline on waiting time variance. Proceedings of the Cambridge Philosophical Society, 58:163--164, 1962.
• 3: David Raz , Hanoch Levy , Benjamin Avi-Itzhak, A resource-allocation queueing fairness measure, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 4: Adam Wierman , Mor Harchol-Balter, Classifying scheduling policies with respect to higher moments of conditional response time, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Queueing theory

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Queueing theory; Modeling and prediction

General Terms:
Design, Performance, Theory