Tuesday, August 30, 2011

A nice example of max-min fairness in networks

An example on max-min fairness taken from here:

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. 

Another example on weighted, max-min fairness:

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.