Research and Innovations

What is max-min fairness? It is a fairness scheme in which capacity is always allocated to the lowest rate flow(s) before allocating remaining capacity to the rest sharing an output link. But, what do we meant by lowest rate flow? Flow with the lowest rate? How do we determine that? Let’s consider a case in which ten flows show an output link and every flow has much information to send. Then it become obvious that a fair scheme is to assign each flow one tenth of the output bandwidth. This is a particular case of max-min fairness. On the other hand, suppose one of the flows has little information to send and chooses to transmit at one twentieth of the bandwidth. Then this flow is allocated its bandwidth required and the excess will be shared by the other nine more aggressive flows. In other words, the rest of the flows will receive one ninth of remaining bandwidth according to definitions of max-min fairness.

How do we compute the max-min fairness bandwidth of a flow if it passes through a few shared links?  Recall that max-min fairness implies that bandwidth is always allocated to the flow with lowest rate first. Therefore, the short-cut for computing bandwidth allocation is always to compute the flow(s) with lowest rate first. Suppose two flows share a link rate R1 before these two flows share another link of rate R2 with another 5 flows. The rate allocations at link 1 and link 2 independently are R1/2 and R2/7 respectively.  Which one is smaller? Allocate the smaller rate first.  If  R2/7 < R1/2, then all flows get R2/7 each. If R2/7 > R2/2, then allocate R/2 to the two flows first and capacity left at link 2 to the other 5 flows, that is, (R2 – R1)/5 each.  Have fun.

This entry was posted on Sunday, October 25th, 2009 at 10:38 pm and is filed under TCP. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.