Re: [RPRWG] Darwin Fairness Algorithm

[Necdet Uzun <nuzun@xxxxxxxxx>]

Rauven,

In Darwin a mode bit is defined as below:

Bit mode; // Advertising mode: 1 conservative, 0 (default) aggressive

In mode 1, congested node (head node) estimates the fair rate and advertises it and upstream nodes have to follow these advertised rate.

In mode 0, since the upstream nodes periodically increment their allow_rate in every decay interval, the congested node can not add more than its fair rate (it can only add as much as left over bandwidth on the ring span). This add rate in turn is feedback to upstream nodes through fairness massages, hence upstream nodes scale back their allow_rate to the advertised rate periodically. Eventually it converges to the fair rate.

Please also see my in line comments.

Thanks.

Necdet
 
 
 
 

Reuven Zeitak wrote:

Dear All,

I am reading the darwin draft, section 12.

I seem to be missing something essential:

When a node is congested, it advertises a

weighted version of its add_rate, so that upstream

stations will "reduce" their rates.  My understanding is that

add_rate is the bandwidth the congested node adds to the ring.

I have two questions:

1) Under what circumstances does the node decrease its own rate ( making add_rate smaller for the next iteration)?

If there is not available bandwidth on the span below it. The upstream nodes periodically increment their allow_rate in every decay interval, the congested node can not add more than its fair rate (it can only add as much as left over bandwidth on the ring span)

 

2) Is it obvious that upstream nodes will really reduce their rates ( considering that they have various weights themselves)?

Here is an example of what I mean:

No reserved/ high priority BW in the system.

2 active nodes : rest of the ring--->A---> B---> rest of the ring

link capacity is 10 units of BW

 each node has equal weight (1)

Case 1

node A transmits 6 units, node B transmits 4 units.

B is congested,  and sends its normalised value 4 /1 to node A

which reduces to 4 giving a total of 8 units of rate ==> congestion removed.

In this case node A will  mostly generate null message as 4+6=10 which is equal to the link capacity. Hence, A will add 4 and B will add close to 6 in the long run.

 

This seems to operate correctly.

case 2

node A transmits 4 units, node B transmits 6 units.

B is congested,  and sends its normalised value 6/1  to node A

which *increases*  to 6 giving a total of 12 units of rate ==> congestion is increased.

In this case B will advertise 6, and A will ramp up slowly but not reach to 6 right away. Since A rumps up, B can not add 6 anymore, hence it has to advertise a smaller value than 6. Eventually it will converge at 5 each if both A and B has enough traffic to add.

 

case 3

node A has weight 2,node B has weight 1

node A transmits 6 units, node B transmits 4 units.

B is congested,  and sends its normalised value 4/1  to node A

which increases its rate  to 2*4/1 giving a total of 12 units of rate ==> congestion is increased.

In this case if A is adding 8 units, B can only add 2 units and advertised it in the next fairness message. After A receives a fair rate = 2, A can now add 2x2=4, then B now becomes uncongested and advertises null in the next fairness message. When A receives null message, it increments its own allow_rate (based on the formula in Annex J:

    allow_rate_congestion += (MAX_LRATE-reserved_rate- allow_rate_congestion)/(LP_ALLOW);)

This makes B congested at some point. Eventually, B adds 3.3 and A adds 6.6.

 

I am sure that I have misunderstood something here. Can someone please help?

It is all how allow_rate is updated. Since the algorithm is aggressive, congested node eventually gets its fair share as the upstream nodes are aggressively ramp-up until one of their downstream node gets congested and stops their rump-up.

 
 

Reuven Zeitak

begin:vcard 
n:Uzun;Necdet
tel;work:408 853 0461
x-mozilla-html:TRUE
url:www.cisco.com
version:2.1
email;internet:nuzun@xxxxxxxxx
adr;quoted-printable:;;Cisco Systems, Inc.=0D=0A170 W. Tasman Drive SJ-16-3=0D=0A;San Jose;CA;95134;
fn:Necdet Uzun
end:vcard