<div dir="ltr">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...<div><br></div><div>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.</div>
<div><br></div><div>How a particular implementation performs that response is totally up to that particular implementer.</div><div><br></div><div>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.</div>
<div><br></div><div>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.  </div>
<div><br></div><div>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?</div>
<div><br></div><div>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. </div>
<div><br></div><div>RFC 793 makes the distinction between the protocol and the algorithms used in the implementation:</div><div><br></div><div>"<font color="#000000"><span style="white-space:pre-wrap">Because of the variability of the networks that compose an </span></font><span style="white-space:pre-wrap;color:rgb(0,0,0)">internetwork system and the wide range of uses of TCP connections the </span><span style="white-space:pre-wrap;color:rgb(0,0,0)">retransmission timeout must be dynamically determined.  One procedure </span><span style="white-space:pre-wrap;color:rgb(0,0,0)">for determining a retransmission time out is given here as an</span><span style="white-space:pre-wrap;color:rgb(0,0,0)"> illustration." (page 41)</span></div>
<div><font color="#000000"><span style="white-space:pre-wrap"><br></span></font></div><div><font color="#000000"><span style="white-space:pre-wrap">The "</span></font><span style="white-space:pre-wrap;color:rgb(0,0,0)">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.</span></div>
<div><span style="white-space:pre-wrap;color:rgb(0,0,0)"><br></span></div><div><span style="white-space:pre-wrap;color:rgb(0,0,0)">That approach provided implementers with a lot of flexibility.</span></div><div><span style="white-space:pre-wrap;color:rgb(0,0,0)"><br>
</span></div><div><span style="white-space:pre-wrap;color:rgb(0,0,0)">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.</span></div>
<div><span style="white-space:pre-wrap;color:rgb(0,0,0)"><br></span></div><div><span style="white-space:pre-wrap;color:rgb(0,0,0)">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.</span></div>
<div><span style="white-space:pre-wrap;color:rgb(0,0,0)"><br></span></div><div><span style="white-space:pre-wrap;color:rgb(0,0,0)">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.</span></div>
<div><span style="white-space:pre-wrap;color:rgb(0,0,0)"><br></span></div><div><span style="white-space:pre-wrap;color:rgb(0,0,0)">The result was that there were a lot of TCP implementations, all conforming to the protocol, but with widely different internal algorithms.</span></div>
<div><span style="white-space:pre-wrap;color:rgb(0,0,0)"><br></span></div><div><span style="white-space:pre-wrap;color:rgb(0,0,0)">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.</span></div>
<div><span style="white-space:pre-wrap;color:rgb(0,0,0)"><br></span></div><div><span style="white-space:pre-wrap;color:rgb(0,0,0)">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.</span></div>
<div><span style="white-space:pre-wrap;color:rgb(0,0,0)"><br></span></div><div><span style="white-space:pre-wrap;color:rgb(0,0,0)">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!</span></div>
<div><span style="white-space:pre-wrap;color:rgb(0,0,0)"><br></span></div><div><span style="white-space:pre-wrap;color:rgb(0,0,0)">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. </span></div>
<div class="gmail_extra"><br></div><div class="gmail_extra">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!</div><div class="gmail_extra">
<br></div><div class="gmail_extra">/Jack Haverty</div><div class="gmail_extra"><br><br><div class="gmail_quote">On Sun, May 18, 2014 at 7:26 AM, Detlef Bosau <span dir="ltr"><<a href="mailto:detlef.bosau@web.de" target="_blank">detlef.bosau@web.de</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Am 18.05.2014 16:03, schrieb Craig Partridge:<br>
<div class="">> I'll try to be brief (a multi-page essay keeps wanting to break out<br>
> as I write this).<br>
><br>
> First, worth remembering that ARQ research (Automatic Repeat reQuest), the<br>
> work that first developed go-back-n, was happening concurrently with TCP<br>
> development.  Sometimes TCP was ahead of the theory.  Indeed, the theory<br>
> never quite caught up as all the ARQ research is based on a slotted<br>
> transmission channel and the question is always "what is the most<br>
> efficient packet to fill the current slot."  Put another way, ARQ<br>
> doesn't do flow control.<br>
<br>
</div>Period :-)<br>
<br>
I think, this is a very important note and as far as  I see, the term<br>
"flow control" is sometimes used in a multi meaning manner.<br>
<div class=""><br>
> Second, formally, go-back-n says that whenever you detect a loss, you<br>
> restart transmission of *all* data beginning with the lost item.<br>
<br>
</div>In terms of TCP and the variables of RFC 793, you set snd.nxt to the<br>
value of snd.una.<br>
Doing so, you accept that some packets are retransmitted without necessity.<br>
<div class="">>  So if<br>
> you sent bytes 1000 through 8000 and learn that there was a loss at 2000,<br>
> you resend 2000 through 8000.<br>
<br>
</div>O.k., I oversimplified. When you wrote the paper together with Phil<br>
Karn, did you assume a retransmission queue as in RFC 793?<br>
In that case, you have one RTO timer per packet and hence can determine<br>
the very packet which is not acknowledged timely.<br>
In more recent RFC, we use only one RTO timer which "slides" with the<br>
window (i.e. when a new ack arrives which does not ack all outstanding<br>
data, you the pending RTO is cancelled and a new one is started waiting<br>
for at least the value "snd.nxt"), hence you will restart the<br>
transmission at snd.una.<br>
<br>
When you use the original concept of a retransmission queue, you can<br>
restart the transmission, referring to your example, with 2000 when 2000<br>
was the first loss.<br>
<div class="">><br>
> Some of the first TCP implementations did something like this (cf. David<br>
> Plummer's note "Re: Interesting Happenings" on the TCP-IP list of 8 June 1984).<br>
> Many other TCPs would only retransmit a chunk of data at 2000 and wait for<br>
> an ACK to see where the next data gap was (also noted in Plummer's note).<br>
> At some point in the early 1980s Jon Postel sent out a note saying that the<br>
> retransmission only of the data immediately around the known loss was the<br>
> right thing to do, but I can't find the note in my (limited) archives.<br>
<br>
</div>That make sense, particularly as it makes flow control difficult to<br>
retransmit data unnecessarily and cause duplicates.<br>
<div class=""><br>
><br>
> I believe by about 1986 or so, all TCPs were only retransmitting the data<br>
> known to be lost.<br>
<br>
</div>I.e. they followed the scheme of a retransmission queue as outlined in<br>
RFC 793?<br>
<div class=""><br>
>  Certainly, the 4.3bsd release of June 1986 only<br>
> retransmitted data that was known to be lost. It is my recollection that<br>
> 4.2bsd only only retransmitted data that was lost as it was based on the<br>
> BBN 4.1c TCP, which only retransmitted lost data.  So by 1986 and probably<br>
> as early as 1979 if not before, BSD TCP was *not* go back n.  (One might say<br>
> it was a flow controlled variant of what theory called "selective repeat ARQ").<br>
><br>
> TCP Tahoe was released in June 1988 and added the initial Van Jacobson<br>
> versions of slow start and the like.  So, in short, TCP Tahoe was never based<br>
> on go back n.<br>
<br>
</div>However, I just had a look at the congavoid paper yesterday, the<br>
congavoid paper does not mention a retransmission queue.<br>
In addition: When Tahoe does selective ARQ, how is it ensured that any<br>
sent  (or re-sent) packets stays within the limites of the actual CWND?<br>
Is it done on per packet basis? (This would require some more lines than<br>
the "three lines of code" mentioned by VJ.)<br>
<div class=""><br>
><br>
> The question of how to do retransmission RTO timers has a parallel history<br>
> until it converges with Van's work in 1988. The broad point is that<br>
> people did not necessarily track each packet's round-trip separately<br>
</div>^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^<br>
exactly that's the point.<br>
<span class="HOEnZb"><font color="#888888"><br>
<br>
Detlef<br>
</font></span></blockquote></div><br></div></div>