Subject: Is it really exponential?

From: [email-masked] (Raghu Mallena)
Date: Thu, 29 Oct 1998 13:44:26 -0800 (PST)

I was looking at some traces and noticed that the Slow Start 
algorithm opens the window size by *one* segment size everytime 
an ACK is received.  This is how it was described in Van Jacobson's 
"Congestion Avoidance and Control" SIGCOM'98 paper.   Is there 
any reason why it is designed this way as opposed to opening 
the window by the amount of data that got acked?   With Delayed 
Ack in effect,  the one-segment growth scheme would increase the 
window in roughly 2^(x/2) way as opposed to a true 2^x growth.    
Basically,  RTT*logW (where W is window size in segments) being 
the time to reach steady state as computed in VJ's paper will 
not be true for Delayed Ack.   And this will be even worse 
for the stacks that are lazy about sending Acks i.e send one 
Ack for more than 2 packets (please... i dont mean to re-start 
last weeks discussion on this subject)

However,  a simple one-line fix to open the window by the amount of 
data acked (ack - snd_una) should work well always.   The window would 
still open exponentially and the time to reach full window size would 
still be in the order of RTT*logW, approximately. 

Any reason why it shouldnt be done this way?

- raghu

---
Raghu Mallena
Silicon Graphics

---

From: Mark Allman <[email-masked]>
Date: Thu, 29 Oct 1998 16:59:38 -0500

> data acked (ack - snd_una) should work well always.  The window
> would still open exponentially and the time to reach full window
> size would still be in the order of RTT*logW, approximately.
> 

I think except for the "work well always" part you are right.  I
think generally the fix you suggest works well.  It lowers the
transfer time (of short connections especially).  The size of the
burst of segments in response to an ACK is incraesed a little and
therefore, there can be a slight increase in loss.  The real problem
comes into play in reno-style recovery, where ACKs for large numbers
of un-ACKed data can come in during a slow start after an RTO
timeout.  In this case, you very much *do not* want to generate a
burst that is basically twice what we generate now.

So, a reasonable approach (I think!) is to use a ``limited byte
counting''.  Basically, you should increase the window by the number
of bytes ACKed, up to some limit like 2 segments.  So, when
responding to a correctly behaving delayed ACK receiver you are
getting better growth.  But, you are limiting the size of the burst
that any ACK can generate to one more segment than is currently
allowed in the case of receiving stretch ACK (because of a buggy
delayed ACK implementation or ACK loss).  That seems to be a good
way to do things to me.

For more information, please see my paper on this topic...

    Mark Allman. On the Generation and Use of TCP
    Acknowledgments. ACM Computer Communication Review, 28(5),
    October 1998. 
    http://gigahertz.lerc.nasa.gov/~mallman/papers/acks.ps

allman

---

From: Mark Allman <[email-masked]>
Date: Thu, 29 Oct 1998 17:03:38 -0500

> Any reason why it shouldnt be done this way?

Oh, so the last message was with my research hat on...  I should
also use my IETF hat and point out that byte counting should not be
used during slow start because the spec (2001, 2001.bis)
intentionally does not allow it.  The feeling is that this change
makes TCP more aggressive and we need to study and understand this
change before we unleash it on the network.

allman