Quiz 8 Question 7 max-min fair allocation

Quiz 8 Question 7 max-min fair allocation

by Weiran Wang -
Number of replies: 1

Hi,

I have one question regarding this quiz question. If water-filling is implemented in order (i.e., link1, link2 and link3), the answer shown below can be obtained. However, if water-filling is implemented in another order, e.g., link1, link3 and link2, x0 = 1, x1 = 1, x2 = 3 and x3 = 7 will be obtained. Is there an order requirement when we use the water-filling algorithm?

I am also wondering in the given answer, link 3 is not saturated. Doesn't the min-max fair allocation require the saturated link?

Thanks!

In reply to Weiran Wang

Re: Quiz 8 Question 7 max-min fair allocation

by Aamir Shakir -
Hey,
from what I understood x0 = 1, x1 = 1, x2 = 3 and x3 = 7 is not max-min fair. You can increase x2 while decreasing x3. And this does not contradict fairness because x3 is larger than x2.

If there exists a max-min allocation, it is unique. So if you do water filling, you give every flow the same rate, for example, 1. If one link is saturated, you freeze (do not change) the flow anymore. And then, you continue increasing the rate for every nonfrozen flow until all flows are frozen. So x0 and x1 are frozen after the first round. In the second round, you increase x2 and x3 to two and so on until you saturate a link, in this case, link2. And link3 stays unsaturated.

It's just my understanding. I hope it helps :)