Abstract
Fairness is a major issue in the operation of queues, perhaps it is the reason why queues were formed in the first place. Recent studies show that the fairness of a queueing system is important to customers not less than the actual delay they experience. Despite this observation little research has been conducted to study fairness in queues, and no commonly agreed upon measure of queue fairness exists. Two recent research exceptions are Avi-Itzhak and Levy [1], where a fairness measure is proposed, and Wierman and Harchol-Balter [18] (this conference, 2003), where a criterion is proposed for classifying service policies as fair or unfair; the criterion focuses on customer service requirement and deals with fairness with respect to service times.In this work we recognize that the inherent behavior of a queueing system is governed by two major factors: Job seniority (arrival times) and job service requirement (service time). Thus, it is desired that a queueing fairness measure would account for both. To this end we propose a Resource Allocation Queueing Fairness Measure, (RAQFM), that accounts for both relative job seniority and relative service time. The measure allows accounting for individual job discrimination as well as system unfairness. The system measure forms a full scale that can be used to evaluate the level of unfairness under various queueing disciplines. We present several basic properties of the measure. We derive the individual measure as well as the system measure for an M/M/1 queue under five fundamental service policies: Processor Sharing (PS), First Come First Served (FCFS), Non-Preemptive Last Come First Served (NP-LCFS), Preemptive Last Come First Served (P-LCFS), and Random Order of Service (ROS). The results of RAQFM are then compared to those of Wierman and Harchol-Balter [18], and the quite intriguing observed differences are discussed.
- B. Avi-Itzhak and H. Levy. On measuring fairness in queues. Advances of Applied Probability, to appear, 2004.Google Scholar
- E. G. Coffman, Jr., R. R. Muntz, and H. Trotter. Waiting time distribution for processor-sharing systems. J. ACM, 17:123--130, 1970. Google ScholarDigital Library
- A. Demers, S. Keshav, and S. Shenker. Analysis and simulation of a fair queueing algorithm. Internetworking Research and Experience, 1:3--26, 1990.Google Scholar
- A. G. Greenberg and N. Madras. How fair is fair queueing? Journal of the ACM, 3(39):568--598, 1992. Google ScholarDigital Library
- M. Harchol-Balter, B. Schroeder, N. Bansal, and M. Agrawal. Size-based scheduling to improve web performance. ACM Transactions on Computer Systems, 21(2):207--233, May 2003. Google ScholarDigital Library
- L. Kleinrock. Analysis of a time-shared processor. Nav. Res. Log. Quarterly, 11:59--73, 1964.Google ScholarCross Ref
- L. Kleinrock. Time-shared systems: A theoretical treatment. J. ACM, 14:242--261, 1967. Google ScholarDigital Library
- R. C. Larson. Perspective on queues: Social justice and the psychology of queueing. Operations Research, 35:895--905, Nov-Dec 1987.Google ScholarDigital Library
- I. Mann. Queue culture: The waiting line as a social system. Am. J. Sociol., 75:340--354, 1969.Google ScholarCross Ref
- C. Palm. Methods of judging the annoyance caused by congestion. Tele. (English Ed.), 2:1--20, 1953.Google Scholar
- A. Parekh and R. G. Gallager. A generalized processor sharing approach to flow control in integrated services networks: The single node case. IEEE/ACM Trans. Networking, 1:344--357, June 1993. Google ScholarDigital Library
- A. Parekh and R. G. Gallager. A generalized processor sharing approach to flow control in integrated services networks: The multiple node case. IEEE/ACM Trans. Networking, 2:137--150, 1994. Google ScholarDigital Library
- A. Rafaeli, G. Barron, and K. Haber. The effects of queue structure on attitudes. Journal of Service Research, 5(2):125--139, 2002.Google ScholarCross Ref
- A. Rafaeli, E. Kedmi, D. Vashdi, and G. Barron. Queues and fairness: A multiple study investigation. Faculty of Industrial Engineering and Management, Technion. Haifa, Israel. Under review, 2003.Google Scholar
- D. Raz, B. Avi-Itzhak, and H. Levy. Classes, priorities and fairness in queueing systems. Forthcoming, 2004.Google Scholar
- Y. T. Wang and R. J. T. Morris. Load sharing in distributed systems. IEEE Trans. on computers, C-34(3):204--217, 1985.Google ScholarDigital Library
- W. Whitt. The amount of overtaking in a network of queues. Networks, 14(3):411--426, 1984.Google ScholarCross Ref
- A. Wierman and M. Harchol-Balter. Classifying scheduling policies with respect to unfairness in an M/GI/1. In Proceedings of ACM Sigmetrics 2003 Conference on Measurement and Modeling of Computer Systems, San Diego, CA, June 2003. Google ScholarDigital Library
Index Terms
- A resource-allocation queueing fairness measure
Recommendations
A resource-allocation queueing fairness measure
SIGMETRICS '04/Performance '04: Proceedings of the joint international conference on Measurement and modeling of computer systemsFairness is a major issue in the operation of queues, perhaps it is the reason why queues were formed in the first place. Recent studies show that the fairness of a queueing system is important to customers not less than the actual delay they ...
Fairness considerations of scheduling in multi-server and multi-queue systems
valuetools '06: Proceedings of the 1st international conference on Performance evaluation methodolgies and toolsMulti-server and multi-queue architectures are common mechanisms used in a large variety of applications (call centers, Web services, computer systems). One of the major motivations behind common queue operation strategies is to grant fair service to ...
Fair operation of multi-server and multi-queue systems
Performance evaluation reviewThis work aims at studying the fairness of multi-queue and multi-server queueing systems. We deal with the issues of queue-multiplicity, queue joining policy and queue jockeying and use a quantitative measure (RAQFM) to evaluate them. Our results yield ...
Comments