Max-min Fair Share Algorithm

14:332:423 Computer and Communication Networks

Max-min Fair Share Algorithm
(Adapted from: S.Keshav, An Engineering Approach to Computer Networking, Addison-Wesley, Reading, MA, 1997.
pages 215-217)

Note: A more complete introduction along with packet-by-packet Fair Queuing and WFQ is available in Chapter 5 of my Computer Networking book [downloadable PDF document].

We often run into the problem of dividing a scarce resource among a set of users, each of whom has an equal right to the resource, but some of whom intrinsically demand fewer resources than others. How, then, should we divide the resource? A sharing technique widely used in practice is called max-min fair share. Intuitively, a fair share allocates a user with a "small" demand what it wants, and evenly distributes unused resources to the "big" users. Formally, we define max-min fair share allocation to be as follows:

Resources are allocated in order of increasing demand
No source gets a resource share larger than its demand
Sources with unsatisfied demands get an equal share of the resource

This formal definition corresponds to the following operational definition. Consider a set of sources 1, ..., n that have resource demands x₁, x₂, ..., x_n. Without loss of generality, order the source demands so that x₁ <= x₂ <= ... <= x_n. Let the server have capacity C. Then, we initially give C/n of the resource to the source with the smallest demand, x₁. This may be more than what source 1 wants, perhaps, so we can continue the process. The process ends when each source gets no more than what it asks for, and, if its demand was not satisfied, no less than what any other source with a higher index got. We call such an allocation a max-min fair allocation, because it maximizes the minimum share of a source whose demand is not fully satisfied.

EXAMPLE 1

Compute the max-min fair allocation for a set of four sources with demands 2, 2.6, 4, 5 when the resource has a capacity of 10.

Solution: We compute the fair share in several rounds of computation. In the first round, we tentatively divide the resource into four portions of size 2.5. Since this is larger than source 1's demand, this leaves 0.5 left over for the remaining three sources, which we divide evenly among the rest, giving them 2.66... each. This is larger than what source 2 wants, so we have an excess of 0.066..., which we divide evenly among the remaining two sources, giving them 2.5 + 0.66... + 0.033... = 2.7 each. Thus, the fair allocation is: source 1 gets 2, source 2 gets 2.6, sources 3 and 4 get 2.7 each.

Thus far, we have assumed that all sources have the same right to the resources. Sometimes, we may want to give some sources a bigger share than others. In particular, we may want to associate weights w₁, w₂, ..., w_n with sources 1, 2, ..., n, which reflect their relative resource share. We extend the concept of max-min fair share to include such weights by defining the max-min weighted fair share allocation as follows:

Resources are allocated in order of increasing demand, normalized by the weight
No source gets a resource share larger than its demand
Sources with unsatisfied demands get rerource shares in proportion to their weights

The following example shows how to achieve this in practice.

EXAMPLE 2

Compute the max-min fair allocation for a set of four sources with demands 4, 2, 10, 4 and weights 2.5, 4, 0.5, 1 when the resource has a capacity of 16.

Solution:The first step is to normalize the weights so that the smallest weight is 1. This gives us the set of weights as 5, 8, 1, 2. We can now pretend that the number of sources, instead of being 4, is 5 + 8 + 1 + 2 = 16. We therefore divide the resource into 16 shares. In each round of resource allocation, we give a source a share proportional to its weight. Thus, in the first round, we compute C/n as 16/16 = 1. In this round, the sources receive 5, 8, 1, 2 units of the resource, respectively. Source 1 gets 5, and only needs 4, so we have 1 unit extra. Similarly, source 2 has 6 units extra. Sources 3 and 4 are backlogged, since their share is less than their demand. We now have 7 units of resources which have to be distributed to sources 3 and 4. Their weights are 1 and 2, and the smallest weight is 1, so there is no need to normalize weights. We give source 3 an additional 7 × 2/3 units (since its weight is 1), and source 4 an additional 7 × 2/3 units (since its weight is 2). This increases source 4's share to 2 + 7 × 2/3 = 6.666 units, which is more than it needs. So we give the excess 2.666 units to source 3, which finally gets 1 + 7/3 + 2.666 = 6 units. The final shares are, therefore, 4, 2, 6, 4. This is the max-min weighted fair share allocation.

Check also Max-min fairness @ Wikipedia

Ivan Marsic
Tue Nov 24 10:32:31 EST 1998