“How Fair Is Your Queue?” – Notes on talk by Prof. Levy
Posted by David Mayer on January 7, 2007
The task of inventing a good fairness metric for queues is a tough and important one. Such a metric would aid the design of wide range of systems, policies and applications including web servers, P2P applications, call centers, and others. In 2006, though, there still is not one single, widely accepted criterion.
In December 2006, Prof. Hanoch Levy from Tel Aviv University, Israel, gave a gripping talk on the topic of fairness in queues. The talk took place at Imperial College, London. In this article, based on Prof. Levy’s talk, we would like to draw the attention of networking researchers and system designers to this useful and practical topic.
What is queue fairness?
Before exposing the centrepiece of Prof. Levy’s talk, we should make clear what “queue fairness” actually is. Most researchers will be familiar with “flow fairness”. Flow fairness attempts to make flows (streams of packets) fair to each other. As an example, take “flow rate fairness”, which makes flows fair to each other in terms of their rates, or a “cost fairness” which makes flows fair with regard to the cost they incur. By contrast, “queue fairness” asks: How fair is the service received by a job (or a customer) in one queue?
As an example, consider the following scenario. A large job arrives at a queue first and a very short job arrives at a queue a bit later. Is it more fair to serve the first job or the short job first? That obviously depends on the type of service, context, culture, but in any case it would be useful to have a metric quantifying the fairness of the policy.
Why bother with queue fairness at all?
- The question is in fact redundant because the very purpose of queues is fairness! Queues, as opposed to crowds, appeal to our notion of fairness. Therefore, fairness is inherent part of queues.
- People do care about fairness. A company can get sued if a customer loses money due to being treated unfairly.
- In order to design a policy, we need a metric to evaluate it. However, there is no widely accepted metric for queue fairness as of yet.
The problem is, there is no established fairness criteria for jobs in a queue and it is difficult to devise one.
Resource Fairness: Solving the Seniority vs. Size Dilemma
At the heart of the difficulty lies the dilemma between seniority and size. Seniority refers to the time a customer spent in the queue waiting. Size refers to the service requirement, which is proportional to the size of the job. Previous proposals based themselves on either seniority  or size , which results in limited applicability and non-intuitive outcomes. For example, a seniority-based criteria ranks FCFS (First-Come-First-Serve) policy as the most fair policy and LCFS (Last-Come-First-Serve) as the most unfair policy, while a size-based criteria gives results exactly opposite.
In Prof. Levy’s talk, it was argued that a fairness measure should account for both. To this end, authors Raz, Levy and Avi-Itzhak in  focus on the server resources and how they are allocated to the jobs. Specifically, the fairness measure is based on the belief that “at every epoch all jobs present in the system deserve an equal share of the server’s attention” . The accumulated deviations from the fair share over time define discrimination. And discrimination is then taken as the measure of unfairness.
Thanks to this definition, we can promptly obtain
- an individual measure of discrimination, defined as the expected discrimination experienced by a customer and conditioned on the number of customers the customer finds upon its arrival (This metric can take positive and negative values, corresponding to positive and negative discrimination, respectively), and
- a system measure of discrimination, defined as the variance of individual discrimination (Zero variance will signify a fair system as everyone is discriminated the same.)
Case analysis: Individual Discrimination in M/M/1 queue with FCFS policy
It is interesting to see how this measure quantifies different extreme situations in a M/M/1/K queue running a FCFS discipline.
Consider the following 4 cases:
|Case||Customer finds||Fairness Criteria outcome|
|a)||Long queue in a lightly loaded system||Negative discrimination|
|b)||Long queue in a heavily loaded system||Zero discrimination|
|c)||Short queue in a lightly loaded system||Zero discrimination|
|d)||Short queue in a heavily loaded system||Positive discrimination|
We see these results are in agreement with the feeling we would have in given situations. (Imagine queueing in a supermarket at busy/dead hour.)
What about system unfairness? It is shown that the proposed fairness metric consistently ranks unfairness of policies as follows (in a M/M/1/K queue):
|Processor Sharing||is always fairer than||FCFS,|
|FCFS||is always fairer than||Random Order of Service,|
|Random Order of Service||is always fairer than||LCFS.|
This orderliness is actually remarkable compared to single-metric based criteria.
The proposed fairness criterion is named “Resource Allocation Queuing Fairness Measure (RAQFM)”. That is because it is based on the amount of resources the queue grants to customers.
When to use which criteria?
Seniority-based fairness  should be used in cases when getting a job done is far more important than the waiting time. An example is queuing for a scarce service such as a limited number of bargain tickets. There being pushed away by 1 place makes all the difference to the customer.
Fairness based on service time  is suitable where resources consumed by the customers do not “run out” (e.g. a web server or a supermarket). An example is the Shortest Job First Policy.
Whenever there is a concern about both seniority and job size, resource-based fairness serves as a suitable measure.
Ideas for future work
Although the problem of queue fairness has been with us as long as queueing theory itself, the attention it has received from the research community has been quite modest. This leaves many interesting problems to explore. We list here a few:
- Suppose a system policy is designed that satisfies certain fair criteria including job size. How will this affect customers in their behaviour? Will they modify their job size and arrivals to improve their treatment?
- Would it be possible to say that simple policies such as FCFS have the advantage of offering less opportunities for customers to exploit the policy?
- Customers with larger jobs can generate more revenue and could be entitled to a priority treatment. How could revenue management be incorporated to the framework of queue fairness? (As heard in the after-presentation discussion.)
 Raz, D., Levy, H., Avi-Itzhak, B. “A Resource-Allocation Queueing Fairness Measure”. In ACM SIGMETRICS/Performance’04, June 2004.
 Avi-Itzhak, B., Levy, H. “On measuring fairness in queues”. Advances of Applied Probability, 36:3 (2004), pp. 919-936, 2004.
 Wierman, A.,Harchol-Balter, A. “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.
If I get permission from Prof. Levy, I’ll post here the PowerPoint presentation used for the talk.
This is the PowerPoint presentation Prof. Levy used for his lecture at Imperial College: