Queues serve as a major scheduling device in computer networks, both at the network level and at the application level. A fundamental and important property of a queue service discipline is its fairness. Recent empirical studies show fairness in queues to be highly important to queueing customers in practical scenarios. The objective of this tutorial is to discuss the issue of queue fairness and its dilemmas, and to review the research conducted on this subject. We discuss the fundamental principles related to queue fairness in the perspective of the relevant applications, with some emphasis on computer communications networks. This is conducted in the context of the recent research in this area and the queueing related fairness measures which have been proposed in recent years. We describe, discuss and compare their properties, and evaluate their relevance to the various practical applications.
Queues serve as a major building block in computer networks and are used to schedule and prioritize tasks both at the network level and at the application level. With the advances of the Internet more and more services move from the “physical world” into the “network controlled” world and require the use of computer and communications controlled queues. Examples include file servers used for the download of music, video, games and other applications, and call-centers.
Why do we use queues in these applications as well as in other real life applications, such as banks, supermarkets, airports, computer systems, Web services and numerous other systems? What purpose do ordered-queues serve? Perhaps the major reason for using a queue at all is to provide fair service to the customers. Furthermore, experimental psychology studies show that fair scheduling in queueing systems is indeed highly important to humans. Nonetheless, Queueing Theory, the theory that deals with analyzing queues and their efficient operation, has hardly dealt with the questions of what is a fair queue and how fair is a queueing policy.
The fairness factor associated to waiting in queues has been recognized in many works and applications. Larson (1988) in his discussion paper on the disutility of waiting, recognizes the central role played by 'Social Justice', (which is another name for fairness), and its perception by customers. This is also addressed in Rothkopf and Rech (1987) in their paper discussing perceptions in queues. Aspects of fairness in queues were discussed earlier by quite a number of authors: Palm (1953) deals with judging the annoyance caused by congestion, Mann (1969) discusses the queue as a social system and Whitt (1984) addresses overtaking in queues, to mention just three.
Empirical evidence of the importance of fairness of queues was recently provided in Rafaeli et. al. (2002),(2003) who studied, using an experimental psychology approach, the reaction of humans to waiting in queues and to various queueing and scheduling policies. The studies revealed that for humans waiting in queues the issue of fairness is highly important, perhaps some times more important than the duration of the wait.
This tutorial aims at addressing the subject of queue fairness, discuss the issues and dilemmas related to it, present the fundamental underlying assumptions and tie them to the real-life applications. Since we deal with the introduction of a new measure for a quantity that is somewhat abstract and not very tangible, several questions should be brought up and discussed. What is the physical entity, or performance objective that should be dealt with? At what level of detail should the system be measured? What are the physical properties that affect the measure? How intuitive and appealing i s the measure? And, how does the measure relate to the relevant applications? These questions are discussed and examined in this tutorial in the context of a few fairness measures proposed recently in the literature. We find it constructive to present many of the examples used in this tutorial in the context of “physical queues” (such as a supermarket queue).