Max-min fairness

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.

Contents

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

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


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Fairness measure — Fairness measures or metrics are used in network engineering to determine whether users or applications are receiving a fair share of system resources. There are several mathematical and conceptual definitions of fairness. NOTOC TCP… …   Wikipedia

  • Bottleneck — For other uses, see Bottleneck (disambiguation). A bottleneck is a phenomenon where the performance or capacity of an entire system is limited by a single or limited number of components or resources. The term bottleneck is taken from the assets… …   Wikipedia

  • Bottleneck (engineering) — In engineering, bottleneck is a phenomenon by which the performance or capacity of an entire system is severely limited by a single component. The component is sometimes called a bottleneck point. The term is metaphorically derived from the neck… …   Wikipedia

  • Network congestion — In data networking and queueing theory, network congestion occurs when a link or node is carrying so much data that its quality of service deteriorates. Typical effects include queueing delay, packet loss or the blocking of new connections. A… …   Wikipedia

  • Maximum throughput scheduling — is a procedure for scheduling data packets in a packet switched best effort communications network, typically a wireless network, in view to maximize the total throughput of the network, or the system spectral efficiency in a wireless network.… …   Wikipedia

  • Taxonomy of congestion control — refers to grouping congestion control algorithms according to their characteristics.Example classificationThe following is one possible classification according to the following properties: #The type and amount of feedback received from the… …   Wikipedia

  • Fair queuing — is a scheduling algorithm used in computer and telecommunications networks to allow multiple packet flows to fairly share the link capacity. The advantage over conventional first in first out (FIFO) queuing is that a high data rate flow,… …   Wikipedia

  • Weighted fair queuing — (WFQ) is a data packet scheduling technique allowing different scheduling priorities to statistically multiplexed data flows. WFQ is a generalization of fair queuing (FQ). Both in WFQ and FQ, each data flow has a separate FIFO queue. In FQ, with… …   Wikipedia

  • Round-robin scheduling — Round robin (RR) is one of the simplest scheduling algorithms for processes in an operating system, which assigns time slices to each process in equal portions and in order, handling all processes without priority. Round robin scheduling is both… …   Wikipedia

  • Network congestion avoidance — is a process used in computer networks to avoid congestion.The fundamental problem is that all network resources are limited, including router processing time and link throughput. Eg.: *today s (2006) Wireless LAN effective bandwidth throughput… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”