- Remember from the Packet Switching article that:
- in a packet switch, only one packet traverses a link at instant “t”
- with statistical multiplexing, the link is used at its full capacity.
- When, at a node, the sum of incoming rates is greater or equal to the rate of the outgoing link, then network congestion will occur.
- Congestion is the normal state of the network. Congestion is inevitable. It’s an indication that the network is efficiently used. If there is no congestion then delay is low and the network is used inefficiently. If there is congestion, then queues are used heavily, and the network is used efficiently.
- We want to use the maximum capacity of the links to make the most advantage of the network.
- Congestion examples:
- two packets collide at a router interface and want to take the wire both at the same time
- two or more incoming flows at their maximum rates, over a prolonged period of time
- high usage of the link at peak hours (such as users browsing CNN.com in the morning)
- When there is congestion, packet drop occurs, which causes packet retransmissions which itself causes more congestion. So we need to have mechanisms to control congestion.
- In the TCP/IP model, congestion control occurs in the TCP protocol
- One of the goals of congestion control is to ensure a fair distribution of the bandwidth of a bottleneck link among competing flows.
The Max-Min fairness allocation
How should the allocation of the link be, if there are flows that want to share it? For that we use the Max-min Fairness allocation, which is one possible resource sharing policy.
The Max-min fairness principle works when multiple flows want to share a bottlenecked link. There is no meaning of applying this principle to links with a single flow.
Max-min Fairness allocation gives relative priority to lower rate flows.
Max-min fairness vs efficiency
A fair allocation is not necessarily an efficient allocation. In fact, this can be described on the Chiu Jain Plot. Having for example two competing flows A and B, if we draw flow A on the x-axis and flow B on the y-axis, then we can represent the fair allocation scheme with the function f(x)=x , i.e both flows have the same allocation. However, the efficiency allocation scheme is different. But there is one specific allocation point where it is both fair and efficient for flows A and B (represented by the green dot in the middle). The Max-min fairness allocation does not care about efficiency. It just cares about fairness. The job of AIMD for multiple flows is to approach the green dot and to make a balance between fairness and efficiency.
Max-min fairness definitions
There are many definitions of the Max-Min fairness allocation. Here are some of them:
Definition 1: “We have Max-min fairness when we can not increase the allocation of one flow without decreasing the allocation of another flow of a lower rate.”
Definition 2: “The Max-min fairness is an allocation where the flow with the lowest rate is maximized, then the flow with the second lowest rate is maximized, and so on.”
Definition 3: for this definition, we define a bottlenecked flow as a flow that is given less than its requested rate (for example a flow that needs 10Mbps but is given 8Mbps) . The third definition of Max-min fairness becomes “if a flow is bottlenecked, then it receives a rate that is at least equal to the fair-share rate of the requested resource”. The requested resource here is the capacity of the shared link.
the Max-min fairness principle suggests a scheme of bandwidth allocation (or capacity allocation) for each flow competing on the links. However, the allocation of flows is dynamic over time, i.e. if one or more flows join the network -or leave the network- the allocation changes: