Subject: Re: [ledbat] max cwnd

From: Janardhan Iyengar <[email-masked]>
Date: Wed, 23 Feb 2011 10:23:19 -0500

All,

I hasten to add that there's only one piece that I've modified in the increase algorithm  (pointed out below).  The rest of it simply eliminates variables that MUST be 1.  I am not opposed to leaving those variables (in particular, GAIN) in, but I wanted to provide a simpler and cleaner counterpoint.

-------------
1.  Original increase algo (with Mirja's normalization of off_target):
On an ack:
     ...
     off_target = TARGET - queuing_delay
     cwnd += GAIN * off_target / TARGET / cwnd
     # flight_size() is the amount of currently not acked data.
     max_allowed_cwnd = ALLOWED_INCREASE + TETHER*flight_size()
     cwnd = min(cwnd, max_allowed_cwnd)

with
- GAIN MUST be 1,
- ALLOWED_INCREASE MUST be at least 1 packet and SHOULD NOT be more than 3 packets,
- TETHER SHOULD be 1.5.

The difficulty here is in tracking precisely how to utilize ALLOWED_INCREASE and TETHER to curb cwnd growth during data lulls, while ensuring that the growth must not be greater than standard TCP's.  Note that as specified, this algorithm allows for faster increase than slow start during data lulls---ALLOWED_INCREASE and TETHER ought to be 1 for slow start like behavior.

-------------
2.  My proposed simplification (changed off_target to cwnd_rate, eliminated GAIN, and replaced the cwnd curbing with an explicit if-else):
On an ack:
   ...
   cwnd_rate = (TARGET - queuing_delay) / TARGET
   if flight_size()>= cwnd:
       cwnd += cwnd_rate / cwnd
   else:
       cwnd = flight_size()

-------------
3.  If we want to retain GAIN and the other variables (someone needs to post justification here; I don't see much at this point):
On an ack:
   ...
   cwnd_rate = GAIN * (TARGET - queuing_delay) / TARGET
   if flight_size()>= cwnd:
       cwnd += cwnd_rate / cwnd
   else:
       cwnd = ALLOWED_INCREASE + TETHER*flight_size()

This form of the algo is (almost) the same as the form (1), with the minor difference that when there isn't a data lull, cwnd grows as we would expect (the body of the if clause).  Constants are:
- GAIN MUST be 1,
- ALLOWED_INCREASE MUST be at least 1 packet and SHOULD NOT be more than 3 packets
- TETHER SHOULD be 1.

------------

Thoughts?
- jana

On 2/23/11 9:48 AM, Janardhan Iyengar wrote:
>  Mirja,
>
>  (I agree with you on normalizing off_target with TARGET.  That part was fully broken in the original algorithm.)
>
>>  there is another line in the pseudo code:
>>
>>      max_allowed_cwnd = ALLOWED_INCREASE + TETHER*flight_size()
>>
>>  The current spec says:
>>  "ALLOWED_INCREASE SHOULD be 1 packet; it MUST be at least 1 packet and SHOULD
>>  NOT be more than 3 packets. TETHER SHOULD be 1.5; it MUST be greater than
>>  1. "
>
>  So, after thinking about ALLOWED_INCREASE, TETHER, and GAIN, I'm increasingly leaning towards eliminating all of these variables in favor of simplicity.
>
>>  This is the cwnd limitation when there are no enough data to fill the cwnd.
>>  As far as I can see the implementation in Linux would limit to
>>
>>      max_allowed_cwnd = 3 + 1*flight_size().
>  [...]
>
>  This use of cwnd comes from TCP's definition of cwnd which conflates the sender's cwnd size with the actual send_window itself. In other words, TCP conflates *what* is outstanding with *how much* is outstanding.  The cwnd ought to reflect *how much* and not *what*.
>   From RFC 5681,
>        CONGESTION WINDOW (cwnd): A TCP state variable that limits the amount
>        of data a TCP can send.  At any given time, a TCP MUST NOT send
>        data with a sequence number higher than the sum of the highest
>        acknowledged sequence number and the minimum of cwnd and rwnd.
>
>  TCP's cwnd is also its send_window.  When there's no loss, this is fine, but when there's loss, the left edge of the send window is stuck to the last acknowledged byte.  At the same time, duplicate acks received do not move the left edge of the send_window, but indicate to the sender that packets are leaving the wire.  To compensate for this discrepancy, the window is allowed to artificially inflate until a new ack allows the left edge of the send_window (and cwnd) to move.
>
>  I propose the following:
>
>  First, a clean definition of cwnd is in order:
>  cwnd:  A sender-side variable that limits the amount of data, regardless of sequence number, that the sender is allowed to have outstanding in the network.  Note that the cwnd variable used in this document reflects and controls the amount of data that a sender is allowed to have outstanding, and is different from TCP's definition of cwnd [RFC5681] in not controlling the actual data being transmitted.  This cwnd MAY be in bytes or packets; for ease of exposition, this document uses cwnd in packets.
>
>  Then the modified increase algorithm:
>  On an ack:
>    ...
>    cwnd_rate = (TARGET - queuing_delay) / TARGET
>    if flight_size()>= cwnd:
>        cwnd += cwnd_rate / cwnd
>    else:
>        cwnd = flight_size()
>
>  Thoughts?
>  - jana
>

---

From: Rolf Winter <[email-masked]>
Date: Thu, 24 Feb 2011 15:47:09 +0000

Hi,

speaking not as chair.

The current spec actually says that GAIN SHOULD be 1, which is wrong it should say MUST NOT be larger 1 in order to not ramp up faster than TCP. Having a GAIN smaller than one, I am not sure how useful that would be given the fact that we restrict LEDBAT to congestion avoidance and not slow start behaviour.

Speaking as chair: can we have more comments on this and come to a timely conclusion?

Best,

Rolf

NEC Europe Limited | Registered Office: NEC House, 1 Victoria Road, London W3 6BL | Registered in England 2832014 

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On
> Behalf Of Janardhan Iyengar
> Sent: Mittwoch, 23. Februar 2011 16:23
> To: Mirja Kuehlewind; [email-masked]
> Subject: Re: [ledbat] max cwnd
> 
> All,
> 
> I hasten to add that there's only one piece that I've modified in the
> increase algorithm  (pointed out below).  The rest of it simply
> eliminates variables that MUST be 1.  I am not opposed to leaving those
> variables (in particular, GAIN) in, but I wanted to provide a simpler
> and cleaner counterpoint.
> 
> -------------
> The difficulty here is in tracking precisely how to utilize
> ALLOWED_INCREASE and TETHER to curb cwnd growth during data lulls,
> while ensuring that the growth must not be greater than standard TCP's.
> Note that as specified, this algorithm allows for faster increase than
> slow start during data lulls---ALLOWED_INCREASE and TETHER ought to be
> 1 for slow start like behavior.
> 
> -------------
> 2.  My proposed simplification (changed off_target to cwnd_rate,
> eliminated GAIN, and replaced the cwnd curbing with an explicit if-
> else):
> On an ack:
>    ...
> 3.  If we want to retain GAIN and the other variables (someone needs to
> post justification here; I don't see much at this point):
> On an ack:
>    ...
> This form of the algo is (almost) the same as the form (1), with the
> minor difference that when there isn't a data lull, cwnd grows as we
> would expect (the body of the if clause).  Constants are:
> - GAIN MUST be 1,
> >  (I agree with you on normalizing off_target with TARGET.  That part
> was fully broken in the original algorithm.)
> >
> >  So, after thinking about ALLOWED_INCREASE, TETHER, and GAIN, I'm
> increasingly leaning towards eliminating all of these variables in
> favor of simplicity.
> >
> >  This use of cwnd comes from TCP's definition of cwnd which conflates
> the sender's cwnd size with the actual send_window itself. In other
> words, TCP conflates *what* is outstanding with *how much* is
> outstanding.  The cwnd ought to reflect *how much* and not *what*.
> >   From RFC 5681,
> >  TCP's cwnd is also its send_window.  When there's no loss, this is
> fine, but when there's loss, the left edge of the send window is stuck
> to the last acknowledged byte.  At the same time, duplicate acks
> received do not move the left edge of the send_window, but indicate to
> the sender that packets are leaving the wire.  To compensate for this
> discrepancy, the window is allowed to artificially inflate until a new
> ack allows the left edge of the send_window (and cwnd) to move.
> >
> >  I propose the following:
> >
> >  cwnd:  A sender-side variable that limits the amount of data,
> regardless of sequence number, that the sender is allowed to have
> outstanding in the network.  Note that the cwnd variable used in this
> document reflects and controls the amount of data that a sender is
> allowed to have outstanding, and is different from TCP's definition of
> cwnd [RFC5681] in not controlling the actual data being transmitted.
> This cwnd MAY be in bytes or packets; for ease of exposition, this
> document uses cwnd in packets.
> >
> _______________________________________________
> ledbat mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/ledbat