[ih] When was Go Back N adopted by TCP

[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.

Second, formally, go-back-n says that whenever you detect a loss, you
restart transmission of *all* data beginning with the lost item.  So if
you sent bytes 1000 through 8000 and learn that there was a loss at 2000,
you resend 2000 through 8000.

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.

I believe by about 1986 or so, all TCPs were only retransmitting the data
known to be lost.  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.

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
and TCP doesn't carry a retransmission indicator in each segment. As a result,
there were various issues in accuracy.  For that, you can go read
Robert Morris' paper in AFIPS 1979, Craig Milo Rogers' notes to TCP-IP
around 1983, Raj Jain's paper at 5th Phoenix Conference on Computers
and Communications in 1986, Lixia Zhang's paper at SIGCOMM '86, my
paper with Phil Karn at SIGCOMM '87 and then Van's paper at SIGCOMM '88.

Thanks!

Craig

> if at all?
> 
> To my understanding, TCP Tahoe was based upon a go back n retransmission
> strategy, which was not yet part of RFC 793.
> 
> In RFC 793, necessary retransmissions have been started by individual
> RTO timers for each packet.
> 
> So, there must have been a change here in the 80s. When did this happen
> and why?