Max-min fairness

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.

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 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. 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 fewer "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".

Max-min fair link capacity pre-allocation

Max-min fairness in communication networks assumes that resources (capacities of communication links) are allocated to flows in advance, as opposed to best-effort networks.

Consider i data flows, sometimes called users or sources. Each data flow has a defined initial node, a destination node, and a desired data rate. A flow on its path through the network may be divided between "parallel" links, in a load balancing scheme.

An allocation vector x whose i-th coordinate is the allocation for flow i, i.e. the rate at which the user i is allowed to emit data.

An 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 the rate of the smaller (or minimum) flows that is made as large as possible (maximized) by the algorithm. Hence we give higher relative priority to small flows. Only when a flow asks to consume more than C/N (link capacity/number of flows) is it at any risk of having its bandwidth throttled by the algorithm.

Bottleneck links

A bottleneck link for a data flow i is a link that is fully utilized (is saturated) and of all the flows sharing this link, the data flow i achieves overall maximum data rate.^[1] Note that this definition is substantially different from a common meaning of a bottleneck. Also note, that this definition does not forbid a single bottleneck link to be shared between multiple flows.

A data rate allocation is max-min fair if and only if a data flow between any two nodes has at least one bottleneck link.

Progressive filling algorithm

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.

See also

• Fairness measures
• Scheduling in multitasking operational systems.

References

1. ^ http://ica1www.epfl.ch/PS_files/LEB3132.pdf#search=%22max-min%20fairness%22 Jean-Yves Le Boudec (EPFL Lausanne) "Rate adaptation, Congestion Control and Fairness: A Tutorial" Nov 2005

External links

• Max-min fair share algorithm