[ih] When was Go Back N adopted by TCP

[Jack Haverty]

Since this is a "history" forum, I'll offer my perspective as one who was
there in the 80s and involved in the TCP work...

IMHO, it's important to make the distinction between the protocol and the
implementations of that protocol.   The protocol defines the formats of the
data passing back and forth "on the wire", and the required actions that
the computer at each and take in response to receiving that data.

How a particular implementation performs that response is totally up to
that particular implementer.

So, when you're talking about ARQ, packet timers, retransmission
algorithms, et al, you're talking about the *implementation*, rather than
the TCP protocol itself.

I wrote a TCP back in the 1979 timeframe - the first one for a Unix system,
running on a PDP-11/40.  It first implemented TCP version 2.5, and later
evolved to version 4.   It was a very basic implementation, no "slow start"
or any other such niceties that were created as the Internet grew.

As far as I know, that 1979 protocol is the same protocol as is in use
today (pending IPV6 of course).   So if my 1979 TCP could somehow be loaded
into a PDP-11 today, it should still be able to communicate with all the
other TCPs out there.  Of course I haven't been tracking all the details of
the TCP work over the last few decades, so someone will tell me if I just
missed it, but I don't think anything in the actual protocol has changed.
 True?

IMHO, TCP itself, i.e. the protocol, hasn't changed at all in the last 30+
years.  However, there has been a lot of work inventing new algorithms and
putting them into implementations of TCP, probably starting with van
Jacobsen's work.

RFC 793 makes the distinction between the protocol and the algorithms used
in the implementation:

"Because of the variability of the networks that compose an internetwork
system and the wide range of uses of TCP connections the retransmission
timeout must be dynamically determined.  One procedure for determining a
retransmission time out is given here as an illustration." (page 41)

The "Example Retransmission Timeout Procedure" which follows in the RFC 793
spec is an *example*. It is not required as part of the protocol. Much of
the detail in RFC 793 about such algorithms and implementation strategies
was presented as an example. The core of the protocol itself is the packet
formats and state diagram, which all implementations must follow.

That approach provided implementers with a lot of flexibility.

This flexibility was intentional, for two reasons. I recall some of the
meetings where retransmission was discussed as TCP 4 congealed. Basically
we decided that we didn't have a clue, or at least didn't agree, what "the"
right answer should be, and much experimentation would be needed and
appropriate. The "rough consensus" criteria wasn't met, so the specific
retransmission algorithm of RFC 793 was included only as an example. It was
intended as a starting point for experimentation.

However, the protocol was structured to essentially preclude certain
implementation strategies. ARQ, for example, involves Requesting a Repeat.
But there is no guaranteed back-channel in TCP whereby you could reliably
make such a request, other than the very rudimentary Window and Sequence
Number mechanisms. No way to say "send that last packet again" for example.
We did talk about such things, a lot, but decided it was too complex,
especially when you had routers doing things like fragmentation, or the
possibility that the reverse traffic flow would be cut off. There was also
discussion of adding an "out of band" channel to TCP to enable
implementations to reliably do negotiations like ARQ but that was also
excluded to reduce complexity. ICMP was introduced as an in-band control
channel of sorts, but such packets were by definition unreliable and
therefore appropriate only for cases where losing a packet wouldn't cause
the connection to lock up or misbehave.

The second reason was that there were many conflicting goals that different
implementers faced. Some had to shoehorn the TCP into a very limited
computer (that would be me). Others were pressured to avoid using precious
computer cycles that otherwise would generate revenue. Some TCPs were used
in situations dominated by character-at-a-time Telnet activity, and users
wanted what they typed to echo immediately - so hanging on to data hoping
for more to arrive before sending it out was unacceptable. There were lots
of forces pulling different ways.

The result was that there were a lot of TCP implementations, all conforming
to the protocol, but with widely different internal algorithms.

I encountered one such implementation that was likely the simplest
possible. It would only accept the next sequential bytes in the byte stream
that would fit in its (small) buffer, and simply discard any packet that
arrived out-of-order, or any other bytes in the packet it received, knowing
they would be sent again.

Another implementation would retransmit all of its unacknowledged data
immediately whenever it received a Source Quench, following the philosophy
that a "Source Quench", despite the name, actually told it that its
previous transmission had been discarded by some router along the way and
therefore had to be retransmitted.

When I was at Oracle, we had to test our software with all the TCPs that a
customer might use. I recall that, at the time (1990 or so), there were
more than 30 unique and different implementations of TCP available just for
DOS!

So, there were (and probably still are) a lot of algorithms within
different TCP implementations that you wouldn't give any "best practice"
medals. But they are all legal implementations of the same TCP protocol.

I still have a listing of that ancient Unix TCP, written in Macro-11, dated
March 30, 1979.   One of these days I'll get it scanned!

/Jack Haverty


On Sun, May 18, 2014 at 7:26 AM, Detlef Bosau <detlef.bosau at web.de> wrote:

> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://elists.isoc.org/pipermail/internet-history/attachments/20140518/c6d2b842/attachment.htm>