Which TCP window update is most recent?

Question

I was writing a TCP implementation, did all the fancy slow and fast retransmission stuff, and it all worked so I thought I was done. But then I reviewed my packet receive function (almost half of the 400 lines total code), and realized that my understanding of basic flow control is incomplete...

Suppose we have a TCP connection with a "sender" and "receiver". Suppose that the "sender" is not sending anything, and the receiver is stalling and then unstalling.

Since the "sender" is not sending anything, the "receiver" sees no ack_no delta. So the two window updates from the "receiver" look like:

1. ack_no = X, window = 0
2. ack_no = X, window = 8K

since both packets have the same ack_no, and they could be reordered in transit, how does the sender know which came first?

If the sender doesn't know which came first, then, after receiving both packets, how does it know whether it's allowed to send?

One guess is that maybe the window's upper endpoint is never allowed to decrease? Once the receiver has allocated a receive buffer and advertised it, it can never un-advertise it? In that case the window update could be reliably handled via the following code (assume no window scale, for simplicity):

  // window update  (https://stackoverflow.com/questions/63931135/)
  int ack_delta = pkt_ack_no - c->tx_sn_ack;
  c->tx_window  = MAX(BE16(PKT.l4.window), c->tx_window - ack_delta);
  if (c->tx_window)
    Net_Notify(); // wake up transmission

But this is terrible from a receiver standpoint: it vastly increases the memory you'd need to support 10K connections reliably. Surely the protocol is smarter than that?

Answer 1

There is an assumption that the receive buffer never shrinks, which is intentionally undocumented to create an elite "skin in the game" club in order to limit the number of TCP implementations.

The original standard says that shrinking the window is "discouraged" but doesn't point out that it can't work reliably:

The mechanisms provided allow a TCP to advertise a large window and to subsequently advertise a much smaller window without having accepted that much data. This, so called "shrinking the window," is strongly discouraged.

Even worse, the standard is actually missing the MAX operation proposed in the question, and just sets the window from the most recent packet if the acknowledgement number isn't increasing:

      If SND.UNA < SEG.ACK =< SND.NXT, the send window should be
      updated.  If (SND.WL1 < SEG.SEQ or (SND.WL1 = SEG.SEQ and
      SND.WL2 =< SEG.ACK)), set SND.WND <- SEG.WND, set
      SND.WL1 <- SEG.SEQ, and set SND.WL2 <- SEG.ACK.

      Note that SND.WND is an offset from SND.UNA, that SND.WL1
      records the sequence number of the last segment used to update
      SND.WND, and that SND.WL2 records the acknowledgment number of
      the last segment used to update SND.WND.  The check here
      prevents using old segments to update the window.

so it will fail to grow the window if packets having the same ack number are reordered.

Bottom line: implement something that actually works robustly, not what's in the standard.