Subject: Send window update algorithm ...

From: Ramesh Shankar <[email-masked]>
Date: Tue, 27 Jun 2000 12:19:56 -0600

Here is what I understood about a correct implementation of a send
window update algorithm (This algorithm is responsible for deciding
whether or not the SEG.WND information in an incoming segment can be
used to update the SND.WND information):

1. Information from older segments shouldn't be used. (SEG.ACK < SND.UNA
or SEG.ACK > SND.MAX). It is assume that the received segment has been
trimmed to fit in the receive window already.
2. Out of order segments shouldn't end up shrinking the window
(especially out of order plain ACKs: see RFC 793, page 43).

Here is one which I add to the above list:

3. With bidirectional data transfer, we could have updated the window
using an out of order segment. If the peer times out and retransmits (or
if we got a fast retransmit), we will start getting sequence #s which
are less than SND.WL1. As long as these segments ACK newer data or
advertise a bigger window, we should use SEG.WND to update SND.WND.

The standard BSD algorithm below, doesn't handle case 3 mentioned above:

Use SEG.WND to update SND.WND if:

- if (SEG.SEQ > SND.WL1)
- OR if ((SEG.SEQ == SND.WL1) && (SEG.ACK > SND.WL2))
- OR if ((SEG.ACK == SND.WL2)) && (SEG.WND > SND.WND))

In fact, during my testing, I ran exactly into case 3 mentioned above.
Instead of using the window information from a retransmission by the
peer which ACKed new data that we sent and which made the window 0, we
ignored the SEG.WND information (as SEG.SEQ < WL1) and continued to
think that we had a non-zero window and tried to send another segment.
To the code this appeared as if the window had shrunk.

I am not sure why the following algorithm can't be used, which handles
all the cases mentioned above:

Use SEG.WND to update SND.WND if:

- if (SEG.SEQ > SND.WL1) [Set SND.WL1 = SEG.SEQ]
- OR if (SEG.ACK > SND.WL2) [Set SND.WL2 = SEG.ACK]
- OR if ((SEG.SEQ == SND.WL1) && (SEG.ACK == SND.WL2) && (SEG.WND >
SND.WND))