[ih] When was Go Back N adopted by TCP

[Detlef Bosau]

Am 18.05.2014 16:03, schrieb Craig Partridge:
> I'll try to be brief (a multi-page essay keeps wanting to break out
> as I write this).
>
> First, worth remembering that ARQ research (Automatic Repeat reQuest), the
> work that first developed go-back-n, was happening concurrently with TCP
> development.  Sometimes TCP was ahead of the theory.  Indeed, the theory
> never quite caught up as all the ARQ research is based on a slotted
> transmission channel and the question is always "what is the most
> efficient packet to fill the current slot."  Put another way, ARQ
> doesn't do flow control.

Period :-)

I think, this is a very important note and as far as  I see, the term
"flow control" is sometimes used in a multi meaning manner.

> Second, formally, go-back-n says that whenever you detect a loss, you
> restart transmission of *all* data beginning with the lost item. 

In terms of TCP and the variables of RFC 793, you set snd.nxt to the
value of snd.una.
Doing so, you accept that some packets are retransmitted without necessity.
>  So if
> you sent bytes 1000 through 8000 and learn that there was a loss at 2000,
> you resend 2000 through 8000.

O.k., I oversimplified. When you wrote the paper together with Phil
Karn, did you assume a retransmission queue as in RFC 793?
In that case, you have one RTO timer per packet and hence can determine
the very packet which is not acknowledged timely.
In more recent RFC, we use only one RTO timer which "slides" with the
window (i.e. when a new ack arrives which does not ack all outstanding
data, you the pending RTO is cancelled and a new one is started waiting
for at least the value "snd.nxt"), hence you will restart the
transmission at snd.una.

When you use the original concept of a retransmission queue, you can
restart the transmission, referring to your example, with 2000 when 2000
was the first loss.
>
> Some of the first TCP implementations did something like this (cf. David
> Plummer's note "Re: Interesting Happenings" on the TCP-IP list of 8 June 1984).
> Many other TCPs would only retransmit a chunk of data at 2000 and wait for
> an ACK to see where the next data gap was (also noted in Plummer's note).
> At some point in the early 1980s Jon Postel sent out a note saying that the
> retransmission only of the data immediately around the known loss was the
> right thing to do, but I can't find the note in my (limited) archives.

That make sense, particularly as it makes flow control difficult to
retransmit data unnecessarily and cause duplicates.

>
> I believe by about 1986 or so, all TCPs were only retransmitting the data
> known to be lost. 

I.e. they followed the scheme of a retransmission queue as outlined in
RFC 793?

>  Certainly, the 4.3bsd release of June 1986 only
> retransmitted data that was known to be lost. It is my recollection that
> 4.2bsd only only retransmitted data that was lost as it was based on the
> BBN 4.1c TCP, which only retransmitted lost data.  So by 1986 and probably
> as early as 1979 if not before, BSD TCP was *not* go back n.  (One might say
> it was a flow controlled variant of what theory called "selective repeat ARQ").
>
> TCP Tahoe was released in June 1988 and added the initial Van Jacobson
> versions of slow start and the like.  So, in short, TCP Tahoe was never based
> on go back n.

However, I just had a look at the congavoid paper yesterday, the
congavoid paper does not mention a retransmission queue.
In addition: When Tahoe does selective ARQ, how is it ensured that any
sent  (or re-sent) packets stays within the limites of the actual CWND?
Is it done on per packet basis? (This would require some more lines than
the "three lines of code" mentioned by VJ.)

>
> The question of how to do retransmission RTO timers has a parallel history
> until it converges with Van's work in 1988. The broad point is that
> people did not necessarily track each packet's round-trip separately
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
exactly that's the point.


Detlef