Subject: Re: [ledbat] max cwnd

From: Janardhan Iyengar <[email-masked]>
Date: Wed, 23 Feb 2011 09:48:12 -0500

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

-- 
Janardhan Iyengar
Assistant Professor, Computer Science
Franklin & Marshall College
http://www.fandm.edu/jiyengar

---

From: Mirja Kühlewind <[email-masked]>
Date: Wed, 23 Feb 2011 16:15:40 +0100

Hi Jana, 

> So, after thinking about ALLOWED_INCREASE, TETHER, and GAIN, I'm
> increasingly leaning towards eliminating all of these variables in favor of
> simplicity.
I'm not sure if I want to change the algorithm proposed by Bittorrent 
completely. As we don't get a response when asking about the reason for these 
parameters, we might just keep them and specify the values as MUST.

About GAIN: I'm still thinking about a comment that a higher GAIN value only 
for the decrease case might be helpful in some case. I'm just not sure how 
those cases exactly look like.

ALLOWED_INCREASE and TETHER doesn't make the algorithm much more complicated 
but still not sure about the right thing here (see below)

>    if flight_size() >= cwnd:
Still not sure, this might decrease the window unnecessarily if there are not 
enough data for only a short time and than a whole bunch of data are 
available at once. 
I'm really not sure if there is THE right solution. That is why I was asking 
for references or best practice on the list. Maybe we can be a little more 
restrictive than usual because we assume time-insensitive bulk traffic. On 
the other hand we have a mechanism to detect congestion before packet loss 
occurs and can decrease the cwnd earlier anyway.

Mirja