A measure of fairness of service for scheduling algorithms in multiuser systems

When considering issues of fairness of scheduling algorithms for packet data in networks, there is no well-defined quantitative value for the "fairness" of the system. Rather, fairness is usually expressed in broader terms. Generally, a system is deemed to be fair if it meets certain criteria on throughput or delay, and unfair if the criteria are not met. For example, a system in which some user receives a throughput less than Xbits/sec or experiences a delay τ with probability greater than p% may be deemed to be unfair. These definitions of fairness say if the system is or is not fair, but not how fair or unfair. This paper attempts to make a quantitative definition for a value of "fairness" that makes sense from both a mathematical and semantic standpoint. Such a value could be used to quickly compare the fairness of differing systems or algorithms. Definitions for the self-fairness and self-unfairness of the users of the system, and the average fairness and average unfairness of the overall system are proposed. The case is first considered when all users are weighted equally. That is, every user is considered to have the same importance, and hence each user should receive an equal proportion of the allocated resources for the system to be fair. The definitions are then extended to the case when the users have different weightings (for example, to achieve different levels of quality of service). The definitions take the viewpoint that the users themselves control what resources they are allocated. However, the definitions can just as easily be applied to the case when a central scheduling algorithm determines the allocation of resources to the users.