Max-min fairness

From Wikipedia, the free encyclopedia

In communication networks and multiplexing, a division of the bandwidth resources is said to be max-min fair when: firstly, the minimum data rate that a dataflow achieves is maximized; secondly, the second lowest data rate that a dataflow achieves is maximized, etc.

In best-effort statistical multiplexing, a first-come first-served (FCFS) scheduling policy is often used. The advantage with max-min fairness over FCFS is that it results in traffic shaping, meaning that an ill-behaved flow, consisting of large data packets or bursts of many packets, will only punish itself and not other flows. Network congestion is consequently to some extent avoided.

Fair Queuing is an example of a max-min fair packet scheduling algorithm for statistical multiplexing and best effort packet-switched networks, since it gives scheduling priority to users that have achieved lowest data rate since they became active. In case of equally sized data packets, Round-robin scheduling is max-min fair.

1 Comparison with other policies for resource sharing
2 Max-min fair resource pre-allocation
3 See also
4 External links
5 Biblio

[edit] Comparison with other policies for resource sharing

Generally, policies for sharing resources that are characterized by low level of fairness (see fairness measures) provide high average throughput (or system spectral efficiency), but low stability in the service quality, meaning that the achieved service quality is varying in time depending on the behavior of other users. If this instability is severe, it may result in unhappy users that will choose another more stable communication service.

Max-min fair resource sharing results in higher average throughput (or system spectral efficiency in wireless networks) and better utilization of the resources than a work-conserving equal sharing policy of the resources. In equal sharing, some dataflows may not be able to utilize their "fair share" of the resources. A policy for equal sharing would prevent a dataflow from obtaining more resources than any other flow, and from utilizing free resources in the network.

On the other hand, max-min fairness provides lower average throughput than maximum throughput resource management, where the least expensive flows are assigned all capacity they can use, and no capacity might remain for the most expensive flows may get no capacity. In a wireless network, an expensive user is typically a mobile station at far distance from the base station, exposed to high signal attenuation. However, a maximum throughput policy would result in "starvation" of expensive flows, and may result in less number of "happy customers".

A compromise between max-min fairness and maximum throughput scheduling is proportional fairness, where the resources are divided with the goal to achieve the same cost to each user, or to minimize the maximum cost per unit that a dataflow reaches. Expensive data flows achieves lower service quality than others in proportional fairness, but does not suffer from "starvation". Max-min fairness results in more stable service quality, and therefore perhaps "happier customers".

[edit] Max-min fair resource pre-allocation

The following text describes max-min fairness in communication networks where resources are allocated to flows in advance, as opposed to best-effort networks.

[edit] Formal Definition

Consider an allocation problem: i users, a vector x whose the ith coordinates is the allocation for user i, i.e. the rate to which the user i can emit data. A feasible allocation of rates x is “max-min fair” if and only if an increase of any rate within the domain of feasible allocations must be at the cost of a decrease of some already smaller rate. Depending on the problem, a max-min fair allocation may or may not exist. However, if it exists, it is unique. The name “max-min” comes from the idea that it is forbidden to decrease the share of sources that have small values, thus, in some sense, we give priority to flows with small values.

[edit] Max-min Fairness and Bottleneck Links

A bottleneck link for a source is a link which is limiting for a given allocation. A feasible allocation is max-min fair if and only if every source has a bottleneck.

[edit] Algorithm for a Max-Min Fair Allocation

If resources are allocated in advance in the network nodes, max-min fairness can be obtained by using an algorithm of progressive filling. You start with all rates equal to 0 and grow all rates together at the same pace, until one or several link capacity limits are hit. The rates for the sources that use these links are not increased any more, and you continue increasing the rates for other sources. All the sources that are stopped have a bottleneck link. This is because they use a saturated link, and all other sources using the saturated link are stopped at the same time, or were stopped before, thus have a smaller or equal rate. The algorithm continues until it is not possible to increase. Lastly, when the algorithm terminates, all sources have been stopped at some time and thus have a bottleneck link. This allocation is max-min fair.