** 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

- 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

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

- 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

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

Tue Nov 24 10:32:31 EST 1998