[ih] When was Go Back N adopted by TCP

Detlef Bosau detlef.bosau at web.de
Sun May 18 13:49:39 PDT 2014


Am 18.05.2014 20:46, schrieb 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...

Nevertheless, my question has a background from my work in this days.
>
> 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.

I agree - however, care must be taken that a protocol's semantics are
not affected.

My question arouse because I'm just about to reimplement my own network
simulator - and (for the 2nd or 3rd time) I want to understand how VJCC
is integrated in TCP and particularly Karn's algorithm.

>From my knowledge up to know I always assumed TCP would do go back n
typically - as I learned now, this assumption was wrong.


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

Yes for the implementation, however a node's behaviour as seen from the
outside should follow the standards quite strict.

"Be liberal in what you accept but conservative in what you send."
>
> 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.

Not quite. The internet is always a well behaved community. E.g.:
Delayed ACK. I would have to look it up in RFC 793, but IIRC delayed ACK
is not mandatory there - actually it is highly recommended. A TCP socket
which would send a pure ACK for each received segment would certainly
work - but it would offer load to the shared resources in a network.
>
> 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?

I think it would be compatible. (Although I didn't know anything about
TCP in 1979, I was born in 1963 and I did not know anything about packet
switching in 1979.)


>
> 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
> anillustration." (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.

However, when we pursue "fairness" for TCP rates, it makes sense to have
identical time out mechanisms.
>
> However, the protocol was structured to essentially preclude certain
> implementation strategies. ARQ, for example, involves Requesting a Repeat.

Not quite. You may well request a repeat by a NACK, you may resend a
packet when there is no ACK. However, the semantics of a present ACK is
not the same as the semantics of a missing NACK.

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

We work around this lack of reliability by TCP's cumulative ACK scheme.

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

The "push" flag and the "urgent pointer" ;-)

Back to my actual work. I wanted to reproduce the step from RFC 793 to
Tahoe - and I ever thought, both did go back n - and learned: Neither
does so.

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

My basic interest is TCP flow control, what hardware limitations are
concerned, these are - at least to a huge degree - historical
considerations.
>
> 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.
>

Is this the semantics of a Source Quench?

> 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!

Yes. And they were as compatible as men and women.

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

O.k., but at one point in time, computer science must turn from a number
of kludges to an engineering science.

Detlef

-- 
------------------------------------------------------------------
Detlef Bosau
Galileistraße 30   
70565 Stuttgart                            Tel.:   +49 711 5208031
                                           mobile: +49 172 6819937
                                           skype:     detlef.bosau
                                           ICQ:          566129673
detlef.bosau at web.de                     http://www.detlef-bosau.de

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://elists.isoc.org/pipermail/internet-history/attachments/20140518/47d05c6c/attachment.htm>


More information about the Internet-history mailing list